Практикум 3-2
|
1. Проверьте работу программы, приведенной на рис.3.3. 2. Проверьте, как изменятся результаты, если в предикат show вставлять предикат отсечения:
Объясните каждый из получившихся результатов. Определите в каждом случае цвет отсечения |
Отсечение - это мощный, но и опасный оператор Пролога: он многое позволяет, но делает программу более трудной для понимания.
Использование рекурсии
Правило является рекурсивным, если содержит в качестве компоненты само себя. Рекурсия допустима в большинстве языков программирования, но там этот механизм не является таким важным, поскольку имеются другие, свойственные процедурным языкам, механизмы – циклы, процедуры и функции.
Рассмотрим преимущества использования рекурсии на примере.
Пусть имеются следующие факты о том, какая валюта котируется выше (рис.3.4):
Рис 3.4. Пример программы
Результатом запроса на рис.3.4 будет yes, потому что такой факт явно описан в программе.
Если же сделать запрос,
GOAL
doroge(евро, йена).
или
doroge (фунт, рубль).
То ответ будет отрицательный (no), поскольку такие факты отсутствуют.
Избежать противоречий здесь можно введением правила, в котором допустимо сравнение между собой не только двух, но и трех объектов:
doroge_3(X, Y):- doroge(X, Y). /* два объекта */
doroge_3(X, Y):- doroge(X, Z), doroge(Z, Y). /* три объекта */
Второе правило описывает правило транзитивности, если X>Z, и Z>Y, то делается вывод, что X>Y.
Однако цепочка взаимных сравнений может быть более длинной. Например, при четырех сравнениях потребуется конструкция:
doroge_4(X, Y):- doroge(X, M), doroge(M, K), doroge(K, Z), doroge(Z, Y).
Описывать такие длинные правила неудобно. Здесь выгоднее применить рекурсию, обратившись к правилу из самого этого правила:
val_doroge(X, Y):- doroge(X, Y).
val_doroge(X, Y):- doroge(X, Z), val_doroge(Z, Y).
Первое предложение в этой конструкции определяет момент прекращения рекурсивных вызовов, если существует такой факт.
Второе правило описывает возможности рекурсивных вызовов, когда существуют варианты решения, выводимые логичски.
Практикум 3-3
|
Проверьте, как работает программа c рекурсией (с фактами о том, какая валюта котируется выше, рис.3.4), получите ответы на вопросы – выбрать все валюты, которые котируется выше рубля, – выбрать все валюты, которые котируется ниже рубля.
|
Любая рекурсивная процедура должна включать в себя базис и шаг рекурсии.
Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения
Шаг рекурсии – это рекурсивное правило, имеющее подцель, которая вырабатывает новые значения аргументов, и рекурсивную подцель, которая использует вычисленные значения. Во избежание зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле.
База правил просматривается всегда сверху вниз. Сначала делается попытка выполнения нерекурсивной фразы (базиса). Если условие окончания рекурсии не указано, то правило может работать бесконечно.
Например:
write_string :- write(“*****”),nl, write_string.
будет бесконечно печатать звездочки на экране компьютера.
Рассмотрим применение рекурсии на примере вычисления факториала натурального числа N!=1*2*3*…*N. Рекурсивная математическая запись:
-
1!=1
N!=(N-1)!*N
На рис. 3.5 представлена программа вычисления факториала, однако эта программа не будет работать правильно, а будет вызывать бесконечный цикл и переполнение памяти. Это происходит потому, что в программе произошел выход в отрицательную часть целых чисел, что не было предусмотрено формулой, на которой была основана эта процедура.
Рис 3.5. Пример неправильной программы
Для исправления этой ошибки возможны два варианта
Можно проверить, что число, для которого применяется правило, больше единицы (рис. 3.6-а).
Добавить в первое предложение (в базис рекурсии) отсечение. При достижении истинности высказывания, предложения процедуры, расположенные ниже той, из которой оно было вызвано, не рассматриваются (рис.3.6-б )
-
а)
б)
Рис 3.6. Примеры исправления программы