 |
Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска
|
|
|
|
Графический интерфейс представлен на рисунке 1.14.
Рисунок 1.14 – Форма
uses wseme1;
procedure TForm1. Button16Click (Sender: TObject);
begin
close;
end;
procedure TForm1. Button1Click (Sender: TObject);
var i:integer;
begin
// генерируем множество, состоящее из случайных чисел
Randomize;
for i:=0 to StringGrid1. RowCount do
StringGrid1. Cells [0, i]:=IntToStr (Random(10000)+1);
end;
procedure TForm1. FormCreate (Sender: TObject);
begin
Button1. Click();
end;
procedure TForm1. Edit1Exit (Sender: TObject);
begin
// проверяем заполнено ли поле
if edit1. Text='' then begin
MessageDlg ('Введите число не больше 15', mtError, [mbOk, mbCancel], 0);
exit; end else
StringGrid1. RowCount:=strtoint (edit1. Text);
StringGrid2. RowCount:=strtoint (edit1. Text);
end;
procedure TForm1. Button3Click (Sender: TObject);
var
n, minimum, j, i, obmen:integer;
a:array [1..15] of integer;
begin
n:=strtoint (edit1. Text);
// задание массива
for j:=1 to n do
a[j]:=StrToInt (StringGrid1. Cells [0, j‑1]);
for j:=1 to n do begin
// номер минимального элемента
minimum:=j;
for i:=j+1 to n do if a[i] < a [minimum] then minimum:=i;
// запоминание минимального элемента
obmen:=a[j];
a[j]:=a[minimum];
a[minimum]:=obmen;
// вывод отсортированного массива
for i:=0 to n do
stringgrid2. Cells [0, j‑1]:=inttostr (a[j]);
end;
end;
procedure TForm1. Button4Click (Sender: TObject);
var
n, obmen, i, j:integer;
a:array [1..15] of integer;
colicobmen:boolean;
begin
n:=strtoint (edit1. Text);
// задание массива
for i:=1 to n do
a[i]:= StrToInt (StringGrid1. Cells [0, i‑1]);
// сортировка массива
repeat
colicobmen:=FALSE;
for j:=1 to n‑1 do
if a[j] > a [j+1] then
begin
obmen:=a[j];
a[j]:=a [j+1];
a [j+1]:=obmen;
colicobmen:=TRUE;
end;
// вывод массива
for i:=1 to n do
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
until not colicobmen;
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
end;
procedure TForm1. Button5Click (Sender: TObject);
var
a:array [1..15] of integer;
i, j, m, L, R, n, x:integer;
begin
n:=strtoint (edit1. Text);
// задание массива
for i:=1 to n do
a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]);
// алгоритм сортировки двоичным включением
for i:=2 to n do
begin
x:=a[i];
L:=1;
R:=i;
while L<R do begin
m:=(L+R) div 2;
if a[m]<=x then L:=m+1 else R:=m;
end;
for j:=i downto R+1 do a[j]:=a [j‑1];
a[R]:=x;
end;
// вывод отсортированного массива
for i:=1 to n do
|
|
|
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
end;
procedure TForm1. Button6Click (Sender: TObject);
const t=15;
var
n:integer;
a:array [1..15] of integer;
i, j, k, s:integer;
x:integer;
m:1..t;
h:array [1..t] of integer;
begin
n:=strtoint (edit1. Text);
// задание массива
for i:=1 to n do
a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]);
// алгоритм Шелла
h[1]:=9;
h[2]:=5;
h[3]:=3;
h[4]:=1;
for m:=1 to t do
begin k:=h[m];
s:=-k;
// барьеры для каждого шага
for i:=k+1 to n do
begin x:=a[i];
j:=i-k;
if s=0 then s:=-k;
s:=s+1;
a[s]:=x;
while x<a[j] do begin a [j+k]:=a[j];
j:=j-k;
end;
a [j+k]:=x;
end;
end;
// вывод отсортированного массива
for i:=1 to n do
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
end;
procedure TForm1. Button7Click (Sender: TObject);
var
n:integer;
a:array [1..15] of integer;
L, R, x, k:integer;
procedure sift (L, R:integer);
var
i, j:integer;
x, y:integer;
begin
i:=L;
j:=2*L;
x:=a[L];
if (j<R) and (a[j]<a [j+1]) then j:=j‑1;
while (j<=R) and (x<a[j]) do begin y:=a[i];
a[i]:=a[j];
a[j]:=y;
a[i]:=a[j];
i:=j;
j:=2*j;
if (j<R) and (a[j]<a [j+l]) then j:=j+l;
end;
end;
begin
n:=strtoint (edit1. Text);
// задание искомого массива
for k:=1 to n do
a[k]:=StrToInt (StringGrid1. Cells [0, k‑1]);
// алгоритм сортировки с помощью дерева
// построение пирамиды
L:=(n div 2)+1;
R:=n;
while L>1 do begin L:=L‑1;
SIFT (L, R);
end;
// сортировка
while R>1 do begin x:=a[l];
a[l]:=a[R];
a[R]:=x;
R:=R‑1;
SIFT (1, R);
end;
// вывод отсортированного массива
for k:=1 to n do
stringgrid2. Cells [0, k‑1]:=inttostr (a[k]);
end;
procedure TForm1. Button8Click (Sender: TObject);
var
n:integer;
a:array [1..15] of integer;
i, j, x:integer;
begin
n:=strtoint (edit1. Text);
// задание искомого массива
for i:=1 to n do
a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]);
// алгоритм пузырьковой сортировки
for i:=2 to n do for j:=n downto i do begin
if a [j‑1]>a[j] then begin x:=a [j‑1];
a [j‑1]:=a[j];
a[j]:=x;
end;
end;
// вывод отсортированного массива
for i:=1 to n do
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
end;
procedure TForm1. Button9Click (Sender: TObject);
var
n:integer;
a:array [1..15] of integer;
i, j, k, L, R, x: integer;
begin
n:=strtoint (edit1. Text);
// задание искомого массива
for i:=1 to n do
a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]);
// алгоритм шейкерной сортировки
L:=2;
R:=-n;
k:=n;
repeat
for i:=2 to n do
for j:=-R downto L do begin
if a [j‑1]>a[j] then begin x:=a [j‑1];
a [j‑1]:=a[j];
a[j]:=x;
k:=j;
end;
end;
L:=k+1;
for i:=2 to n do
for j:=L to R do begin
if a [j‑1]>a[j] then begin x:=a [j‑1] end else
a [j‑1]:=a[j];
a[j]:=x;
k:=-j;
end;
R:=k‑1;
until L>R;
// вывод отсортированного массива
|
|
|
for i:=1 to n do
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
end;
procedure TForm1. Button10Click (Sender: TObject);
var
n:integer;
a:array [1..15] of integer;
i:integer;
procedure sort (L, R: integer);
var
i, j:integer;
x, y:integer;
begin
i:=L;
j:=R;
x:=a[(L+R) div 2];
repeat
while a[i]<x do i:=i+l;
while x<a[j] do j:=j‑1;
if i<=j then begin y:=a[i];
a[i]:=a[j];
a[j]:=y;
i:=i+l;
j:=j-l;
end;
until i>j;
if L<j then SORT (L, j);
if i<R then SORT (i, R);
end;
begin
n:=strtoint (edit1. Text);
// задание искомого массива
for i:=1 to n do
a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]);
// алгоритм быстрой сортировки
// рекурсивная процедура
SORT (1, n);
// вывод отсортированного массива
for i:=1 to n do
stringgrid2. Cells [0, i‑1]:=inttostr (a[i]);
end;
procedure TForm1. Button17Click (Sender: TObject);
begin
AboutBox.showmodal;
end;
end.
Пример выполнения
Задание: заданы два одномерных массива А и В, содержащие по n элементов каждый. Объединить эти два массива в один, исключив повторяющиеся элементы. Считать, что массивы А и В отсортированы по убыванию.
Теоретическое описание метода
Метод пузырька, как таковой, не требует глубокого рассмотрения. Смысл метода заключается в том, что мы находим в определённой области максимальный (или минимальный элемент) и помещаем его в начало исследуемой области, далее уменьшаем область поиска на 1 и повторяем те же действия, не имеет худшего случая, всегда O (n 2).
Рисунок 1.15 – Форма с результатами расчета
Код программы на Delphi:
const n=5;
var
a:array [1..n] of Byte;
b:array [1..n] of Byte;
c: array of Byte;
i:byte;
implementation
procedure TForm1. Button1Click (Sender: TObject);
var m, x:byte;
begin
randomize;
for i:=1 to n do begin
a[i]:=random(200);
b[i]:=random(200);
end;
for m:=n downto 2 do begin
for i:=1 to m‑1 do begin
if a[i]<a [i+1] then begin
x:=a[i];
a[i]:=a [i+1];
a [i+1]:=x;
end;
if b[i]<b [i+1] then begin
x:=b[i];
b[i]:=b [i+1];
b [i+1]:=x;
end;
end;
end;
for i:=1 to n do begin
StringGrid1. Cells [i – 1,0]:=IntToStr (a[i]);
StringGrid2. Cells [i – 1,0]:=IntToStr (b[i]);
end;
end;
procedure TForm1. Button2Click (Sender: TObject);
label m1;
var k, l, x:byte;
begin
k:=1;
l:=1;
x:=0;
SetLength (c, 1);
while (k<=n) or (l<=n) do begin
m1: if a[k]>b[l] then begin
x:=x+1;
SetLength (c, x);
c [x‑1]:=a[k];
k:=k+1;
goto m1;
end;
if a[k]<b[l] then begin
x:=x+1;
SetLength (c, x);
c [x‑1]:=b[l];
end;
l:=l+1;
end;
For i:=0 to high(c) do ListBox1. Items. Add (IntToStr(c[i]));
end;
end.
Варианты заданий
Варианты 1 – 27 имеют пояснения к выполнению решений в [7].
1) Для заданного массива A размером n требуется выполнить проверку на упорядоченность. Результат присвоить переменной строкового типа (сделать вывод, каким именно образом упорядочен массив, если он окажется упорядоченным: по возрастанию, по убыванию, по неубыванию, по невозрастанию). Пояснения в [7], стр. 245.
|
|
|
2) Выполнить поиск заданного элемента в упорядоченном массиве. Пояснения в [7], стр. 246.
3) Требуется объединить два упорядоченных по возрастанию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2 N также упорядоченный по возрастанию. Пояснения в [7], стр. 247.
4) Требуется объединить два упорядоченных по убыванию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2 N также упорядоченный по убыванию. Пояснения в [7], стр. 247.
5) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2 N, упорядоченный по возрастанию. [7], стр. 247.
6) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2 N, упорядоченный по убыванию. Пояснения в [7], стр. 247.
7) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по возрастанию в один массив размером 2 N, упорядоченный по неубыванию. [7], стр. 247; [9], стр. 75.
8) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по убыванию в один массив размером 2 N, упорядоченный по невозрастанию. Пояснения в [7], стр. 247.
9) Требуется определить количество совпадающих элементов двух упорядоченных по убыванию массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
10) Требуется определить количество совпадающих элементов двух неупорядоченных массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
11) Требуется определить количество совпадающих элементов двух упорядоченных по убыванию массивов A и B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.
12) Требуется определить количество совпадающих элементов двух неупорядоченных массивов A и B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.
13) Требуется определить количество совпадающих элементов двух упорядоченных по возрастанию массивов A и B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
|
|
|
14) Фамилии участников соревнований по фигурному катанию после короткой программы расположены в порядке, соответствующем занятому месту. Составить список участников в порядке их стартовых номеров для произвольной программы (участники выступают в порядке, обратном занятым местам). Пояснения в [7], стр. 255.
15) Японская радиокомпания провела опрос 250 радиослушателей по трём вопросам:
1) Какое животное Вы связываете с Японией и японцами?
2) Какая черта характера присуща японцам больше всего?
3) Какой неодушевлённый предмет или понятие Вы связываете с Японией?
Большинство опрошенных прислали ответы на все или на часть вопросов. Составить программу получения первых пяти наиболее часто встречающихся ответов по каждому вопросу и доли (в%) каждого такого ответа. Предусмотреть необходимость сжатия столбца ответов в случае отсутствия ответов на некоторые вопросы. Пояснения в [7], стр. 264.
16) В памяти компьютера хранится список фамилий абонентов в алфавитном порядке их номеров телефонов. Составить программу, обеспечивающую быстрый поиск фамилии абонента по номеру телефона. Пояснения в [7], стр. 266.
17) В памяти ЭВМ хранятся списки номеров телефонов и фамилий абонентов, упорядоченные по номерам телефонов, для каждого из пяти телефонных узлов города. Один телефонный узел включает несколько АТС (не более 10). Номера АТС (первые две цифры номера телефона), относящихся к каждому телефонному узлу, также хранятся в памяти ЭВМ. Составить программу, обеспечивающую быстрый поиск фамилии абонента по заданному номеру телефона (количественные данные по телефонной сети не относятся к г. Москва). Пояснения в [7], стр. 266
18) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом пузырька.
19) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом пузырька.
20) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом Шелла.
21) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом Шелла.
22) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом прямого включения. Пояснения в [9], стр. 78 – стр. 80.
23) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по возрастанию методом прямого выбора. Пояснения в [9], стр. 79 – стр. 80.
|
|
|
24) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом прямого включения. Пояснения в [9], стр. 78.
25) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом прямого выбора. Пояснения в [9], стр. 79 – стр. 80.
26) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом сортировки прямым обменом (шейкерная сортировка).
27) Требуется упорядочить заданный одномерный массив A размером N (N – заданное натуральное число) по убыванию методом улучшенной сортировки разделением (быстрая сортировка с рекурсией).
28) Составить программу сортировки, используя деревья сортировки (улучшенная сортировка выбором – сортировка с помощью дерева).
29) Составить программу сортировки в файле (сортировка последовательного файла).
30) Составить программу сортировки в файле (сортировка последовательного файла слиянием).
31) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Если элементы массива А составляют строго монотонную последовательность, то все положительные элементы массива заменить единицей, иначе отсортировать массив по возрастанию.
32) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Если имеется хотя бы одна пара совпадающих элементов, то упорядочить элементы этого массива по неубыванию, иначе записать элементы этого массива в обратном порядке.
33) Заданы два одномерных целочисленных массива А и В, состоящие из N элементов каждый (N – заданное натуральное число). Объединить элементы этих двух массивов в один и упорядочить их по неубыванию, удалив из него элементы, являющиеся четными положительными числами.
34) Дан одномерный целочисленный массив А, состоящий из N элементов (N – заданное натуральное число). Присвоить переменной F значение 1, если элементы массива составляют строго возрастающую последовательность, F =-1, если строго убывающую, F =2, если элементы массива составляют знакочередующуюся последовательность, F =0, если она не является строго монотонной или знакочередующейся.
35) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Упорядочить массив А по неубыванию, воспользовавшись следующим алгоритмом сортировки. Отыскивается максимальный элемент и переносится в конец. Затем этот алгоритм применяется ко всем элементам кроме последнего и т. д.
36) Даны два одномерных целочисленных массива А и В, состоящих из N элементов каждый (N – заданное натуральное число). Сформировать массив, элементы которого являются пересечением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значения заносить только один раз. Если пресечение массивов есть пустое множество, то выдать соответствующее текстовое сообщение.
37) Даны два одномерных целочисленных массива А и В, состоящих из N элементов каждый, N – заданное натуральное число. Сформировать массив С, элементы которого являются объединением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значение заносить только один раз.
38) Дан одномерный массив А, состоящий из N элементов (N – заданное натуральное число). Присвоить переменной F =1, если элементы массива составляют строгую возрастающую арифметическую прогрессию, и F =-1, если строго убывающую арифметическую прогрессию.
39) Дан одномерный целочисленный массив А, состоящий из N элементов, N – заданное натуральное число. Пусть МАХ – наибольшее, а MIN – наименьшее значения среди элементов массива. Составить одномерный массив В из простых чисел из сегмента [ MIN, МАХ ], которые не являются элементами массива А, записав его элементы в порядке неубывания. Если таких элементов нет, то выдать соответствующее текстовое сообщение.
40) Каждый из 12 магазинов имеет свой список товаров с известными ценами и в известном количестве. Число товаров в каждом списке различно и заранее не определено. Подсчитать, на какую сумму денег имеет товаров каждый магазин, расположив список в порядке убывания этой суммы.
41) Каждая из 30 групп студентов имеет свой процент успеваемости (от 0 % до 100 %). Составить список номеров групп, которым необходимо повысить успеваемость до среднего уровня. Список расположить в порядке убывания процента успеваемости этих групп.
42) В магазине имеются товары различных наименований. В течение дня каждый из М покупателей (М – заданное число) сообщил о своем намерении приобрести определенное количество товара одного из наименований. Требуется определить суммарный спрос на товары каждого наименования, расположив товары в порядке убывания дневного спроса на них.
43) Опросили 200 подписчиков. Каждый из них назвал три любимые газеты. Напечатать пронумерованный список первых 10 наиболее популярных газет, расположив названия газет в списке в порядке уменьшения числа поданных за них голосов. Предусмотреть, что каждый из опрошенных должен назвать три разные газеты, а общее число названных газет может быть как больше, так и меньше 10.
44) Каждый из X магазинов в течение месяца работал Di дней (N и Di – заданные числа, где i =l, 2,…, X). Известна прибыль каждого магазина в каждый день его работы. Необходимо напечатать упорядоченный по месячным доходам список названий магазинов, имеющих прибыль в пересчете на один день работы выше средней дневной прибыли по всем магазинам.
45) В гостинице N этажей по M номеров на этаже (N и М заданы, а нумерация гостиничных номеров сплошная). Требуется для каждого номера ввести его стоимость и информацию о том, свободен он, занят или забронирован, а затем получить ведомости всех свободных, занятых и забронированных номеров в порядке возрастания их стоимости с указанием стоимости проживания, этажа и номера гостиницы.
46) В итоговой таблице первого круга футбольного чемпионата, каждая из N команд (N и названия команд заданы) представлена количеством забитых и пропущенных голов в каждой из встреч с противниками. Перечислить команды, которые в сумме забили в чужие ворота голов больше, чем пропустили в свои, в порядке убывания разности забитых и пропущенных голов.
47) По результатам опроса прошлого года известен список 10 политических деятелей в порядке убывания их популярности. Проведен новый опрос. Каждый из N журналистов (N – заданное число) назвал три различные фамилии из этого списка. Требуется получить новый список в порядке убывания популярности политических деятелей и показать место, которое занимал каждый деятель в предыдущем опросе. Предусмотреть проверку: каждый из опрошенных журналистов называл разные фамилии и только из имеющихся в старом списке.
48) Опросили 30 кинологов, каждый из которых 3 раза назвал одну породу собак или разные породы собак в любом сочетании, как самую популярную (популярные) по его мнению. Вывести на экран список пород, попавших в первую десятку в порядке убывания популярности, с указанием числа полученных ими голосов опрошенных.
49) Каждая из М библиотек района (М – задано) составляет заявку на приобретение книг. Заявка содержит перечень книг, состоящий из не более 20 наименований. Каждая библиотека в каждой строке заявки указывает название книги, фамилию автора, а также количество экземпляров. Определить суммарный спрос на каждую из указанных книг, и напечатать общий список книг в порядке убывания спроса.
50) 200 учеников шести школ города (номера школ заданы) принимают участие в тестировании по математике. Правильные численные ответы к пяти предложенным задачам даны. О каждом ученике известно: фамилия, номер школы и пять ответов на задачи. Сведения об учениках не имеют определенной упорядоченности. Составить списки учеников по школам, расположив в каждом списке фамилии в порядке убывания количества решенных задач. Предусмотреть возможный ответ «не решил».
51) Каждое из М садоводческих товариществ (М – заданное число) направляет на базу свой список-заявку с указанием наименований требуемых и семян и их количества в кг. Число наименований семян в заявке для каждого товарищества не превышает 20‑ти. Составить суммарный запрос на базу, указав общее необходимое количество семян каждого вида, расположив наименования в списке в порядке убывания спроса.
52) В массив размерности N (N – заданное натуральное число) ввести слова длиной не более 15 символов каждое. Вывести на экран эти слова в порядке увеличения их длины с указанием количества букв «i» в каждом из них. Выполнить проверку вводимой информации.
53) Имеются сведения о каждом рейсе Аэрофлота с номерами от 1 до 100: пункт назначения и количество перевезенных пассажиров. Определить количество пунктов назначения и построить списки номеров рейсов для каждого из них в порядке уменьшения числа пассажиров, перевезенных этими рейсами.
54) Ввести в массив N произвольных чисел (N – заданное натуральное число). Отсортировать отрицательные числа по убыванию, положительные – по возрастанию, оставив отрицательные на местах, принадлежащих отрицательным, а положительные на местах, принадлежащих положительным. Постараться дополнительных массивов не использовать. Вывести на экран исходный и полученный массивы.
55) Ввести произвольные числа в два одномерных массива одинакового размера N (N – заданное натуральное число). Переставить элементы первого массива так, чтобы его максимальный элемент находился на месте, расположения максимального элемента из второго массива, а каждый очередной по убыванию элемент из первого массива располагался на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать модифицированный массив.
56) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Изменить порядок следования элементов в нем на обратный отдельно до и отдельно после К -го элемента массива (К задано). Напечатать модифицированный массив. При вводе данных осуществить проверку.
57) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Не изменяя состояния этого массива и используя лишь один дополнительный массив, напечатать номера элементов исходного массива, соответствующие порядку убывания значений элементов. При вводе данных осуществить проверку.
58) В два одномерных массива одинакового размера N (N – заданное натуральное число) ввести произвольные числа. Не изменяя исходных массивов, сформировать из элементов первого массива третий массив так, чтобы максимальный элемент первого массива в третьем находился на месте, соответствующем расположению максимального во втором, а каждый очередной по убыванию элемент из первого массива располагался в третьем на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать все три массива.
59) Напечатать в возрастающем порядке все четырехзначные натуральные числа, все цифры которых являются соседями в натуральном ряду. Примерами таких чисел являются 4756 и 7645. Найти количество и среднее арифметическое этих чисел.
60) Ввести числовую матрицу размером N x M (N, M заданы). Найти максимальный элемент среди расположенных в тех строках матрицы, которые являются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить, что такого элемента нет.
Вопросы для самопроверки
1) Какими свойствами обладает отношение частичного порядка? Приведите примеры этого отношения.
2) Дайте определение отношения линейного порядка.
3) Сформулируйте постановку задачи сортировки.
4) В чём заключается преимущество отсортированных (упорядоченных) данных?
5) Как рассматривается задача сортировки с точки зрения программирования?
6) От каких факторов зависит эффективность алгоритма сортировки?
7) Перечислите наиболее часто используемые на практике методы поиска и сортировки.
8) Каким образом могут быть представлены данные при поиске и сортировке?
9) Перечислите основные операции при работе с данными.
10) В чём заключается алгоритм линейного поиска?
11) В чём заключается алгоритм бинарного поиска?
12) Опишите кратко поиск в бинарных деревьях.
13) Какие функции используются при оценке времени исполнения алгоритма?
14) В чём заключается метод сортировки вставками?
15) В чём заключается метод сортировки с помощью включения, прямого включения?
16) В чём заключается метод Шелла?
17) Опишите сортировку с помощью обменов.
18) Опишите алгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).
|
|
|
