Песни о Паскале - [87]

      { Функция двоичного поиска }
function FindBin (aNum: integer): integer;
var L, M, R : integer; { левый, правый и средний индексы }
begin
      FindBin:= -1;       { результат на случай неудачи }
      L:= 1; R:= CSize;       { начальные значения индексов }
      repeat
      M:= (L+R) div 2;       { индекс среднего элемента }
      if aNum= ArrSort[M] then begin
      FindBin:= M;       { нашли ! }
      Break;       { успешный выход из цикла }
      end;
      if aNum > ArrSort[M] { где искать дальше? }
      then L:= M+1       { ищем правее }
      else R:= M–1; { ищем левее }
      until L > R;       { выход при неудачном поиске }
end;

Теперь мы готовы создать исследовательскую программу, которая будет сравнивать два способа поиска.

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

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

      { P_42_1 – Исследование методов поиска }
const CSize = 1000; { размер массива }
      { объявление типа для массива }
Type TNumbers = array [1..CSize] of integer;
Var ArrRand : TNumbers; { несортированный массив }
      ArrSort : TNumbers; { сортированный массив }
      Steps : integer; { для подсчета числа шагов поиска }
{ Процедура "пузырьковой" сортировки чисел в порядке возрастания }
procedure BubbleSort(var arg: TNumbers);
var i, j, t: Integer;
begin
for i:= 1 to CSize-1 do       { внешний цикл }
      for j:= 1 to CSize-i do { внутренний цикл }
      if arg[j] > arg[j+1] then begin { обмен местами }
      t:= arg[j]; arg[j]:= arg[j+1]; arg[j+1]:= t;
      end;
end;
      { Функция последовательного поиска (Find Sequence) }
function FindSeq (aNum: integer): integer;
var i: integer;
begin
      FindSeq:= -1;       { если не найдем, результат будет -1 }
      for i:=1 to CSize do begin
      Steps:= Steps+1; { подсчет шагов поиска }
      if aNum= ArrRand[i] then begin
      FindSeq:= i;       { нашли, возвращаем позицию }
      Break;       { выход из цикла }
      end;
      end;
end;
      { Функция двоичного поиска (Find Binary) }
function FindBin (aNum: integer): integer;
var L, M, R : integer;
begin
      FindBin:= -1;
      L:= 1; R:= CSize;
      repeat
      Steps:= Steps+1;       { подсчет шагов поиска }
      M:= (L+R) div 2;
      if aNum= ArrSort[M] then begin
      FindBin:= M;       { нашли ! }
      Break;       { выход из цикла }
      end;
      if aNum > ArrSort[M]
      then L:= M+1
      else R:= M-1;
      until L > R;
end;
      {--- Главная программа ---}
Var i, n, p : integer;       { вспомогательные переменные }
      F: text;       { файл результатов }
begin
      Assign(F,'P_42_1.OUT'); Rewrite(F);
      { Заполняем массив случайными числами }
      for i:=1 to CSize do ArrRand[i]:=1+Random(10000);
      ArrSort:= ArrRand;       { копируем один массив в другой }
      BubbleSort(ArrSort); { сортируем второй массив }

      repeat       { цикл с экспериментами }
      i:= 1+ Random(CSize); { индекс в пределах массива }
      n:= ArrRand[i];       { случайное число из массива }

      Writeln(F,'Искомое число= ', n);
      Steps:=0;       { обнуляем счетчик шагов поиска }
      p:= FindSeq(n);       { последовательный поиск }
      Writeln(F,'Последовательный: ', 'Позиция= ',
      p:3, ' Шагов= ', Steps);
      Steps:=0;       { обнуляем счетчик шагов поиска }
      p:= FindBin(n);       { двоичный поиск }
      Writeln(F,'Двоичный поиск: ', 'Позиция= ',
      p:3, ' Шагов= ', Steps);
      Write('Введите 0 для выхода из цикла '); Readln(n);
      until n=0;
      Close(F);
end.

Вот результаты трех экспериментов.

Искомое число= 5026
Последовательный: Позиция= 544 Шагов= 544
Двоичный поиск: Позиция= 518 Шагов= 10
Искомое число= 8528
Последовательный: Позиция= 828 Шагов= 828
Двоичный поиск: Позиция= 854 Шагов= 10
Искомое число= 7397
Последовательный: Позиция= 100 Шагов= 100
Двоичный поиск: Позиция= 748 Шагов= 9

Я не поленился проделать 20 опытов, результаты которых занес в табл. 7. Среднее число шагов поиска для каждого из методов посчитано мною на калькуляторе и внесено в последнюю строку таблицы.

Табл. 7- Результаты исследования алгоритмов поиска

Экспе-римент	Искомое число	Количество шагов поиска
		Последовательный поиск	Двоичный поиск
1	5026	544	10
2	8528	828	10
3	7397	100	9
4	2061	52	9
5	8227	634	9
6	9043	177	10
7	4257