Основы дискретной математики

program sortirovka__faila_2;

{сортировка последовательного файла слиянием}

const N=8;

type item= integer;

var a: array [1..2*n] of item;

i, j, k, L, t, h, m, p, q, r: integer; f: boolean;

begin

{задание искомого массива}

for i:=1 to N do begin write ('введи элемент а [', i, '] = ');

readln (a[i]);

end;

writeln;

{сортировка слиянием}

f:=true; p:=1;

repeat

h:=1; m:=n; if f then begin

i:=1; j:=n; k:=n+1; L:=2*n

end

else begin k:=1; L:=n; i:=n+1; j:=2*n

end;

repeat

if m>=p then q:=p else q:=m; m:=m-q;

if m>=p then r:=p else r:=m; m:=m-r;

while (q< >0) and (r<>0) do

begin

if a[i}<a[j] then

begin a[k]:=a[i]; k:=k+h; i:=i+1; q:=q_1

end

else

begin a[k]:=a[j]; k:=k+h; j:=j_1; r:=r_1

end;

end;

while r>0 do

begin a[k]:=a[j]; k:=k+h; j:=j_1; r:=r_1;

end;

while q>0 do begin

a[k]:=a[i]; k: - k+h; i:=i+1; q:=q_1;

end;

h:=-h; t:=k; k:=L; L:=t;

until m=0;

f:=not(f); p:=2*p;

until p>=n;

if not(f) then for i:=1 to n do a[i]:=a [i+n];

{вывод результата}

for i:=1 to N do begin write (a[i], ' ');

end;

readln;

end.

Рассмотренные два предыдущих примера иллюстрируют большие проблемы сортировки внешних файлов, если в них часты изменения элементов, например, удаления, добавления, корректировки существующих.

В подобных ситуациях эффективными становятся алгоритмы, в которых обрабатываемые элементы представляются в виде структур данных, удобных для поиска и сортировки. В качестве структур данных можно отметить, в частности, линейные списки, очереди, стеки, деревья и т. п. О них было рассказано в предыдущем разделе.

1.3 Практическая часть

1.3.1 Содержание отчёта по практической работе

1 Задание по варианту.

2 Теоретическая часть (краткое описание используемого метода и необходимые пояснения для понимания функционирования приложения на Delphi).

3 Блок-схема для процедуры, реализующей основной алгоритм.

4 Код программы.

5 Результаты расчёта.

Примечание: а) подбор исходных данных выполнить самостоятельно; б) если в варианте не указан метод, то выбрать наиболее подходящий для решения поставленной задачи (предварительно согласовать с преподавателем).

1.3.2 Приложение на 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.

1.3.3 Пример выполнения

Задание: заданы два одномерных массива А и В, содержащие по n элементов каждый. Объединить эти два массива в один, исключив повторяющиеся элементы. Считать, что массивы А и В отсортированы по убыванию.

Теоретическое описание метода

Метод пузырька, как таковой, не требует глубокого рассмотрения. Смысл метода заключается в том, что мы находим в определённой области максимальный (или минимальный элемент) и помещаем его в начало исследуемой области, далее уменьшаем область поиска на 1 и повторяем те же действия, не имеет худшего случая, всегда O(n²).

Рисунок 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 - заданное натуральное число. Сформировать массив С, элементы которого являются объединением указанных массивов, и расположить его элементы по неубыванию. Одинаковые значение заносить только один раз.

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) Ввести числовую матрицу размером NxM (N, M заданы). Найти максимальный элемент среди расположенных в тех строках матрицы, которые являются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить, что такого элемента нет.

1.4 Вопросы для самопроверки

1) Какими свойствами обладает отношение частичного порядка? Приведите примеры этого отношения.

2) Дайте определение отношения линейного порядка.

3) Сформулируйте постановку задачи сортировки.

4) В чём заключается преимущество отсортированных (упорядоченных) данных?

5) Как рассматривается задача сортировки с точки зрения программирования?

6) От каких факторов зависит эффективность алгоритма сортировки?

7) Перечислите наиболее часто используемые на практике методы поиска и сортировки.

8) Каким образом могут быть представлены данные при поиске и сортировке?

9) Перечислите основные операции при работе с данными.

10) В чём заключается алгоритм линейного поиска?

11) В чём заключается алгоритм бинарного поиска?

12) Опишите кратко поиск в бинарных деревьях.

13) Какие функции используются при оценке времени исполнения алгоритма?

14) В чём заключается метод сортировки вставками?

15) В чём заключается метод сортировки с помощью включения, прямого включения?

16) В чём заключается метод Шелла?

17) Опишите сортировку с помощью обменов.

18) Опишите алгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).

Практическая работа № 2. Представление множеств в компьютере

Цель работы: изучение представлений множеств и отношений в программах, алгоритмов с использованием множеств; представление множеств характеристическими векторами и их практическая реализация.

2.1 Теоретическая часть

2.1.1 Множества и операции над ними

Множество - это совокупность объектов, называемых элементами множества. Например:

* {Эссекс, Йоркшир, Девон};

* {2, 3, 5, 7, 11}.

В этом примере элементы каждого множества заключены в фигурные скобки. Чтобы обеспечить возможность ссылок, мы будем обозначать множества прописными латинскими буквами. Например,

S = {3, 2, 11, 5, 7} - множество, содержащее целые числа. Заметим, что множество S совпадает с одним из множеств, выписанных выше, поскольку порядок, в котором записываются элементы множества, значения не имеет.

В общем случае запись аS означает, что объект а - элемент множества S. Часто говорят, что а принадлежит множеству S. Если объект а не принадлежит S, то пишут: а S.

В современных языках программирования требуется, чтобы переменные объявлялись как принадлежащие к определенному типу данных. Тип данных представляет собой множество объектов со списком стандартных операций над ними. Определение типа переменных равносильно указанию множества, из которого переменным присваиваются значения [22].

Существует несколько способов конструирования нового множества из двух данных. Опишем коротко эти операции на множествах. Прежде всего, отметим, что все элементы некоторых множеств принадлежали другим большим множествам. Например, все элементы множества С = {0, 1, 4, 9, 16,…} содержатся в множестве

Z = {0, ±1, ±2, ±3,…}.

Рисунок 2.1 - Диаграмма Венна подмножества А S

Объединением двух множеств А и В называется множество

АВ = {х: х А или х В}.

Оно состоит из тех элементов, которые принадлежат либо множеству A, либо множеству В, а возможно и обоим сразу. Диаграмма Венна объединения показана на рисунке 2.2.

Пересечением двух множеств А и В называется множество

А В = {х: х А и х В}.

Оно состоит из элементов, которые принадлежат как множеству А, так и множеству B. Диаграмма Венна пересечения приведена на рисунке 2.3.

Рисунок 2.2 - Диаграмма Венна Рисунок 2.3 - Диаграмма Венна для объединения множеств для пересечения множеств

Дополнением множества В до множества А называется

A\В = {х: х А и x В}.

Дополнение А \ В состоит из всех элементов множества А, которые не принадлежат В (см. рисунок 2.4). Если мы оперируем подмножествами некоего большого множества U, мы называем U универсальным множеством для данной задачи. На наших диаграммах Венна прямоугольник как раз и символизирует это универсальное множество. Для подмножества А универсального множества U можно рассматривать дополнение А до U, т. е. U \ А. Поскольку в каждой конкретной задаче универсальное множество фиксировано, множество U \ А обычно обозначают и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U можно записать

= {х: не (х А)} = {х: х A}.

Диаграмма Венна дополнения изображена на рисунке 2.5.

Рисунок 2.4 - Диаграмма Венна разности А \ В	Рисунок 2.5 - Диаграмма Венна дополнения

Симметрической разностью двух множеств А и В называют множество А Д В = {х: (х А и х В) или (х В и х А)}.

Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна, иллюстрирующая симметрическую разность, начерчена на рисунке 2.6.



Рисунок 2.6 - Диаграмма Венна симметрической разности А Д В

2.1.2 Представление множеств и отношений в программах

В этом параграфе рассматривается представление множеств в программах. Термин «представление» (еще употребляют термин «реализация») применительно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) - значит, описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции. Предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций [5].

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других - другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.

Множества и задачи информационного поиска

Наиболее продуктивный подход к разработке эффективного алгоритма для решения любой задачи - изучить ее сущность. Довольно часто задачу можно сформулировать на языке теории множеств, относящейся к фундаментальным разделам математики. В этом случае алгоритм ее решения можно изложить в терминах основных операций над множествами. К таким задачам относятся и задачи информационного поиска, в которых решаются проблемы, связанные с линейно упорядоченными множествами [1].

Многие задачи, встречающиеся на практике, сводятся к одной или нескольким подзадачам, которые можно абстрактно сформулировать как последовательность основных команд, выполняемых на некоторой базе данных (универсальном множестве элементов). Например, выполнение последовательности команд, состоящих из операций поиск, вставка, удаление и минимум, составляет существенную часть задач поиска. Об этих и других подобных командах и пойдет речь ниже [12].

Рассмотрим несколько основных операций над множествами, типичных для задач информационного поиска.

* Поиск (а; S) определяет, принадлежит ли элемент а множеству S;

если а S, результат операции - ответ «да»; в противном случае -

ответ «нет».

* Вставка (а, S) добавляет элемент а в множество S, то есть заменяет S на S U {а}.

* Алгоритм правильного обхода(S) печатает элементы множества S с

соблюдением порядка.

* Удаление (a, S) удаляет элемент а из множества S, то есть заменяет S на S \ {а}.

* Объединение (S1, S2, S3) объединяет множества S1 и S2, т. е. строит

множество S3 = S1 U S2.

* Минимум (S) выдает наименьший элемент множества S.

Следующая операция - операция минимум(S). Для нахождения наименьшего элемента в двоичном дереве поиска Т строится путь v₀, v_i, …, v_p, где v₀-корень дерева Т, v_i - левый сын вершины v_i-1 (i= 1,2,…, р), а у вершины v_p левый сын отсутствует. Ключ вершины v_p, и является наименьшим элементом в дереве Т. В некоторых задачах полезно иметь указатель на вершину v_y, чтобы обеспечить доступ к наименьшему элементу за постоянное время.

Алгоритм выполнения операции минимум(S) использует рекурсивную процедуру левый сын(v), определяющую левого сына вершины v. Алгоритм и процедура выглядят следующим образом.

Input

двоичное дерево поиска Т для множества S

begin

if T = 0 then output «дерево пусто»;

else

вызвать процедуру левый сын(r)

(здесь r - корень дерева Т);

минимум:=1 (v), где v - возврат процедуры левый сын;

end

Output ответ «дерево пусто», если Т не содержит вершин;

минимум - наименьший элемент дерева Т в противном случае.

Procedure левый сын (v).

begin

if v имеет левого сына w then return левый сын (w)

else return v

end

Пример 2.1 Проследите работу алгоритма минимум на дереве поиска, изображенном на рисунке 2.7.

Решение. Дерево Т не пусто, следовательно, вызывается процедура левый сын (1).

Вершина 1 имеет левого сына - вершину 2, значит, вызывается процедура левый сын (2).

Вершина 2 имеет левого сына вершину 4, значит, вызывается процедура левый сын (4).

Вершина 4 не имеет левого сына, поэтому вершина 4 и будет возвратом процедуры левый сын.

Ключом вершины 4 является слово begin, следовательно, наименьшим элементом дерева Т является значение минимум= begin.

Рисунок 2.7 - Дерево поиска минимума S

Реализовать операцию удаление (a, S) на основе бинарных поисковых деревьев тоже просто. Допустим, что элемент а, подлежащий удалению, расположен в вершине v. Возможны три случая:

* вершина v является листом; в этом случае v просто удаляется

из дерева;

* у вершины v в точности один сын; в этом случае объявляем отца вершины v отцом сына вершины v, удаляя тем самым v из дерева (если v - корень, то его сына делаем новым корнем);

* у вершины v два сына; в этом случае находим в левом поддереве вершины v наибольший элемент b, рекурсивно удаляем из этого поддерева вершину, содержащую b, и присваиваем вершине v ключ b. (Заметим, что среди элементов, меньших а, элемент b будет наибольшим элементом дерева. Кроме того, вершина, содержащая b, может быть или листом, являющимся чьим-то правым сыном, или иметь только левое поддерево.)

Ясно, что до выполнения операции удаление (а, S) необходимо проверить, не является ли дерево пустым и содержится ли элемент а в множестве S. Для этого придется выполнить операцию поиск (а, S), причем, и в случае положительного ответа необходимо выдать кроме ответа «да» и номер вершины, ключ которой совпадает с a (далее ключ вершины v будем обозначать через l(v)). Кроме этого, для реализации операции удаление (a, S) требуется знать и номер вершины w, являющейся отцом вершины v. Саму же рекурсивную процедуру удаление (а, S) можно реализовать так, как показано ниже.

Procedure удаление (а, S)

begin

if v - лист then удалить v из Т

else

(2) if v имеет только левого или только

правого сына u then

(3) if v имеет отца w then

назначить и сыном w

else

сделать u корнем дерева,

присвоив ему номер v

else

найти в левом поддереве v наибольший элемент b, содержащийся в вершине у;

(6) return удаление (b, S);

(7) l(v):=b;

end

Пример 2.2 Проследите за работой алгоритма удаление (а, S) для двоичного дерева поиска S, изображенного на рисунке 2.7, если a - это слово «if».

Решение. Слово «if» расположено в корне с номером 1, у которого два сына (вершины 2 и 3), поэтому выполняем строку (5) алгоритма. Наибольшее слово, меньшее «if» (лексикографически), расположенное в левом поддереве корня и находящееся в вершине 2, - это end. Вызываем процедуру удаление (end, S).

Условие строки (2) алгоритма выполняется, так как вершина 2 с ключом end имеет только левого сына. Условие строки (3) не выполняется, так как удаляемая вершина является корнем. Поэтому переходим к строке (4): делаем вершину 2 корнем, сыновьями которого становятся вершины 4 (левым) и 3 (правым). Работа процедуры удаление (end, S) закончена.

Продолжаем выполнение алгоритма (выполняем строку (7)): полагаем ключ вершины 1 равным «end» (l (I):=end).

Полученное в результате дерево изображено на рисунке 2.8.

Заметим, что при работе рассмотренных алгоритмов необходимо находить сыновей, отца и ключ заданной вершины двоичного дерева поиска. Это можно сделать довольно просто, если дерево в памяти компьютера хранится в виде трех массивов: LEFTSON, RIGHTSON и KEY. Эти массивы устроены следующим образом:

LEFTSON (i) =	v, если v - левый сын вершины i *, если у вершины i левого сына нет
RIGHTSONM (i) =	v, если v - правый сын вершины i *, если у вершины i правого сына нет

key(i) = l(i) - ключ вершины i.

Рисунок 2.8 - Результат работы алгоритма удаление (а, S) для двоичного дерева поиска S

Например, бинарное поисковое дерево, изображенное на рисунке 2.7, может быть представлено в виде таблицы 2.1.

Таблица 2.1 - Представление бинарного поискового дерева в виде таблицы

I	LEFTSON	RIGHTSON	KEY
1	2	3	if
2	4	*	end
3	*	6	then
4	*	5	begin
5	*	*	else
6	*	*	while

Правила поиска сыновей и ключа заданной вершины следуют из определения массивов. Определение отца заданной вершины состоит в нахождении строки массивов LEFTSON или RIGHTSON, в которой находится номер заданной вершины. Например, отцом вершины 4 является вершина 2, так как число 4 находится во второй строке массива LEFTSON.

Объединение множеств

Обратимся теперь к объединению множеств, то есть к операции объединение (S1, S2, S3).

Если множества S1 и S2 линейно упорядочены, то естественно требовать такого порядка и от их объединения. Один из возможных способов объединения состоит в последовательном выполнении описанной выше операции вставка для добавления каждого элемента одного множества в другое. При этом, очевидно, операцию вставка предпочтительнее выполнять над элементами меньшего множества с целью сокращения времени на объединение. Отметим, что такой способ работы подходит как для непересекающихся, так и для пересекающихся множеств.

Во многих задачах объединяются непересекающиеся множества. Это упрощает процесс, так как исчезает необходимость каждый раз проверять, содержится ли добавляемый элемент в множестве, либо удалять повторяющиеся экземпляры одного и того же элемента из S3.

Процедура объединения непересекающихся множеств применяется, например, при построении минимального остовного дерева в данном нагруженном графе.

Рассмотрим алгоритм объединения непересекающихся множеств на основе списков. Будем считать, что элементы объединяемых множеств пронумерованы натуральными числами 1,2,…. n. Кроме того, предположим, что имена множеств - также натуральные числа. Это не ограничивает общности, поскольку имена множеств можно просто пронумеровать натуральными числами.

Представим рассматриваемые множества в виде совокупности линейных связанных списков. Такую структуру данных можно организовать следующим образом.

Сформируем два массива R и next размерности n, в которых R(i) - имя множества, содержащего элемент i, a next(i) указывает номер следующего элемента массива R, принадлежащего тому же множеству, что и элемент i. Если i - последний элемент какого-то множества, то положим next(i) = 0. Для указателей на первые элементы каждого множества будем использовать массив list, число элементов которого равно числу рассматриваемых в задаче множеств, и элемент которого list(j) содержит номер первого элемента множества с именем j в массиве R.

Кроме того, сформируем массив size, каждый элемент которого size(j) содержит количество элементов множества с именем j.

Будем различать внутренние имена множеств, содержащиеся в массиве к, и внешние имена, получаемые множествами в результате выполнения операции объединение. Соответствие между внутренними и внешними именами множеств можно установить с помощью массивов Ехт-NAME и INT-NAME. Элемент массива EXT-NAME(j) содержит внешнее имя множества, внутреннее имя которого есть j, а INT-NAME(k) - внутреннее имя множества, внешнее имя которого есть к.

Пример 2.3 Используя только что определенные массивы, опишите множества {1,3,5,7}, {2,4.8}, {6} с внешними именами 1, 2, 3 и внутренними именами 2, 3, 1 соответственно.

Решение. Прежде всего, отметим, что общее количество элементов всех множеств равно восьми. Поэтому размерность массивов R и next будет n = 8. Кроме того, напомним, что номера элементов массивов list, SIZE, Ехт-NAME и значения элементов массива R - это внутренние имена множеств, а массива INT-NAME внешние.

Алгоритм выполнения операции объединение (S1, S2, S3) состоит в добавлении к списку элементов большего из множеств S1 и S2 элементов меньшего множества и присвоение полученному множеству внешнего имени S3. При этом вычисляется также размер построенного множества S3.

Объединение (i, j, к)

Input

i, j - внешние имена объединяемых множеств

(пусть размер i меньше размера j);

массивы R, NEXT, LIST, SIZE, ЕХТ-NAME, INT-NAME;

begin

A:=INT-NAME(i);

B:=INT-NAME(j);

element:=LIST(A);

while element <> 0 do

begin

R(element):=B;

last:=element;

element:=NEXT(element)

end

NEXT(last):=LIST(B);

LIST(B):=LIST(A);

SIZE(B):=SIZE(B) + SIZE(A);

INT-NAME(K):=B;

EXT-NAME(B):=k

End

Объединение множеств i, j с внешним именем k.

В процессе работы алгоритм совершает следующие действия:

1) определяет внутренние имена множеств i и j;

2) определяет начало списка элементов меньшего множества;

3) просматривает список элементов меньшего множества и изменяет соответствующие элементы массива R на внутреннее имя большего множества;

4) объединяет множества путем подстановки меньшего множества перед большим;

5) присваивает новому множеству внешнее имя k.

Заметим, что время выполнения операции объединения двух множеств с помощью рассмотренного алгоритма пропорционально мощности меньшего множества.

2.1.3 Алгоритмы генерации множеств

Реализация операций над подмножествами заданного универсума U

Пусть универсум U - конечный, и число элементов в нем не превосходит разрядности ЭВМ: мощность |U| < n. Элементы универсума нумеруются: U = {u₁,…, u_n}. Подмножество А универсума U представляется кодом (машинным словом или битовой шкалой) С, в котором:

где С(i) - это i_й разряд кода С.

Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно.

Если мощность универсума превосходит размер машинного слова, но не очень велика, то для представления множеств используются массивы битовых шкал. В этом случае операции над множествами реализуются с помощью циклов по элементам массива [23].

Генерация всех подмножеств универсума

Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причем число 2k - 1 представляется кодом, содержащим k единиц. Таким образом, число 0 является представлением пустого множества 0, число 1 является представлением подмножества, состоящего из первого элемента, и т. д. Следующий тривиальный алгоритм перечисляет все подмножества n_элементного множества (представлен в паскале-подобном коде, описание в [23]).

Алгоритм 1.1: Алгоритм генерации всех подмножеств n_элементного множества

Вход: n 0 - мощность множества

Выход: последовательность кодов подмножеств i

for i from 0 to 2n - 1 do

yield i

end for

Обоснование: Алгоритм выдает 2n различных целых чисел, следовательно, 2n различных кодов.

С увеличением числа n увеличивается количество двоичных разрядов, необходимых для его представления. Самое большое (из генерируемых) число 2n_1 требует для своего представления ровно n разрядов. Таким образом, все подмножества генерируются, причем ровно по одному разу.

Во многих переборных задачах требуется рассмотреть все подмножества некоторого множества и найти среди них то, которое удовлетворяет заданному условию. При этом проверка условия часто может быть весьма трудоемкой и зависеть от состава элементов очередного рассматриваемого подмножества. В частности, если очередное рассматриваемое подмножество незначительно отличается по набору элементов от предыдущего, то иногда можно воспользоваться результатами оценки элементов, которые рассматривались на предыдущем шаге перебора. В таком случае, если перебирать множества в определенном порядке, можно значительно ускорить работу переборного алгоритма. [5]