А слабо?

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

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

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

Г) Напишите функцию, проверяющую, упорядочен ли числовой массив. Функция должна вернуть 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 шага. Скажете: всего-то? Восемь шагов или четыре – разница невелика. Так проверим оба метода на большом наборе данных, – поищем в массиве из тысячи чисел. Только избавьте меня от ручной работы, – этот эксперимент поручим компьютеру, для чего соорудим несложную программу.