Материал: Методическое пособие по Turbo Prolog (новое)

Будет получен утвердительный ответ, поскольку такой факт явно описан в программе. Если же сделать запрос,

? doroje(evro, iena).

То ответ будет отрицательный, поскольку такой факт отсутствует. Аналогичным будет ответ на вопрос:

? doroje(funt, rubl).

Избежать противоречий здесь можно введением правила, в котором допустимо сравнение между собой не только двух, но и трех объектов:

Второе правило описывает, очевидно, вариант, когда X>Z, а Z>Y, откуда делается вывод, что X>Y.

Однако цепочка взаимных сравнений может быть длинной. Например, при четырех сравнениях потребуется конструкция:

doroje2(X, Y):- doroje(X, M), doroje(M, K), doroje(K, Z), doroje(Z, Y).

Описывать такие длинные правила неудобно. Здесь выгоднее применить рекурсию, обратившись к правилу из самого этого правила:

doroje1(X, Y):- doroje(X, Y).

doroje1(X, Y):- doroje(X, Z), doroje1(Z, Y).

Первое предложение в этой конструкции определяет момент прекращения рекурсивных вызовов.

Второе правило описывает возможности рекурсивных вызовов, когда существуют непроверенные варианты решения.

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

1.Нерекурсивную фразу, определяющую правило, применяемое в момент прекращения рекурсии.

2.Рекурсивное правило, первая подцель которого вырабатывает новые значения аргументов, а вторая – рекурсивная подцель – использует эти значения.

База правил просматривается сверху вниз. Сначала делается попытка выполнения нерекурсивной фразы. Если условие окончания рекурсии не указано, то правило может работать бесконечно. Например:

16

write_string :- write(“*****”),nl, write_string.

будет бесконечно печатать звездочки на экране компьютера. Следующая программа печатает на экране компьютера цифры от 1

до 7.

Программа 10

DOMAINS number=integer

PREDICATES write_number(number)

GOAL

write(“Это числа:”), nl, write_number(1). CLAUSES

write_number(10).

write_number(N) :- N<10,write(N),nl,N1:=N+1, write_number(N). В разделе clauses даны два описания предиката write_number. Если в

процессе решения первое описание неуспешно, то используется второе описание.

Программа 11 печатает сумму всех цифр введенного с клавиатуры числа.

Программа 11

PREDICATES summa(integer,integer)

CLAUSES summa(X,Y):-X<10,Y=X,!.

summa(X,Y):-X1=X div 10,summa(X1,Y1),Z=X mod 10,Y=Y1+Z. Использование предиката ! в описании нерекурсивного правила по-

зволяет избежать здесь переполнения стека.

Существуют проблемы, в которых использование рекурсии особенно выгодно.

Рассмотрим задачу «Ханойская башня» которую, как говорят, придумал в 1883 г. французский математик Люка.

Имеются три стержня, на одном из которых помещены N колец разного диаметра, при этом, чем меньше диаметр кольца, тем выше оно лежит (рис. 1). Например, для четырех колец получается картинка:

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

17

Рис. 1

рекладывания верхнего диска с одного из стержней на другой стержень. При этом больший диск никогда нельзя ставить на меньший диск.

Если ввести обозначения:

рация.

Очевидно можно записать:

(m,a,b) → (m-1,a,c) <a,b> (m-1,c,b) Т. е. для перемещения m-дисков с a на b нужно:

1)Переместить m-1 – диск с a на c (с – вспомогательный стержень).

2)Переместить нижний диск с номером m с a на b.

3)Переместить m-1 – диск с c на b (с – вспомогательный стержень). Здесь возникает рекурсия – целевое действие определяется через

промежуточные действия того же вида.

Например, пусть m = 3, т. е. имеется три кольца. Тогда: (3,1,3)→ (2,1,2)<1,3>(2,2,3)

Окончательно:

<1,3><1,2><3,2><1,3><2,1><2,3><1,3>

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

Существует «восточная легенда» (которую, как говорят, придумал тот же математик Люка), согласно которой в одной из пещер Гималаев три буддийских монаха решают эту задачу для 64 колец. Когда они переложат все кольца, наступит конец света.

18

Решение задачи требует 2n-1 действий. Если считать, что одно действие выполняется за 1 с, то уже для 40 колец должно потребоваться более 2000000 лет, что звучит достаточно оптимистически.

Программа 12 решает задачу «Ханойская башня» на ПРОЛОГе.

Программа 12

DOMAINS

loc =right;middle;left PREDICATES

hanoi(integer)

move(integer,loc,loc,loc)

inform(loc,loc) GOAL

hanoi(5). CLAUSES

hanoi(N):- move(N,left,middle,right). move(1,A,_,C):- inform(A,C),!.

move(N,A,B,C):- N1=N-1, move(N1,A,C,B), inform(A,C), move(N1,B,A,C).

inform(Loc1, Loc2):- nl,write(“Диск с”, Loc1, “ на “, Loc2).

7. ИСПОЛЬЗОВАНИЕ СПИСКОВ

Списки – одна из наиболее часто употребляемых структур в ПРОЛОГе. Список – это набор объектов одного и того же типа. При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми, например:

[1,2,3]

[1.1,1.2,3.6]

[“вчера”,”сегодня”,”завтра”] Элементами списка могут быть любые термы ПРОЛОГа, т.е. атомы,

числа, переменные и составные термы.

Каждый непустой список может быть разделен на голову – первый элемент списка и хвост – остальные элементы списка. Это позволяет всякий список представить в виде бинарного дерева (рис. 2).

У списка, состоящего только из одного элемента, головой является этот элемент, а хвостом – пустой список.

Для использования списка необходимо описать предикат списка.

19

Рис. 2

Например: num([1,2,3]).

Пусть мы хотим описать с помощью списка породы собак.

Программа 13

DOMAINS

dog_list= symbol* /* здесь «*» указывает на список*/ PREDICATES

dogs(dog_list). CLAUSES

dogs([“лайка”,”борзая”,”дог”,”болонка”]). После запроса:

goal: dogs(Х)

будут напечатаны все породы собак, а после запроса: goal: dogs(_,_,_,Х)

получим: Х = болонка.

Операция разделения списка на голову и хвост обозначается с помощью вертикальной черты:

[Head|Tail]

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

print_list([ ]).

print_list([X|Y]) :- write(X),nl, print_list([Y]).

20