Основы дискретной математики (стр. 6 из 23)
readln (a[i]);
end;
writeln; assign (fl, 'datl.dat'); rewrite(fl);
assign (f2, 'dat2.dat'); rewrite(f2);
{формированиепоследовательногофайла}
for i:=1 to N do begin writeln (fl, a[i]);
end;
{алгоритм сортировки с использованием вспомогательного файла}
for k:=1 to (n div 2) do
begin {извлечение из исходного файла и запись во вспомогательный}
reset(fl); readln (fl, x);
for i:=2 to n do begin readln (fl, y);
if x>y then writeln (f2, y) else begin writeln (f2, x); x:=y;
end;
end;
writeln (f2, x);
{извлечение из вспомогательного файла и запись в исходный}
rewrite(fl); reset(f2); readln (f2, x);
for i:=2 to n do begin readln (f2, y);
if x>y then writeln (fl, y) else begin writeln (fl, x); x:=y;
end;
end;
writeln (fl, x); rewrite(f2); end;
(выводрезультата)
reset(fl);
for i:=1 to N do readln (fl, a[i]);
for i:=1 to N do begin write (a[i], ' ');
end;
close(fl); close(f2); readln;
end.
По сути можно в программе обойтись без массива а [1..n]. В качестве упражнения попытайтесь создать программу, в которой не используются массивы.
Многие методы сортировки последовательных файлов основаны на процедуре слияния, означающей объединение двух (или более) последовательностей в одну, упорядоченную с помощью повторяющегося выбора элементов (доступных в данный момент). В дальнейшем (чтобы не осуществлять многократного обращения к внешней памяти), будем рассматривать вместо файла массив данных, обращение к которому можно осуществлять строго последовательно. В этом смысле массив представляется как последовательность элементов, имеющая два конца, с которых можно считывать данные. При слиянии можно брать элементы с двух концов массива, что эквивалентно считыванию элементов из двух входных файлов.
Идея слияния заключается в том, что исходная последовательность разбивается на две половины, которые сливаются вновь в одну упорядоченными парами, образованными двумя элементами, последовательно извлекаемыми из этих двух подпоследовательностей. Вновь повторяем деление и слияние, но упорядочивая пары, затем четверки и т. д. Для реализации подобного алгоритма необходимы два массива, которые поочередно (как и в предыдущем примере) меняются ролями в качестве исходного и вспомогательного.
Если объединить эти два массива в один, разумеется, двойного размера, то программа упрощается. Пусть индексы 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 Содержание отчёта по практической работе
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.
Задание: заданы два одномерных массива А и В, содержащие по n элементов каждый. Объединить эти два массива в один, исключив повторяющиеся элементы. Считать, что массивы А и В отсортированы по убыванию.