Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

сообщить о нарушении

Текущая страница: 15 (всего у книги 29 страниц)

В программе «P_40_2» обратите внимание на пропуск пустых строк в процедуре ReadFromFile. Если этого не сделать, счётчик Fact может оказаться на 1 больше, чем должно, – так случится, если за последним числом будут пустые строки. Следующий далее оператор чтения числа пренебрегает границами между строками, поэтому в одной строке допустимы несколько чисел.

{ P_40_2 – Полицейская база данных с применением массива }

const CNumbers = 1000; { размер массива с номерами автомобилей }

      { объявление типа для массива номеров }

type TNumbers = array[1..CNumbers] of integer;

var Numbers : TNumbers; { объявление массива номеров }

      Fact : integer;       { фактическое количество номеров в файле }

      F : text;       { файл с номерами }

      Num : integer;       { номер проверяемого автомобиля }

      { Процедура ввода номеров из файла }

procedure ReadFromFile(var aFile: text);

var i: integer;

begin

Fact:=0; { для начала подсчета номеров обнуляем счетчик }

for i:=1 to CNumbers do begin { цикл по массиву номеров }

while Eoln(aFile) do { Пропуск пустых строк }

      if Eof(aFile) then Break else Readln(aFile);

if Eof(aFile) then Break; { если конец файла – выход из цикла }

Read(aFile, Numbers[i]); { читаем номер в элемент массива }

Fact:= Fact+1;       { наращиваем счетчик номеров }

end;

end;

{ Функция поиска в массиве номеров автомобилей }

function FindNumber(aNum: integer): boolean;

var i: integer;

begin

      FindNumber:= false;

      for i:=1 to Fact do

      if aNum=Numbers[i] then begin

      FindNumber:= true;       { нашли ! }

      Break;       { выход из цикла }

      end

end;

begin       {– Главная программа –}

      { открываем файл и читаем номера автомобилей }

      Assign(F, 'P_38_2.in'); Reset(F);

      ReadFromFile(F);       { ввод номеров из файла }

      Close(F);

      repeat       { Главный цикл }

      Write('Укажите номер автомобиля: '); Readln(Num);

      if FindNumber(Num)

      then Writeln('Эта машина в розыске, хватайте его!')

      else Writeln('Пропустите его');

      until Num=0; { 0 – признак завершения программы}

end.

Ещё раз о статистике

Следующая программка будет маленькой, да удаленькой. Вернемся к статистике, с которой познакомились при обработке классного журнала. Напомню, что статистика – это наука, изучающая массовые явления. В текстах наших программ полным-полно разных букв, – давайте посчитаем их. Результатом работы программы будет таблица, похожая на эту.

a 119

b 45

c 72

...

Здесь левый столбец составляют буквы, а правый – количество этих букв в некотором файле. Упростим себе задачу, ограничившись подсчетом лишь маленьких латинских букв от «a» до «z».

Для подсчета общего количества символов в файле хватило бы одного счетчика. Но здесь 26 букв, а значит и счетчиков надо столько же. Массив счетчиков напрашивается сам собой, его тип можно объявить так:

type TCounts = array [1..26] of integer;

Однако не спешите этого делать. Вспомните о том, что индексом массива может быть любой порядковый тип данных. А к ним, наряду с числами, относятся символьный и даже булев тип. Стало быть, допустимы такие массивы.

type TA = array ['A'..'F'] of integer;

      TB = array [false..true] of integer;

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

type TCounts = array ['a'..'z'] of integer;

Теперь символ, прочитанный из файла, можно использовать как индекс в массиве счетчиков, надо лишь предварительно проверить его на попадание в нужный диапазон.

Входным файлом программы будет текст её самой же. Вот она, простая и красивая.

{ P_40_3 – Подсчет количества различных букв в файле }

      { Тип массива из целых чисел, индекс – символьный }

type TCounts = array ['a'..'z'] of integer;

var Counts : TCounts; { массив из счетчиков букв }

      c: char; { текущий символ файла, он же – индекс счетчика }

      F : text; { файл с текстом программы }

begin       {– главная программа –}

{ Перед началом подсчета все счетчики обнуляем }

for c:='a' to 'z' do Counts[c]:=0;

{ Открываем входной файл для чтения }

Assign(F, 'P_40_3.pas'); Reset(F);

while not Eof(F) do begin { Цикл чтения и подсчета букв }

Read(F, c);       { чтение одного символа из файла }

if c in ['a'..'z']       { если символ в нужном диапазоне }

      then Counts[c]:= Counts[c]+1; { наращиваем его счетчик }

end;

Close(F);

{ После подсчета распечатаем все счетчики }

for c:='a' to 'z' do Writeln (c, Counts[c]:6);

Write('Нажмите Enter'); Readln;

end.

Здесь осталась лишь одна шероховатость – при печати результатов часть строк не поместится на экране. Так направьте вывод в текстовый файл. Или слабо?

Итоги

• Массивы, как любые переменные, «живут» в оперативной памяти. Переместив данные из файлов в массивы, мы многократно ускорим их обработку.

• Для индексации массивов допустимы любые порядковые типы данных. Выбор подходящего типа для индекса упрощает и украшает программу.

• При чтении чисел из текстового файла в «боевых» программах необходимо учитывать возможное наличие в файле пустых строк. Такие строки могут привести к чтению оператором Read несуществующего пустого числа (см. процедуру ReadFromFile в программе «P_40_2»).

А слабо?

А) Напишите программу для подсчета различных цифр в файле полицейской базы данных (считать надо именно цифры, а не числа!).

Б) Объявите массив из сотни целых чисел, заполните его случайными числами в диапазоне от 0 до 255 и распечатайте этот массив.

В) Найдите в массиве (задание Б) все элементы, хранящие число 7 (если таковые найдутся). Напечатайте индексы элементов, которые содержат это число.

Г) Заполните массив (задание Б) случайными числами в диапазоне от 0 до 255 так, чтобы ни одно из них не повторялось. Воспользуйтесь вспомогательным множеством чисел, где будут запоминаться сгенерированные ранее числа.

Д) Найдите в массиве (задание Г) наименьшее и наибольшее числа, напечатайте их, а также соответствующие им индексы элементов массива.

Е) Вращение массива вправо. Объявите массив из 10 чисел и заполните его случайным образом. Напишите процедуру, перемещающую 1-й элемент на 2-е место, 2-й – на 3-е место и т.д. Последний элемент должен занять 1-е место.

Ж) Вращение массива влево. Напишите процедуру для перемещения 2-го элемента на 1-е место, 3-го – на 2-е место и т.д. При этом первый элемент должен стать последним.

И) Напишите функцию для подсчета количества номеров в полицейской БД при условии, что одна строка может содержать несколько номеров, а некоторые строки (в т.ч. в конце файла) могут быть пустыми.

Глава 41

По порядку, становись!

В 39-й главе, где состоялось наше знакомство с массивами, мы намерились отсортировать футбольные команды в порядке набранных ими очков. Следуя к этой цели, перенесемся ненадолго в прошлое, – лет на триста назад.

Пиратская справедливость

Тогда в морях разбойничали «джентльмены», которых мы зовем пиратами. Одной из таких бригад повелевал некто Райт. Пиратские команды не отличались дисциплиной, но Райт добился порядка на корабле, избегая жестокостей. Отважный в бою, Райт давал пример и в мирных обстоятельствах, деля добычу если не поровну, то хотя бы по справедливости. Вожак брал равную со всеми долю, потому команда чтила его и подчинялась беспрекословно.

Однажды джентльменам удачи достался сундук с золотыми слитками. Пересчитав их, пираты выяснили, что каждому из них полагается ровно по два. Казалось бы, о чем тут думать? – садись и дели. Однако слитки существенно отличались формой и размерами. Пираты не могли распилить или переплавить их, сделав одинаковыми. Как быть? – с таким вопросом Райт обратился к экипажу.

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

– Я предлагаю, – молвил Нашатырь, – разложить слитки в порядке их веса. Затем кто-то из нас возьмет самый легкий и самый тяжелый из них. Другой – самый легкий и самый тяжелый из оставшихся, и так далее.

Свою мысль он сопроводил рисунком с шестью слитками разного веса и размера (рис. 89).

– Отлично, – согласился Райт, – но как взвесить слитки? У нас нет ни гирь, ни весов.

– Зачем мне гири? Для сравнения слитков годится вот это, – и лекарь достал из своего сундука самодельные чашечные весы.

– Ну что ж, – сказал Райт, – ты придумал, тебе и делить.

И под пристальными взглядами всей команды лекарь принялся за дело.

Вначале ряд слитков он выложил, как попало. Затем стал по очереди сравнивать соседние куски. Если первый из них был тяжелее второго, аптекарь менял их местами. Так он сравнил первый и второй слитки, второй и третий, третий и четвертый и так далее до последнего слитка. В конце концов, самый тяжелый слиток оказался на последнем месте. Затем он повторил все это ещё раз, – и тогда второй по величине слиток оказался на предпоследнем месте. Проделав это N-1 раз, где N – количество слитков, лекарь выложил слитки в нужном порядке: первым лежал самый легкий, а последним – самый тяжелый.

Рис.89 – Пример справедливого дележа шести слитков между тремя пиратами

«А теперь бросайте жребий, – подытожил Нашатырь, скромно отходя в сторону, – пусть он определит порядок взятия долей». Пираты остались довольны.

Пузырьковая сортировка

Вернемся в наше время. О пиратской истории программист сказал бы так: разложив куски золота в нужном порядке, лекарь отсортировал массив слитков. Его метод известен как «пузырьковая сортировка» – Bubble Sort. Откуда взялось это название? Проследите за пузырьками в стакане газировки: по мере всплытия они объединяются с другими и становятся крупнее.

Воспользуемся методом лекаря-аптекаря для сортировки массива из 10 целых чисел – это будут наши золотые слитки. А для испытания алгоритма напишем программу «P_41_1», которая вначале заполнит массив случайным образом и распечатает его. Затем отсортирует этот массив и снова распечатает. Работу по сортировке выделим в отдельную процедуру по имени BubbleSort, – она ещё пригодится нам в последующих проектах.

Исследуйте процедуру сортировки по шагам. Здесь «крутятся» два цикла FOR-TO-DO, вложенные друг в друга. Внутренний цикл со счетчиком J сравнивает соседние числа и, при необходимости, меняет их местами. Переменная T нужна для перестановки соседних элементов. По завершении одного внутреннего цикла очередное крупное число оказывается на своем месте. Но, поскольку сортируются CSize чисел, то внутренний цикл надо повторить CSize-1 раз, – это делает внешний цикл со счетчиком I.

      { P_41_1 – Сортировка массива целых чисел }

const CSize = 10; { размер массива }

      { объявление типа для массива }

type TGolds = array [1..CSize] of integer;

var Golds : TGolds; { массив кусков золота }

      { Процедура "пузырьковой" сортировки }

      { Внимание! Параметр-массив передается по ссылке! }

procedure BubbleSort (var arg: TGolds);

var i, j, t: Integer;

begin

for i:= 1 to CSize-1 do { внешний цикл }

      for j:= 1 to CSize-1 do { внутренний цикл }

      { если текущий элемент больше следующего …}

      if arg[j] > arg[j+1] then begin

      { то меняем местами соседние элементы }

      t:= arg[j];       { временно запоминаем }

      arg[j]:= arg[j+1];       { следующий -> в текущий }

      arg[j+1]:= t;       { текущий -> в следующий }

      end;

end;

var i:integer; { для индекса в главной программе }

begin {– Главная программа –}

      { заполняем массив случайным образом }

      Randomize;

      for i:=1 to CSize do Golds [i]:= 1+Random(1000);

      { распечатаем до сортировки }

      Writeln('До сортировки:');

      for i:=1 to CSize do Writeln(Golds [i]:3);

      { сортируем }

      BubbleSort(Golds);

      { распечатаем после сортировки }

      Writeln('После сортировки:');

      for i:=1 to CSize do Writeln(Golds [i]:3);

      Readln;

end.

Обратите внимание: сортируемый массив передан в процедуру по ссылке VAR. Передача в процедуры массивов, множеств, строк и других сложных типов данных по ссылкам CONST и VAR – обычная практика. Это повышает скорость работы программ и уменьшает объём памяти, занимаемый параматрами.

При должном внимании вы обнаружите в этой сортировке небольшой изъян, суть которого такова. После отработки первого внутреннего цикла самый большой элемент окажется на последнем месте. А значит, на втором внутреннем цикле нет смысла сравнивать два последних элемента. На третьем проходе соответственно нет смысла сравнивать три последних элемента, – они уже лежат в нужном порядке. На этих сравнениях мы зря теряем время. Порок этот легко устранить, если поправить внутренний цикл так:

      for j:= 1 to CSize – i do { внутренний цикл }

Теперь каждый следующий внутренний цикл будет на единицу короче предыдущего (ведь счетчик внешнего цикла I растет). В следующей программе мы так и сделаем.

Электронная делёжка

Рассмотрев хитрости пузырьковой сортировки, поможем теперь морским романтикам. Напишем программу для справедливой дележки золотых слитков. Основная работа уже проделана, – мы смогли отсортировать массив. Осталось лишь распечатать веса тех кусков, что достанутся каждому из пиратов. Известно, что первому пирату достанется первый и последний слитки, второму – второй и предпоследний и так далее. Иначе говоря, I–му пирату достанутся слитки с номерами I и CSize+1-I. Программа «P_41_2» «делит слитки», распечатывая после сортировки веса соответствующих пар.

{ P_41_2 – Пиратская делёжка по справедливости }

const CSize = 16; { размер массива слитков }

      { объявление типа для массива слитков }

type TGolds = array [1..CSize] of integer;

var Golds : TGolds; { массив кусков золота }

      { Процедура "пузырьковой" сортировки }

procedure BubbleSort (var arg: TGolds);

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;

var i:integer; { используется в качестве индекса в главной программе }

begin

      { заполняем массив случайным образом }

      Randomize;

      for i:=1 to CSize do Golds[i]:= 500 + Random(500);

      { сортируем }

      BubbleSort(Golds);

      Writeln('По справедливости:');

      for i:=1 to (CSize div 2) do begin

      { два куска по отдельности }

      Write(i:2, Golds[i]:5,' + ',Golds[CSize+1-i]:3,' = ');

      { сумма двух кусков }

      Writeln(Golds[i]+Golds[CSize+1-i] :4);

      end;

      Readln;

end.

Вот результат одной из таких делёжек:

По справедливости:

1 506 + 975 = 1481

2 556 + 967 = 1523

3 587 + 954 = 1541

4 629 + 916 = 1545

5 691 + 876 = 1567

6 694 + 872 = 1566

7 749 + 845 = 1594

8 751 + 800 = 1551

Здесь самый легкий и самый тяжелый слитки отличаются почти вдвое: 506 и 975 граммов. Но пары слитков, доставшихся пиратам, отличаются по весу незначительно.

Возвращение на футбольное поле

Закаленные морскими приключениями, вернемся к сортировке футбольных клубов (задача поставлена в главе 39, помните?). Что мы будем сортировать? Набранные очки? Да, но их надо как-то привязать к названиям команд.

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

Впрочем, потребуется ещё одно мелкое изменение. Если при сортировке золотых слитков мы добивались возрастающего порядка, то теперь нужен противоположный, убывающий порядок сортировки. Как его добиться? Очень просто: изменим условие сравнения соседних элементов на противоположное. Вот собственно и все, осталось лишь показать программу «P_41_3».

{P_41_3 – Футбольный чемпионат }

const CSize = 16; { количество команд }

      { объявление типов для массивов }

type TAces = array [1..CSize] of integer; { тип для очков }

      TNames = array [1..CSize] of string; { тип для названий }

var Aces : TAces; { набранные очки }

      Names: TNames; { названия команд }

      { Процедура "пузырьковой" сортировки очков с именами команд }

procedure BubbleSort2(var arg1: TAces; var arg2: TNames);

var i, j, t: Integer;

      s: string;

begin

for i:= 1 to CSize-1 do { внешний цикл }

      for j:= 1 to CSize-i do { внутренний цикл }

      { если текущий элемент меньше следующего …}

      if arg1[j] < arg1[j+1] then begin

      { то меняем местами соседние элементы }

      t:= arg1[j];       { временно запоминаем }

      arg1[j]:= arg1[j+1]; { следующий -> в текущий }

      arg1[j+1]:= t;       { текущий -> в следующий }

      { меняем местами и названия команд }

      s:= arg2[j];       { временно запоминаем }

      arg2[j]:= arg2[j+1]; { следующий -> в текущий }

      arg2[j+1]:= s;       { текущий -> в следующий }

      end;

end;

var i: integer;

begin       { главная программа }

{ Вводим названия команд и набранные очки }

for i:=1 to CSize do begin

      Write('Название команды: '); Readln(Names[i]);

      Write('Набранные очки: '); Readln(Aces[i]);

end;

BubbleSort2(Aces, Names); { сортируем }

Writeln('Итоги чемпионата:');

Writeln('Место       Команда       Очки');

for i:=1 to CSize do

      Writeln(i:3,' ':3, Names[i], Aces[i]:20-Length(Names[i]));

Readln;

end.

Спецификатор ширины поля в операторе печати задан выражением.

      20 – Length(Names[i])

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

Для проверки программы я ввел наобум имена четырех команд нашего чемпионата и очки, якобы заработанные ими (количество команд CSize установил равным 4), и вот что у меня вышло.

Итоги чемпионата:

Место Команда       Очки

1 Локомотив       55

2 Крылья Советов 54

3 Спартак       47

4 Зенит       43

Болельщики вправе оспорить результат, но я им доволен.

Итоги

• Расположение данных в порядке возрастания или убывания называется сортировкой.

• Простейший алгоритм сортировки массива – «пузырьковая» сортировка. Она состоит в сравнении и перестановке соседних элементов массива, при этом организуются два вложенных цикла.

А слабо?

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

Б) Придумайте самый несправедливый способ пиратской дележки по два слитка и напишите программу для неё.

В) Напишите программу для дележки случайным образом (как это собирались сделать пираты). Насколько отличаются ваши результаты от справедливого способа?

Г) Напишите функцию, проверяющую, упорядочен ли числовой массив. Функция должна вернуть TRUE, если массив упорядочен по возрастанию. Массив внутрь функции передайте параметром по ссылке.

Глава 42

Кто ищет, тот всегда найдет

Все кругом ищут что-то: Карабас-Барабас – золотой ключик, Лиса с Котом – дураков, а Буратино – Страну Дураков. И я ищу: то ключи в карманах, то тапочки под диваном. А сколько всего таится в Интернете! Благо, искать информацию там помогают компьютеры.

Где эта улица, где этот дом?

В 40-й главе мы смастерили программу для поиска угнанных автомобилей. Испытаем её вон на той легковушке. Вводим номер машины и… оп! Вот так удача! Автомобильчик-то в розыске, – надо вернуть его владельцу. Однако, кто он? Где живет? А телефончик не подскажете? К сожалению, в нашей базе данных этих сведений нет, – её следует дополнить.

Добавим в программу поиска автомобилей массив строк, где будем хранить сведения о владельце: его имя, фамилию и телефон.

const CNumbers = 100; { размер массивов }

type TNumbers = array[1..CNumbers] of integer;

      TNames = array[1..CNumbers] of string;

var Numbers : TNumbers; { массив номеров автомобилей }

      Names : TNames;       { массив сведений о владельце }

Здесь добавлен массив Names (имена), содержащий столько же строк, сколько номеров в базе данных. Эти строки соответствуют элементам массива номеров Numbers. Так, если элемент Numbers[7] содержит число 123, а элемент Names[7] – строку «Горбунков С.С., тел. 11-22-33», то значит, гражданин Горбунков владеет автомобилем с номером 123.

Что связывает массивы Names и Numbers? Ответ очевиден – общий индекс. Определив индекс автомобиля в массиве номеров, мы получим доступ и к сведениям о его владельце в строковом массиве.

Последовательный поиск

Напомню, что в полицейской базе данных из 40-й главы заголовок функции поиска был таким.

function FindNumber(aNum: integer): boolean;

Функция FindNumber выясняет, существует ли искомый номер в массиве Numbers, то есть она дает булев результат. Теперь этого мало, – хочется получить индекс элемента, где хранится искомый номер. А если такого номера в массиве нет? Пусть тогда функция вернет некоторое условное значение, например, минус единицу.

С учетом этих пожеланий, напишем новую функцию поиска и дадим ей имя FindSeq (от слов Find – «искать», Sequence – «последовательно»).

      { Функция поиска в массиве Numbers позиции числа aNum }

function FindSeq (aNum: integer): integer;

var i: integer;

begin

      FindSeq:= -1;       { если не найдем, то результат будет -1 }

      for i:=1 to Fact do

      if aNum=Numbers[i] then begin

      FindSeq:= i;       { нашли, возвращаем индекс }

      Break;       { выход из цикла }

      end

end;

Новая функция сравнивает искомое число с элементами массива, перебирая их последовательно до тех пор, пока не найдет подходящий элемент или не уткнется в конец массива. В случае успеха она вернет индекс элемента в массиве, а иначе – минус единицу.

Этот способ называют поиском прямым перебором или линейным поиском. Линейный поиск прост, но крайне медлителен. Если бы библиотекарь искал заказанную книгу прямым перебором, клиент дремал бы в ожидании заказа месяцами! Но библиотекарь справляется с поиском, живо находя нужное среди сотен тысяч томов. Как ему удается это?

Все дело в порядке. Там, где порядок, искать проще и быстрей. Вы ищите ложку в кухонном шкафу, а ботинки – на обувной полке, но не обшариваете весь дом. Есть свой порядок и в библиотеке, потому персонал и справляется с работой. Компьютер ищет куда быстрее человека, и все же понуждать его к линейному поиску – проявление крайней жестокости. Впрочем, пострадает не столько компьютер, сколько уснувший в томлении пользователь.

Двоичный поиск

Один удачливый зверолов в минуту откровенности поделился секретом своих успехов. «Вначале я делю лес своей огромной сетью примерно пополам, и выясняю, в которой из двух половин очутился нужный мне зверь – пояснил охотник. – Затем половину со зверем опять делю пополам и гляжу, где он теперь. И так поступаю, пока животное не окажется в тесном загоне». И зверолов нацарапал на песке рис. 90.

Рис.90 – Поимка зайца шестью сетями

Здесь показано, как шестью сетями (они обозначены цифрами) был изловлен несчастный заяц. Обратите внимание на нумерацию сетей, – они расставлялись в этом порядке.

Не воспользоваться ли уловкой зверолова для поиска в массиве? Ускорит ли это дело? Конечно! Но массив должен быть заранее отсортирован. На рис. 91 показан отсортированный по возрастанию массив, содержащий 12 чисел. Для наглядности числа изображены столбиками. Среди них я выбрал наугад число 32, и прямым перебором нашел его позицию (индекс) в массиве. Очевидно, что я выполнил 8 шагов поиска, поскольку число 32 хранится в 8-м элементе массива.

А теперь применим метод зверолова. Обратимся к среднему элементу массива, индекс которого равен полу-сумме первого и последнего индексов, то есть:

(1+12)/2 = 6

Рис.91 – Двоичный поиск в отсортированном массиве

Поскольку индекс – это целое число, дробную часть при делении отбросим. Итак, в позиции 6 оказалось число 21, которое меньше искомого числа 32. Это значит, что «зверь притаился» где-то правее. Раз так, элементы массива, расположенные левее, нас уже не интересуют, – мысленно отбросим их.

С оставшейся частью массива поступим точно так же, то есть, исследуем средний его элемент с индексом

(7+12)/2 = 9

Сравним «живущее» там число 40 с искомым числом 32. На этот раз оно оказалось больше искомого, а значит, искать надо левее, а все, что справа, отбросить. Так, на третьем шаге поиска из 12 элементов массива остались лишь два. Рассуждая тем же порядком, выделяем элемент с индексом

(7+8)/2 = 7

и отбрасываем на этот раз число 27. И вот на последнем четвертом шаге остался лишь один элемент с искомым числом 32.

Подведем итог: вместо 8 шагов последовательного поиска, метод зверолова сделал то же самое за 4 шага. Скажете: всего-то? Восемь шагов или четыре – разница невелика. Так проверим оба метода на большом наборе данных, – поищем в массиве из тысячи чисел. Только избавьте меня от ручной работы, – этот эксперимент поручим компьютеру, для чего соорудим несложную программу.

Исследование двоичного поиска

Частью этой программы будет функция двоичного поиска, алгоритм которой раскрыл зверолов. Но не худо привести и блок-схему этого чудесного изобретения. На блок-схеме (рис. 92), как и в программе, индексы элементов обозначены начальными буквами соответствующих английских слов: L – левый индекс (Left), R – правый индекс (Right), и M – средний индекс (Middle).

Рис.92 – Блок-схема алгоритма двоичного поиска

Функцию, работающую по этому алгоритму, я назвал FindBin (Find – «поиск», Binary – «двоичный»), она показана ниже. Полагаю, что приведенных в ней комментариев будет достаточно.

      { Функция двоичного поиска }

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);