 |
Предварительные и последующие операции
|
|
|
|
Отметим, что программа, которая находит решения для целевого утверждения, может выполнять какие-либо предварительные или завершающие операции. Например, в нашем примере программа могла бы:
1. Напечатать
Some delightful places to live are... (Некоторые восхитительные места для проживания...).
2. Напечатать все решения для country (X).
3. Завершить печать фразой And maybe others (Могут быть и другие).
Заметьте, что print_countries, определенное в предыдущем примере, уже содержит предложение вывести на печать все решения country (X) и отпечатать завершающее сообщение.
Первое предложение для print_countries соответствует шагу 2 и выводит на печать все решения. Его второе предложение соответствует шагу 3 и просто успешно завершает целевое утверждение (потому что первое предложение всегда в режиме fail — "неудачное завершение").
Можно было бы изменить второе предложение в программе ch06e01.pro.
print_countnes:-
write("And maybe others."), nl.
которое выполнило бы шаг 3, как указано.
А что можно сказать о шаге 1? В нем нет смысла, когда print_countnes содержал только 2 предложения. Но в предикате может быть и три предложения:
print_countries:-
write("Some delightful places to live are"), nl,
fail.
pnnt_countnes:-
country(X),
write(X),nl,
fail.
print_countries:-
write("And maybe others."), nl.
Наличие fail в первом предложении важно, поскольку он обеспечивает после выполнения первого предложения возврат и переход ко второму предложению Кроме того, это важно, потому что предикаты write и nl не образуют альтернатив Строго говоря, первое предложение проверяет все возможные решения перед тем, как завершиться неуспехом.
Такая структура из трех предложений более удобна по сравнению с общепринятым подходом.
Использование отката с петлями
Поиск с возвратом является хорошим способом определить все возможные решения целевого утверждения Но, даже если ваша задача не имеет множества решений, можно использовать поиск с возвратом для выполнения итераций Просто определите предикат с двумя предложениями
|
|
|
repeat
repeat - repeat
Этот прием демонстрирует создание структуры управления Пролога (см листинг на рис. 2.), которая порождает бесконечное множество решений. Цель предиката repeat — допустить бесконечность поиска с возвратом (бесконечное количество откатов)
/* Использование repeat для сохранения введенных символов и печатать их до тех пор, пока пользователь не нажмет Enter (Ввод)*/
predicates
repeat
typewriter
clauses
repeat.
repeat -repeat.
typewriter:-
repeat,
readchar(C),% Читать символ, его значение присвоить С
write(С),
С = '\r',% Символ возврат каретки (Enter)? или неуспех
goal
typewriter (), nl.
Рис. 9. Листинг 13.2. Программа ch06e02.pro
Программа ch06e02 pro показывает, как работает repeat Правило typewriter - описывает процесс приема символов с клавиатуры и отображения их на экране, пока пользователь не нажмет клавишу <Enter> (<Return>)
Правило typewriter работает следующим образом
1 Выполняет repeat (который ничего не делает, но ставит точку отката).
2 Присваивает переменной с значение символа.
3 Отображает С.
4 Проверяет, соответствует ли с коду возврата каретки.
5 Если соответствует, то — завершение. Если нет — возвращается к точке отката и ищет альтернативы, так как ни write, ни readchar не являются альтернативами,
Рекурсивные процедуры
Понятие рекурсии
Одним из способов организации повторений — рекурсия. Рекурсивная процедура — это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката.
Логика рекурсии проста для осуществления. Представьте себе ЭВМ, способную "понять":
|
|
|
Найти факториал числа N:
Если N равно 1, то факториал равен 1
Иначе найти факториал N-1 и умножить его на N.
Этот подход означает следующее:
первое («закручиваете» стек), чтобы найти факториал 3, вы должны найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факториал 1. факториал 1 ищется без обращения к другим факториалам, т.к. он равен 1, поэтому повторения не начнутся.
второе («раскручиваете» стек), если у вас есть факториал 1, то умножаете его на 2, чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получить факториал 3.
Информация хранится в области памяти, называемой стековым фреймом (stack frame) или просто стеком (stack), который создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стековым фреймом память освобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя.
Преимущества рекурсии
Рекурсия имеет три основных преимущества:
· она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;
· она логически проще метода итерации;
· она широко используется в обработке списков.
Рекурсия — хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, поиск в дереве (дерево состоит из более мелких деревьев) и рекурсивная сортировка (для сортировки списка, он разделяется на части, часть сортируются и затем объединяются вместе).
Логически рекурсивным алгоритмам присуща структура индуктивного математического доказательства. Приведенная выше рекурсивная программа вычисления факториала описывает бесконечное множество различных вычислений с помощью всего лишь двух предложений. Это позволяет легко увидеть правильность этих предложений. Кроме того, правильность каждого предложения может быть изучена независимо от другого.
|
|
|
