ВУЗ:
Procedure Поиск (Список, ИскомоеЗначение)
if
(Список пустой)
then {сообщить о неудаче}
else
{выбрать “средний” элемент как ПроверяемоеЗначение;
выполнить набор команд, соответствующий одному
из случаев:
Случай 1: ИскомоеЗначение = ПроверяемоеЗначение
{сообщить об успехе}
Случай 2: ИскомоеЗначение < ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в верхней части Списка и
сообщить о результате этого поиска}
Случай 3: ИскомоеЗначение > ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в нижней части Списка и
сообщить о результате этого поиска}
}
Procedure Поиск (Список, ИскомоеЗначение)
if
(Список пустой)
then {сообщить о неудаче}
else
{выбрать “средний” элемент как ПроверяемоеЗначение;
выполнить набор команд, соответствующий одному
из случаев:
Случай 1: ИскомоеЗначение = ПроверяемоеЗначение
{сообщить об успехе}
Случай 2: ИскомоеЗначение < ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в верхней части Списка и
сообщить о результате этого поиска}
Случай 3: ИскомоеЗначение > ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в нижней части Списка и
сообщить о результате этого поиска}
}
Evelyn
Fred
George
Alice
Carol
Список Список
Рис. 4.16. Вызов второй копии процедуры из ее исходной копии при поиске записи David
На этом этапе мы завершили дополнительный поиск, как предписывалось исходной процедурой, поэтому можно продол-
жить выполнение этой исходной копии, т.е. объявить результат дополнительного поиска результатом первоначального поис-
ка. В итоге выполнения всего процесса было совершенно справедливо установлено, что имя Bill присутствует в списке имен
Alice, Bill, Carol, David, Evelyn, Fred, George.
Теперь давайте посмотрим, что произойдет, если перед представленной на рис. 4.14 процедурой поставить задачу опре-
делить наличие в списке Alice, Carol, Evelyn, Fred, George элемента David. На этот раз исходная копия процедуры выбирает в
качестве проверяемого значения имя Evelyn и определяет, что искомое значение должно находиться в предшествующей час-
ти списка. Поэтому она вызывает еще одну копию процедуры для поиска в списке тех элементов, которые стоят перед име-
нем Evelyn, т.е. в двухэлементном списке, состоящем из имен Alice и Carol. Ситуация на этой стадии выполнения алгоритма
представлена на рис. 4.16.
Вторая копия процедуры выберет в качестве проверяемого элемента имя Carol и определит, что искомое значение
должно находиться после него. Процедура вызовет третью копию процедуры "Поиск" для поиска требуемого элемента в
списке имен, следующих за именем Carol в списке Alice, Carol. Однако этот список пуст и перед третьей копией процедуры
стоит задача поиска искомого значения David в пустом списке. Исходная копия процедуры осуществляет поиск требуемого
элемента в списке Alice, Carol, Evelyn, Fred, George, выбрав в качестве проверяемого имя Evelyn; вторая копия процедуры
занята поиском требуемого элемента в списке Alice, Carol, выбрав в качеству проверяемого элемент Carol; а третья начинает
поиск в пустом списке.
Конечно же, третья копия процедуры тут же объявляет свой поиск неудачным и завершается. После этого вторая копия
может продолжить свою работу. Она обнаруживает, что запрошенный поиск оказался неуспешным, поэтому также объявля-
ет свой поиск неудачным и завершается. Исходная копия процедуры, ожидавшая поступления сообщения от второй копии,
теперь может продолжить свою работу. Так как запрошенный поиск оказался неудачным, она тоже объявляет свой поиск
неудачным, после чего завершается. Таким образом, наша программа пришла к правильному заключению, что имя David не
содержится в списке имен Alice, Carol, Evelyn, Fred, George.
Если еще раз просмотреть приведенные выше примеры, можно увидеть, что в процессе, осуществляемом представлен-
ным на рис. 4.14 алгоритмом, необходимо многократно разделять рассматриваемый список на две примерно равные части,
после чего область дальнейшего поиска ограничивается лишь одной из этих частей. Именно это повторяющееся деление на
два послужило причиной того, что данный алгоритм был назван двоичным поиском.
Управление рекурсией. Алгоритм двоичного поиска похож на алгоритм последовательного поиска, так как каждый из них
предусматривает выполнение повторяющегося процесса. Однако реализация этого повторения в каждом случае существенно от-
личается. При последовательном поиске повторение организуется с помощью цикла, в случае двоичного поиска каждая стадия
повторения реализуется как подзадача предыдущей стадии. Этот метод повторения известен как рекурсия (recursion).
При выполнении рекурсивного алгоритма создается иллюзия существования множества его копий, называемых акти-
вациями (activation), которые появляются и исчезают по мере выполнения алгоритма. Из всех активаций, существующих в
заданный момент времени, активно функционирует только одна. Все остальные фактически остановлены, поскольку каждая
из них ожидает, пока завершится следующая, запущенная ею активация, и только после этого она сможет продолжить свою
работу.
Будучи повторяющимися процессами, рекурсивные структуры почти так же зависят от корректного управления, как и
циклические структуры. Как и в случае управления циклами, рекурсивные системы зависят от проверки условия окончания
Страницы
- « первая
- ‹ предыдущая
- …
- 94
- 95
- 96
- 97
- 98
- …
- следующая ›
- последняя »
