Поиск минимального (максимального) элемента массива в Delphi

Листинг . Поиск минимального элемента массива

 

01.unit lookmin_;
02.interface
03.uses
04.Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
05.Dialogs, StdCtrls, Grids;
06.type
07.TForm1 = classTForm1
08.Label1: TLabel;
09.Button1: TButton;
10.Label2: TLabel;
11.StringGridl: TStringGrid;
12.procedure ButtonlClickfSender: TObject);
13.private
14.{Private declarations }
15.public
16.{ Public declarations }
17.end;
18.var
19.Forml: TForml;
20.implementation
21.{$R *.DFM}
22.procedure TForffll.ButtonlClick(Sender: TObjectl;
23.const
24.SIZE=5;
25.var
26.s:array[l. .SIZE]of integer// массив целых
27.utin:integer// номер минимального элемента массива
28.i:integer// номер элемента, сравниваемого с минимальным
29.begin
30.// ввод массива
31.for i:=l to SIZE do
32.a:=StrToInt(StringGridl.Cells[i-1,0]);
33.// поиск минимального элемента
34.min:=l; // пусть первый элемент минимальный
35.for i:-2 to SIZE do
36.if a(i]< a[min]then min:=i;
37.// вывод результате
38.label2.caption: = 'Минимальный элемент массива:'+IntToStr(afmin))+#13+'Номер элемента:'+IntToStr(min);
39.endend.

 

На рис. 5,8 приведен вид диалогового окна приложения после щелчка на кнопке Поиск.

 

Поиск в массиве заданного элемента: Метод бинарного поиска

 

На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту, массив данных о погоде — по датам наблюдений. В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых — метод бинарного поиска. Пусть есть упорядоченный по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец). {replace on}

Метод (алгоритм) бинарного поиска реализуется следующим образом:

  1. Сначала образец сравнивается со средним (по номеру) элементом массива (рис. 5.10, а). 
  • Если образец равен среднему элементу, то задача решена.
  • Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+i и niz), и за новое значение verb принимается sred+i, а значение niz не меняется (рис. 5.10, 6),
  • Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-i), и за новое значение niz принимается sred-i, а значение verh не меняется (рис. 5.10, в).

После того как определена часть массива, в которой может находиться
искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое
значение sred и поиск продолжается.

          2.После того как определена часть массива, в которой может находитьсяискомый элемент, по формуле (niz-verh) /2+verh вычисляется новоезначение sred и поиск продолжается.

Алгоритм бинарного поиска, блок-схема которого представлена на рис. 5.П, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение verb больше, чем niz. Вид диалогового окна программы Бинарный поиск в массиве приведен на рис. 5.12. Поле метки Labels используется для вывода результатов поиска и протокола поиска. Протокол поиска выводится, если установлен флажок выводить протокол. Протокол содержит значения переменных verh, niz, sred. Эта информация, выводимая во время поиска, полезна для понимания сути алгоритма.

 

В форме приложения появился новый компонент, который до этого момента в программах не использовался, — флажок (компонент CheckBox). Значок компонента CheckBox находится на вкладке Standard (рис. 5.13). Добавляется к форме он точно так же, как и другие компоненты.

 

После того как компонент checkBox будет добавлен к форме, а добавляется он обычным образом, нужно установить значения его свойств в соответствии с табл. 5.6.

В листинге 5.8 приведен текст процедуры обработки события onclick для командной кнопки Поиск (Buttoni). Процедура вводит значения элементов массива и образец, затем, используя алгоритм бинарного поиска, проверяет, содержит ли массив элемент, равный образцу. Кроме того, переменная n (число сравнений с образцом) позволяет оценить эффективность алгоритма бинарного поиска по сравнению с поиском методом простого перебора. При вычислении номера среднего элемента используется функция Trunc, которая округляет до ближайшего целого и преобразует к типу integer выражение, полученное в качестве аргумента. Необходимость использования trunc объясняется тем, что выражение (niz-verh) /2 -- дробного типа, переменная sred — целого, а переменной целого типа присвоить дробное значение нельзя (компилятор выдаст сообщение об ошибке).

Обратите внимание на процедуры обработки события опкеургезз для компонентов stringGridl и Editi- Первая из них обеспечивает перемещение курсора в следующую ячейку таблицы или в поле Editi (из последней ячейки) в результате нажатия клавиши , вторая — активизирует командную кнопку Поиск также в результате нажатия клавиши .

Листинг 5.8. Бинарный поиск в массиве

 

01.unit b_found_;
02.interface
03.uses
04.Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
05.Dialogs, StdCtrls, Grids;
06.type
07.TForml = class(TForm)
08.Labell: TLabel;
09.Label2: TLabel;
10.Buttonl: TButton;
11.LabelS; TLabel;
12.CheekBoxl: TCheckBox;
13.StringGridl: TStringGrid;
14.Editi; TEdit;
15.procedure ButtonlClick(Sender: TObject);
16.procedure StringGricllKeyPress (Sendee: TObject; var Key: Char);
17.procedure EditlKeyPress(Sender: TObject; var Key; Char);
18.private
19.{ Private declarations }
20.public
21.{Public declarations }
22.end;
23.var
24.Forml: TForml;
25.implementation
26.{$R*.dfm}
27.{ Бинарный поиск в массиве }
28.procedure TForml.ButtonlClicklSender: TObject) ;
29.const
30.SIZE=10;
31.var
32.a:array [1. .SIZE] of integer{ массив }
33.obr:integer{ образец для поиска}
34.verh:integer{ верхняя граница поиска i
35.niz: integer; / нижняя граница поиска )
36.sred:integer; f номер среднего элемента }
37.found:boolean; / TRUE — совладение образца с элементом массива I
38.n: integer{ число сравнений с образцом )
39.i: integer;
40.begin
41.// ввод массива и образца
42.for i:=l to SIZE do
43.a :=StrToInt(StringGridl. Cells [i-1, 0]) ;
44.obr := StrToInt(Editl.textl;
45.// поиск
46.verh:=l;
47.found :=FALSE;
48.Iabel3. caption:=' ' ;
49.if checkBoxl. State = cbChecked
50.then Label3. caption: = 'verh4-#9+'niz 49' sred413;
51.// бинарный поиск в массиве
52.repeat
53.sred:=Trunc"l (niz-verh}/2]+verh;
54.if Che ckBox 1 . Checked
55.then Labels. caption:=label3. caption+IntToStr(verh) + #9
56.+IntToStr(niz) + #9
57.+lntToStr(sred) + #13;
58.n:=n+l;
59.if a[sred] = obr
60.then found:=TRUE
61.else
62.if obr < a[sred]
63.then niz:=sred-l
64.else verh:=sred+l;
65.until (verb > niz) or found;
66.if found
67.then label3.caption:=labe!3.caption
68.+'Совпадение с элементом номер '•f intToStr [sred)+#13'Сравнений ' + IntToStrln)
69.else Iabel3.caption:=label3.caption+'Образец в массиве не найден.1;
70.end;
71.// нажaтие клавиши в ячейке StringGrid
72.procedure TForml.StringGridlKeyPress(Sender: TObject; var Key: Char);
73.begin
74.if Key = #13 then // нажата клавиша
75.if StringGridl.Col < StringGridl.ColCount - 1
76.then // курсор s следукацую ячейку таблицы
77.StringGridl.Col := StringGridl.Col +1
78.else // курсор в поле Editl, в поле ввода образца
79.Editl.SetFocus;
80.end;
81.// нажагие клавиши я поле Editl
82.procedure TForml.EditIKeyPress(Sender: TObject;.var Key: Char);
83.begin
84.if Key = #13 // нажата клавиша<enter></enter>
85.then // сделать активной командную кнопку
86.Buttonl.SetFocus;
87.endend.

 

Ниже приведены примеры диалоговых окон программы Бинарный поиск в массиве после выполнения поиска — с выводом протокола (рис. 5.14, а) и без протокола (рис. 5.14, б).

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

dle

Помоги проекту! Расскажи друзьям об этом сайте: