Сортировка массива методом Шелла, поиск методом Фибоначчи

Текст задания :
Ввести список чисел из файла, затем сортировать их методом Шелла, а после поиск по списку методом Фибоначчи.
Решение :
Создаем новый VCL проект. Бросаем на форму компоненты
TGroupBox;TGroupBox;TMemo;TMemo;TButton;TButton;TLabel;TEdit;TButton; TLabel; TEdit;
Получится должно что-то вроде этого :
Снимок

Сортировку методом Шелла реализуем в процедуре Sort_Shell :
[cc lang=»delphi» tab_size=»2″ line_numbers=»false» no_links=»false»]
procedure Sort_Shell(var a: array of integer);
var
bis, i, j, k: LongInt;
h: Word;
begin
bis := High(a);
k := bis shr 1; // div 2
while k > 0 do
begin
for i := 0 to bis — k do
begin
j := i;
while (j >= 0) and (a[j] > a[j + k]) do
begin
h := a[j];
a[j] := a[j + k];
a[j + k] := h;
if j > k then
Dec(j, k)
else
j := 0;
end; // {end while]
end; // { end for}
k := k shr 1; // div 2
end; // {end while}
end;
[/cc]

Поиск методом Фибоначчи реализуем в виде функции Fib :
[cc lang=»delphi» tab_size=»2″ line_numbers=»false» no_links=»false»]
function Fib(N: integer): integer;
var
F1, F2: integer;
begin
if (N = 0) or (N = 1) then
Fib := N
else if N >= 2 then
begin
F1 := Fib(N — 1);
F2 := Fib(N — 2);
Fib := F1 + F2
end
end;
[/cc]

Кнопку «Вставка массива» запрограммируем следующим образом :

[cc lang=»delphi» tab_size=»2″ line_numbers=»false» no_links=»false»]
procedure TForm1.Button1Click(Sender: TObject);
begin
AssignFile(F1, ‘laba1.TXT’);
Reset(F1);
N := 0;
Memo1.Text := ‘ ‘;
while not Eof(F1) do
begin
N := N + 1;
Readln(F1, x[N]);
Memo1.Text := Memo1.Text + IntToStr(x[N]) + chr(13) + chr(10);
end;
CloseFile(F1);
end;
[/cc]
Кнопку «Сортировка» запрограммируем следующим образом :

[cc lang=»delphi» tab_size=»2″ line_numbers=»false» no_links=»false»]
procedure TForm1.Button2Click(Sender: TObject);
var
i: integer;
begin
Sort_Shell(x);
Memo2.Clear;
for i := 1 to 20 do
Memo2.Text := Memo2.Text + ‘ ‘ + IntToStr(x[i]) + chr(13) + chr(10);
end;
[/cc]

Кнопку «Поиск» запрограммируем следующим образом :
[cc lang=»delphi» tab_size=»2″ line_numbers=»false» no_links=»false»]
procedure TForm1.Button3Click(Sender: TObject);
var
Key: integer; { Искомый элемент }
Search: 0 .. 20; { Индекс найденного элемента }
{ 0, если элемент не найден }
Mid: integer; { Индекс внутреннего элемента }
j: integer;
F1, F2, t: integer;
Finish: boolean;
begin
Key := StrToInt(Edit1.Text);
j := 1;
While Fib(j) < N + 1 do
j := j + 1;
Mid := N — Fib(j — 2) + 1;
F1 := Fib(j — 2);
F2 := Fib(j — 3);
Finish := FALSE;
While (Key <> x[Mid]) AND (Finish = FALSE) do
If (Mid <= 0) OR (Key > x[Mid]) then
If F1 = 1 then
Finish := TRUE
else
begin
Mid := Mid + F2;
F1 := F1 — F2;
F2 := F2 — F1
end
else If F2 = 0 then
Finish := TRUE
else
begin
Mid := Mid — F2;
t := F1 — F2;
F1 := F2;
F2 := t
end;
If Finish then
Search := 0
else
Search := Mid;
Edit2.Text := IntToStr(Search);
end;
[/cc]
Добавим глобальные переменные, чтобы раздел выглядел вот так :
[cc lang=»delphi» tab_size=»2″ line_numbers=»false» no_links=»false»]
var
Form1: TForm1;
N: integer;
x: array [1 .. 20] of integer; // массив
F1: TextFile; // файл
[/cc]
Если все шаги проделаны верно, положите рядом с .exe файлом нашей программы текстовый файл с именем laba1.TXT.
Который должен содержать список чисел для нашего массива.

Запустите программу и проверьте,что все правильно работает.
Снимок

Нашли ошибку в тексте?

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *