Информатика. Курс лекций. Громов Ю.Ю - 95 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 4.14. Алгоритм двоичного поиска, записанный на псевдокоде
вторую копию процедуры Search, предназначенную для решения данной промежуточной задачи.
Теперь мы имеем две выполняющиеся копии нашей процедуры поиска, как показано на рис. 4.15. Дальнейшее выполне-
ние исходной копии процедуры временно приостановлено на следующей инструкции:
Применить процедуру Search, чтобы определить, есть ли в части списка, предшествующей
элементу <проверяемый_элемент>, элемент <искомое_значение>
Вторая копия процедуры используется для поиска имени Bill в списке Alice, Bill, Carol. Завершив вторую процедуру
двоичного поиска, мы аннулируем ее копию и сообщим полученные в ней результаты исходной копии, после чего выполне-
ние исходной копии будет продолжено с указанного места. Таким образом, вторая копия процедуры функционирует как
подчиненная исходной, выполняя задачу, запрошенную исходной копией, а затем исчезая.
Вторичная процедура поиска выбирает имя Bill в качестве проверяемого значения, так как это средний элемент в списке
Alice, Bill, Carol. Поскольку он совпадает с искомым значением, поиск объявляется успешным и вторичная процедура за-
вершает свою работу.
Procedure
Поиск (Список, ИскомоеЗначение)
if (Список пустой)
then {сообщить о неудаче}
else {выбрать “средний” элемент как ПроверяемоеЗначение;
выполнить набор команд, соответствующий одному
из случаев:
Случай 1: ИскомоеЗначение = ПроверяемоеЗначение
{сообщить об успехе}
Случай 2
: ИскомоеЗначение < ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в верхней части Списка и
сообщить о результате этого поиска}
Случай 3
: ИскомоеЗначение > ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в нижней части Списка и
сообщить о результате этого поиска}
}
Procedure
Поиск (Список, ИскомоеЗначение)
if (Список пустой)
then {сообщить о неудаче}
else {выбрать “средний” элемент как ПроверяемоеЗначение;
выполнить набор команд, соответствующий одному
из случаев:
Случай 1: ИскомоеЗначение = ПроверяемоеЗначение
{сообщить об успехе}
Случай 2
: ИскомоеЗначение < ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в верхней части Списка и
сообщить о результате этого поиска}
Случай 3
: ИскомоеЗначение > ПроверяемоеЗначение
{применить процедуру Поиск для обнаружения
ИскомоеЗначение в нижней части Списка и
сообщить о результате этого поиска}
}
David
Evelyn
Fred
George
Alice
Bill
Carol
Список Список
Рис. 4.15. Вызов второй копии процедуры из ее исходной копии при поиске записи Bill
Procedure Поиск (Список, ИскомоеЗначение)
if (Список пустой)
then {сообщить о неудаче}
else {выбрать “средний” элемент как Про-
веряемоеЗначение;выполнить набор команд, соответ-
ствующий одному из случаев:
Случай 1: ИскомоеЗначение = Проверяе-
моеЗначение {сообщить об успехе}
Случай 2: ИскомоеЗначение < Проверяе-
моеЗначение {применить процедуру Поиск для обна-
ружения ИскомоеЗначение в верхней части Списка, и
сообщить о результате этого поиска}
Случай 3: ИскомоеЗначение > Проверяе-
моеЗначение {применить процедуру Поиск для обна-
ружения ИскомоеЗначение в нижней части Списка, и
сообщить о результате этого поиска}
}

Страницы