Алгоритм последовательного поиска

Рассмотрим задачу поиска определенного значения в списке. Мы хотим построить алгоритм, который определяет, есть ли в списке такое значение. Если есть, то поиск считается успешным; в противном случае поиск считается неудачным. Допустим, что элементы списка упорядочены по какому-то правилу. Например, если это список имен, то предположим, что его элементы располагаются в алфавитном порядке. Или, если список состоит из числовых значений, то элементы списка располагаются по возрастанию значения.

Для того чтобы сделать первый шаг в построении алгоритма, представим, что нам нужно найти некоторое имя в списке, состоящем из 20 гостей. В таком случае мы можем просмотреть список от начала до конца, сравнивая каждый элемент с искомым именем. Если мы найдем имя, то поиск закончится успехом. Однако, если мы дойдем до конца списка, не найдя имени, то поиск закончится неудачей. На самом деле поиск можно считать неудачным, когда мы достигли имени, которое начинается с буквы, находящейся в алфавите после первой буквы искомого имени. (Не забывайте, что элементы списка располагаются в алфавитном порядке, поэтому если мы достигли имени, которое в алфавитном порядке должно находиться после искомого, значит, нужного имени в списке нет.) Идея заключается

в том, чтобы продолжать поиск до тех пор, пока в списке есть имена и искомое имя больше, чем рассматриваемое имя списка.

Псевдокод этого процесса можно записать следующим образом:

Выбрать первый элемент списка как ПроверяемоеЗначение.

while (ИскомоеЗначение > ПроверяемоеЗначение и остаются не рассмотренные элементы списка)

do (Выбрать в качестве ПроверяемоеЗначение следующий элемент списка)

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

if (ИскомоеЗначение = ПроверяемоеЗначение) then (Поиск успешен.) else (Поиск неудачен.)

Наконец, можно заметить, что первая команда в нашей процедуре, которая выбирает первый элемент списка для рассмотрения, основана на предположении, что данный список содержит по крайней мере один элемент. Такое предположение достаточно надежно, но для большей уверенности можно начать процедуру условным оператором i f, поместив приведенный ранее псевдокод в качестве аргумента, после зарезервированного слова else:

if (список пустой)

then (поиск неудачен.) else (...)

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

Применить процедуру Поиск к списку пассажиров, чтобы найти имя Даррел Бейкер.

чтобы выяснить, является ли Даррел Бейкер пассажиром. Или выражение

Применить процедуру Поиск к списку ингредиентов, используя в качестве искомого значения мускатный орех.

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

Листинг 4.1. Алгоритм последовательно поиска, записанный с помощью псевдокода

procedure Поиск (Список. ИскомоеЗначение) if (Список пустой)

then (поиск неудачен) el se

(Выбрать первый элемент Список как ПроверяемоеЗначение;

while (ИскомоеЗначение > ПроверяемоеЗначение и остаются не рассмотренные элементы) do

(Выбрать в качестве ПроверяемоеЗначение следующий элемент Список); if (ИскомоеЗначение = ПроверяемоеЗначение) then (Поиск успешен.) else (Поиск неудачен.)) end if

Алгоритм (см. листинг 4.1) последовательно рассматривает элементы списка в том порядке, в каком они располагаются в списке. Поэтому он и называется алгоритмом последовательного поиска (sequential search). Благодаря своей простоте он часто используется для коротких списков. Однако когда мы имеем дело с длинными списками, последовательный поиск не так эффективен, как другие виды поиска, которые мы рассмотрим позже.

Управление циклом

Повторяющееся выполнение команды или набора команд является важным алгоритмическим понятием. Один из способов осуществления такого повторения — итеративная структура, которая называется циклом (loop). В цикле набор команд, которые называются телом цикла, выполняются повторно под контролем управляющего процесса. Пример цикла можно найти в алгоритме последовательного поиска (см. листинг 4.1). Здесь оператор цикла while используется для управления повторным выполнением команды Выбрать в качестве ПроверяемоеЗначение следующий элемент списка.

Оператор цикла while (условие) do (тело цикла)

служит примером цикла, поскольку его выполнение происходит по циклической

модели

проверить условие выполнить тело цикла проверить условие выполнить тело цинпа

проверить условие

до тех пор, пока условие истинно.

Как правило, использование циклов дает большую гибкость, чем написание тела цикла несколько раз. Например, хотя цикл

Выполнить команду "Добавить каплю серной кислоты" три раза. соответствует последовательности

Добавить каплю серной кислоты Добавить каплю серной кислоты Добавить каплю серной кислоты.

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

while (уровень рН больше 4) do (добавить каплю серной кислоты).

поскольку мы не знаем заранее, сколько может потребоваться капель серной кислоты.

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

Управление циклом состоит из трех шагов: инициализации, проверки и модификации (табл. 4.1), причем для успешной работы цикла необходимо присутствие всех этих трех этапов. При проверке отслеживается условие, которое обозначает окончание цикла, и если оно истинно, выполнение цикла завершается. Это условие называется условием завершения. Именно для осуществления проверки мы записываем условие в операторе цикла whi 1е нашего псевдокода. Однако в случае оператора while мы указываем условие выполнения цикла. Условием же завершения будет отрицание условия, находящегося в цикле. Таким образом, для цикла while (см. листинг 4.1) условие завершения такое:

(ИскомоеЗначение < ПроверяемоеЗначение) или (больне нет не рассмотренных элементов)

Таблица 4.1. Этапы управления циклом

Инициализация: определение начального состояния, которое будет модифицироваться до условия завершения.

Проверка: сравнение текущего состояния с условием завершения и, если они

совпадают, выполнение цикла завершается.

Модификация: изменение состояния так, чтобы оно приближалось к условию завершения.

Другие два этапа управления циклом обеспечивают проявление условия завершения. В процессе инициализации вводится начальное условие, а шаг модификации видоизменяет это условие до условия завершения. Например, в алгоритме (см. листинг 4.1) инициализация происходит с помощью выражения, предшествующего оператору while, когда текущий элемент списка назначается первым элементом для рассмотрения. Шаг модификации в этом примере выполняется в теле цикла, когда интересующая нас позиция смещается к концу списка. Таким образом, после инициализации повторяющаяся модификация приведет к выполнению условия завершения. (Или мы достигнем элемента списка, который больше или равен искомому значению, или мы достигнем конца списка.)

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

Number <— 1; while (Number *6) do (Number <— Number + 2)

Здесь условием завершения цикла является Number, равное 6. Начальное значение Number равно 1, затем в процессе модификации это значение увеличивается на 2. Следовательно, во время выполнения цикла переменной Number будут присвоены значения 1, 3, 5, 7, 9 и т. д., но никогда 6. Поэтому выполнение цикла никогда не закончится.

Существует две распространенных циклических структуры, которые отличаются только порядком выполнения шагов управления циклом. Примером первого является оператор цикла нашего псевдокода while (условие) do (действие), семантика которого изображена в виде блок-схемы (flowchart) на рис. 4.4. В таких схемах для представления отдельных шагов используются разные геометри-

ческие фигуры, а для отображения порядка шагов применяются стрелки. Форма геометрической фигуры обозначает тип действия, соответствующий данному шагу. Например, ромб обозначает принятие решения, а прямоугольник — команду или набор команд. Обратите внимание на то, что проверка условия завершения в цикле while осуществляется до выполнения тела цикла.

В отличие от оператора цикла while циклическая структура, изображенная на рис. 4.5, требует выполнения тела цикла до проверки условия завершения. В таком случае тело цикла выполняется по крайней мере один раз, в то время как в структуре с оператором while тело цикла не будет выполнено ни разу, если условие завершения истинно во время первой проверки.

Для того чтобы записать структуру, представленную на рис. 4.5, в нашем псевдокоде, будем использовать синтаксическую форму repeat (действие) until (условие)

Следовательно, выражение

repeat (достать монету из кошелька) until (в кошельке нет монет)

предполагает, что вначале в кошельке есть монета, а выражение

while (s кошельке есть монета) do (достать монету из кошелька)

не предполагает.

Придерживаясь терминологии нашего псевдокода, будем называть эти структуры оператором цикла с условием продолжения и оператором цикла с условием завершения. Иногда оператор цикла while называют априорным циклом (pretest loop), или циклом с предусловием, поскольку условие завершения проверяется до выполнения тела цикла, а оператор цикла repeat называется апостериорным циклом (posttest loop), или циклом с постусловием, поскольку условие завершения проверяется после выполнения цикла.