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

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

редно (как и в предыдущем примере) меняются ролями в качестве исходного и вспомогательного.

Если объединить эти два массива в один, разумеется, двойного размера, то программа упрощается. Пусть индексы i и j фиксируют два входных элемента с концов исходного массива, k и L – два выходных, соответствующих концам вспомогательного массива. Направлением пересылки (сменой ролей массивов) удобно управлять с помощью булевской переменной, которая меняет свое значение после каждого прохода, когда элементы a1…, an движутся на место ani….a2n и наоборот. Необходимо еще учесть изменяющийся на каждом проходе размер объединяемых упорядоченных групп элементов. Перед каждым последующим проходом размер удваивается. Если считать, что количество элементов в исходной последовательности не является степенью двойки (для процедуры разделения это существенно), то необходимо придумать стратегию разбиения на группы, размеры которых q и r могут не совпадать с ведущим размером очередного прохода. В окончательном виде алгоритм сортировки слиянием представлен ниже.

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;

 Скачать реферат