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

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(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.

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