1. Состав Dеlphi-проекта

Программа включает одну форму: главную, на которой и реализован интерфейс программы

На форме пристутствуют следующие компоненты:

2 компоненты TstringGrid: для отображения результатов работы программа в виде двух таблиц со значениями;

6 компонент TLabel: для отображения поясняющих надписей;

1 компонента TButton: для включения режима поиска;

1 компонента: TBitBtn: для закрытия формы и выхода из приложения;

4 компоненты TRadioButton: для выбора режима отображения кривых на компонентах Tchart (вывод графиков вместе и по отдельности);

4 компоненты TEdit: для ввода данных пользователем;

2 компоненты TChart: для отображения графиков функций;

2 компоненты TComboBox: для выбора графика, отображаемого на компоненте Tchart в режиме «показывать по отдельности»;

2 компоненты TPanel: для группировки компонент TRadioButton.

Программа содержит два модуля: главный модуль программы Project.dpr и модуль MainForm.pas, в котором непосредственно реализуются действия, связанные с поиском.

2. Статические данные и структуры

A: file of Word - файл из N элементов, интерпретируется как таблица, содержащая только целые ключи (N изменяется от Nmin до Nmax )(N*2 байта);

B : array of Word - вектор из К элементов, представляет собой набор аргументов поиска (K*2 байта);

arA : array of Word - массив для временного хранения данных в процедуре сортировки файла A (N*2 байта);

Nmin : Word – минимальное число элементов в таблице A (2 байта);

Nmax : Word – максимальное число элементов в таблице A (2 байта);

Step : Word – шаг изменения числа элементов в таблице A (2 байта);

K : Word - число элементов в векторе B (2 байта);

T, i: Word – счётчики (2 байта);

rnd : Word – переменная, содержащая случайное значение, генерируемое датчиком RANDOM случайных чисел из диапазона [0, 64000] (2 байта);

Fval : Word – значение текущего элемента файла A (2 байта);

SortA1, SortA2, SortAB : array [0..1, 1..4, 1..65535] of Word – значения текущего времени перед выполнением сотвуетствующего вида сортировки в цикле (2*4*65536*2 байта = 1048560 байт);

LinF1, LinF2, BinF, LinFAcc: array [0..1, 1..4, 1..65535] of Word значения текущего времени перед очередным циклом и после него в соответствующих видах поиска (2*4*65535*2 байта = 1048560 байт);

TSortA1, TSortA2, TSortAB array [1..65535] of Word – значения периодов времени, затраченного на соответствующий вид сортировки в цикле (65535*2 байта = 131070 байт);

TLinF1, TLinF2, TBinF, TLinFAcc: array [1..65535] of Word – значения периодов времени, затраченного на соответствующий вид поиска в цикле (65535*2 байта = 131070 байт);

Acc : array [1..3, 1..65535] of Word – массив, накапливающий запросы (3*65535*2 байта = 393210 байт).

3. Логические структуры данных

Логическая схема структуры файла A:

Количество элементов в файле N в процессе выполнения программы изменяется от Nmin до Nmax, т.е. создаётся файл из N=Nmin элементов, затем после необходимых процедур уничтожается и создаётся файл из

Nmin+1 элементов и так, пока N не достигнет значения Nmax

Логическая схема структуры вектора B

4. Алгоритмы обработки основных структур

procedure tform1.fill;

var

r : integer;

begin

rewrite(a);

for r:=1 to i do //наполнение файла

begin //случайными значениями

fval:=random(64000);

write(a, fval);

end;

end;

Данная процедура наполняет файл i значениями, сгенерированными датчиком Random.

Файл A после выполнения первой итерации.

Файл A после выполнения второй итерации.

Файл A после выполнения последней итерации.

procedure tform1.linfind; //линейный поиск

var

s1, s2 : word;

begin

for s1:=0 to k-1 do

for s2:=0 to i-1 do

begin

seek(a, s2);

read(a, fval);

if (b[s1]=fval) then exit;

end;

end;

Процедура перебирает значения из вектора В, сранивая их поэлементно со значениями из файла А.

Состояние вектора и файла при:

первой итерации второй итерации i-й итерации

1*i+1-й итерации 1*i+2-й итерации 1*i+3-й итерации

k*i+1-й итерации k *i+2-й итерации k*i+3-й итерации

procedure tform1.binfind; //двоичный поиск

var

s1, cou, cou1, cou2 : integer;

label

1;

begin

for s1:=0 to k-1 do

begin

cou1:=0;

cou2:=i-1;

while cou1<=cou2 do

begin

cou:=(cou2+cou1) div 2;

seek(a, cou);

read(a, fval);

if (fval=b[s1]) then goto 1

else if fval

else cou2:=cou-1;

end;

1 : end;

end;

Процедура перебирает значения из вектора В, сранивая их поэлементно со значениями из файла А (файл А должен быть предварительно отсортирован), причём делит файл А пополам и сравнивает значения. Если значение из вектора В больше значения из файла А, то таким же образом исследуется левая половина файла, в противном случае – правая и т.д.

Состояние вектора и файла при:

первой итерации

второй итерации

procedure tform1.linfindacc; //линейный поиск с накоплением

var

s1, s2, cou : word;

begin

cou:=1;

for s1:=0 to k-1 do

for s2:=0 to i-1 do

begin

seek(a, s2);

read(a, fval);

if (b[s1]=fval) then

begin

acc[1, cou]:=s2;

acc[2, cou]:=s1;

acc[3, cou]:=fval;

cou:=cou+1;

end;

end;

end;

Алгоритм процедуры аналогичен алгоритму процедуры tform1.linfind с той разницей, что при совпадении значения в векторе и файле в двухмерный массив аcc записываются индексы файла и вектора, а также совпавшее значение.

procedure tform1.sorta; //сортировка файла a

var

r, d : integer;

tmp, val : word;

begin

setlength(ara, i);

for r:=0 to i-1 do

begin

seek(a, r);

read(a, val);

ara[r]:=val;

end;

for r:=0 to i-2 do

for d:=r+1 to i-1 do

begin

if (ara[r]>ara[d]) then

begin

tmp:=ara[r];

ara[r]:=ara[d];

ara[d]:=tmp;

end;

end;

rewrite(a);

for r:=0 to i-1 do write(a, ara[r]);

end;

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

procedure tform1.sortb; //сортировка вектора b

var

r, d : integer;

tmp : word;

begin

for r:=0 to k-2 do

for d:=r+1 to k-1 do

begin

if (b[r]>b[d]) then

begin

tmp:=b[r];

b[r]:=b[d];

b[d]:=tmp;

end;

end;

end;

Алгоритм сортировки вектора аналогичен вышеописанному методу сортировки файла.

5 Руководство пользователя

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

1. Ввод необходимых данных.

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

В случае введения неверной информации программа выдаст соответствующее диалоговое окно:

а) при незаполнении одного из полей:

б) при введении в одно из полей символа(ов), не являющегося(ихся) цифрой(ами):

в) при введении в поле Nmin значения, превышающего значение в поле Nmax:

г) при введении неположительного числа(чисел) либо числа(чисел), превышающего(их) максимально допустимое значение - 65535:

2. Поиск и вычисление времени, затраченного на поиск и сортировку

Для включения режима поиска необходимо нажать кнопку с надписью «ПОИСК»

При верно введенных данных режим поиска успешно начнёт работу, о чём будет свидетельствовать отсутствие диалоговых окон после нажатия кнопки «ПОИСК». После окончания вышеуказанного процесса результаты будут представлены в таблицы 1 и 2, а также выведены в виде графиков соответствующих функций для дальнейшего анализа.

3. Анализ.

Как уже было сказано ранее, данные для анализа будут представлены в таблицах 1 и 2, а также в виде кривых.

Таблица 1 состоит из следующих граф:

• N (длина таблицы),

• t_ЛП1(N) – время первого линейного поиска,

• t_лп2(N) – время второго линейного поиска,

• t_ДП(N) – время двоичного поиска,

t_ЛП-М(N) – время поиска с накоплением запросов.

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

• N,

• t_лп2(N)+ t_сА(N), где t_СА(N) – время сортировки файла А,

• t_Дп(N)+ t_сА(N),

• t_лп-М(N)+ t_сА(N)+ t_сВ(N).

Справа от каждой таблицы изображены графики соответствующих функций, которые можно просматривать как вместе, так и по отдельности, для чего необходимо выбрать соответствующее положение кнопки(ок) RadioButton:

или так:

Для просмотра определённого графика необходимо выбрать соответствующее название в выпадающем списке справа от панели с кнопками переключения режима вывода графиков (при этом, конечно, должен быть включен режим «ПО ОТДЕЛЬНОСТИ»).

При удовлетворительных результатах можно перейти к завершению приложения, в противном случае же – ввести новые данные и начать новый поиск (см. п.1).

4. Выход из программы.

Для завершения приложения необходимо нажать на кнопку «ЗАКРЫТЬ» или на крестик в правом верхнем углу.

ЗАКЛЮЧЕНИЕ

Приложение (исходные тексты всех модулей)

Исходный текст модуля Project.dpr:

program Project;

uses

Forms,

MainForm in 'MainForm.pas' {Form1};

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.Run;

end.

Исходный текст модуля MainForm.pas:

unit MainForm;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Buttons, Grids,

Series;

type

TForm1 = class(TForm)

sgTb2: TStringGrid;

sgTb1: TStringGrid;

Label1: TLabel;

Label2: TLabel;

btFind: TButton;

btClose: TBitBtn;

rbTog1: TRadioButton;

rbEve1: TRadioButton;

cbSel1: TComboBox;

edNmin: TEdit;

edNmax: TEdit;

edLen: TEdit;

Label4: TLabel;

Chart1: TChart;

Series1: TLineSeries;

Series2: TLineSeries;

Series3: TLineSeries;

Series4: TLineSeries;

edStep: TEdit;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Chart2: TChart;

rbTog2: TRadioButton;

rbEve2: TRadioButton;

cbSel2: TComboBox;

Series5: TLineSeries;

Series6: TLineSeries;

Series7: TLineSeries;

Panel1: TPanel;

Panel2: TPanel;

procedure rbEve1Click(Sender: TObject);

procedure rbTog1Click(Sender: TObject);

procedure btFindClick(Sender: TObject);

procedure LinFind;

procedure BinFind;

procedure LinFindAcc;

procedure SortA;

procedure SortB;

procedure Verify;