Основы дискретной математики (стр. 7 из 23)
Теоретическое описание метода
Метод пузырька, как таковой, не требует глубокого рассмотрения. Смысл метода заключается в том, что мы находим в определённой области максимальный (или минимальный элемент) и помещаем его в начало исследуемой области, далее уменьшаем область поиска на 1 и повторяем те же действия, не имеет худшего случая, всегда O(n2).
Рисунок 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.3.4 Варианты заданий
Варианты 1 – 27 имеют пояснения к выполнению решений в [7].
1) Для заданного массива A размером n требуется выполнить проверку на упорядоченность. Результат присвоить переменной строкового типа (сделать вывод, каким именно образом упорядочен массив, если он окажется упорядоченным: по возрастанию, по убыванию, по неубыванию, по невозрастанию). Пояснения в [7], стр. 245.
2) Выполнить поиск заданного элемента в упорядоченном массиве. Пояснения в [7], стр. 246.
3) Требуется объединить два упорядоченных по возрастанию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N также упорядоченный по возрастанию. Пояснения в [7], стр. 247.
4) Требуется объединить два упорядоченных по убыванию массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N также упорядоченный по убыванию. Пояснения в [7], стр. 247.
5) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N, упорядоченный по возрастанию. [7], стр. 247.
6) Требуется объединить два массива A и B одного размера N (N – заданное натуральное число) в один массив размером 2N, упорядоченный по убыванию. Пояснения в [7], стр. 247.
7) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по возрастанию в один массив размером 2N, упорядоченный по неубыванию. [7], стр. 247; [9], стр. 75.
8) Требуется объединить два упорядоченных массива A и B одного размера N (N – заданное натуральное число) по убыванию в один массив размером 2N, упорядоченный по невозрастанию. Пояснения в [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 – заданное натуральное число. Сформировать массив С, элементы которого являются объединением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значение заносить только один раз.