Довольно просто сделать рекурсивный вызов в последней подцели последнего предложения. Но как гарантировать, что в любых других вызываемых процедурах нет альтернатив? Команда cut (!) позволяет отвергать все существующие альтернативы. Чтобы установить ее, необходимо использовать директиву компилятора check_determ.
Можно установить badcount3 следующим образом (изменяя его имя в процессе) и оставляя check без изменений:
сutcount3(X):-
write(X), nl,
NewX = X+1,
check(NewX),
!,
cutcount3(NewX).
Команда «cut» «однажды достигнув этой точки, не обращать внимание на альтернативные предложения этого предиката и альтернативные решения предыдущих подцелей, включая данное предложение». Поскольку альтернативы исключаются, стек не нужен и рекурсивный вызов может свободно идти дальше.
«Cut» также эффективен и в badcount2:
cutcount2(X):-
X >= 0, !,
write(X), nl,
NewX = X+1,
cutcount2(NewX).
cutcount2(X):-
write(«X is negative.).
Если «cut» выполняется, компьютер предполагает, что непроверенных альтернатив нет, и не создает стек.
К сожалению, «cut» не сможет помочь с badcount1, которому необходимость стеков не позволяет ничего делать с непроверенными альтернативами.
Единственный способ усовершенствовать badcount1 — представить вычисление таким образом, чтобы рекурсивный вызов приходил в конце предложения.
/* Файл Lab3_5.PRO */
predicates
count(real) % хвостовая рекурсия, которая не истощает память.
/*Три предиката без хвостовой рекурсии. Они истощают запас своей памяти через несколько сотен итераций.*/
badcount1(real)
badcount2(real)
badcount3(real)
/* Следующие два предиката показывают, как bedcount2 и bedcount3 могут быть установлены объявлением «cut» для исключения непроверенных предложений. Эти версии — хвостовая рекурсия. */
cutcount2(real)
cutcount3(real)
check(real)
clauses
count(N):-
write(N), nl,
NewN = N+1,
count(NewN).
/* badcount1:
Рекурсивный вызов — не последний шаг.*/
badcount1(X):-
write(X), nl,
NewX = X+1,
badcount1(NewX),
nl.
/* badcount2:
Предложение не выполняется во время осуществления рекур-
сивного вызова. */
badcount2(X):-
write(X), nl,
NewX = X+1,
badcount2(NewX).
badcount2(X):-
X < 0,
write(«X is negative.»).
/* badcount3:
Непроверенная альтернатива в процедуре, вызванной перед
рекурсивным вызовом. */
badcount3(X):-
write(X), nl,
NewX = X+1,
check(NewX),
badcount1(NewX).
/* cutcount2:
Выполнение этого предложения не завершается во время рекурсивного вызова. */
cutcount2(X):-
X >= 0, !,
write(X),
nl,
NewX = X+1,
cutcount2(NewX).
cutcount2(_):-
write(«X is negative.»).
/* cutcount3:
Непроверенная альтернатива в предложении, вызванном перед рекурсивным вызовом. */
cutcount3(X):-
write(X),
nl,
NewX = X+1,
check(NewX),
!,
cutcount3(NewX).
check(Z):- Z >= 0.
check(Z):- Z < 0.
Заметьте, что badcount2 и badcount3 хуже, чем badcount1, потому что они образуют возвратные точки.
Задание:
1. Создайте программу «советник по транспорту». Выберите либо сеть, состоящую из городов, либо транспортную сеть маршрутов троллейбусов или автобусов в пределах одного города. Вы должны информировать систему о том, откуда и куда Вы собираетесь добраться, а система должна выдавать рекомендации о том, какими поездами, самолетами, автобусами и т.д. следует воспользоваться, чтобы добраться до пункта назначения.
Программа может содержать, например,
а) факты:
путешествие (компания, пункт_отправления, пункт_назначения, вид_транспорта),
б) рекурсивную процедуру «можно_путешествовать», которая определяет отношение между двумя городами: можно совершить путешествие из одного города в другой через любое количество промежуточных пунктов;
2. Напишите программу с хвостовой рекурсией, которая печатает таблицу степеней числа 2, как показано ниже:
N 2^N
— ——
1 2
2 4
3 8
4 16
… …
10 1024
Остановите программу при N = 10.
3. Напишите программу с хвостовой рекурсией, которая допускает ввод числа и способна завершаться двумя способами. Она должна начинаться умножением числа на себя до тех пор, пока не достигнет числа 81 или числа, большего чем 100. Если достигнуто число 81, то печатается «YES», если же число больше 100 — печатается «NO».
4. Индивидуальные задания типа: Вычислить значение ряда
Реализовать с помощью итеративного и рекурсивного алгоритмов.
Замечание: Так как в Прологе нет операции возведения в степень, то
№ 4.1
Дано натуральное число N. Вычислить:
№ 4.2
Дано натуральное число N. Вычислить:
№ 4.3
Дано натуральное число N. Вычислить произведение первых N сомножителей
№ 4.4
Дано натуральное число N. Вычислить:
№ 4.5
Дано действительное число х. Вычислить:
№ 4.6
Даны натуральное п, действительное х. Вычислить:
№ 4.7
Даны действительное число а, натуральное число n. Вычислить:
Р= а(а + 1)… (а + n — 1).
№ 4.8
Даны действительное число а, натуральное число n. Вычислить:
Р= а(а — n)(а – 2n)… (а — n2).
№ 4.9
Даны действительное число а, натуральное число n. Вычислить:
№ 4.10
Дано действительное х. Вычислить:
№ 4.11
Вычислить:
(1 + sin 0,l)(l + sin 0,2)… (1 + sin 10).
№ 4.12
Даны натуральное n, действительное х. Вычислить:
№ 4.13
Дано натуральное n. Вычислить:
S= 1 • 2 + 2 • 3 • 4 +… + n • (n + 1) •… • 2n.
№ 4.14
Дано натуральное число n. Вычислить:
№ 4.15
Дано натуральное число n. Вычислить:
№ 4.16
Дано натуральное число n. Вычислить:
S= 1!+2!+3!+… + n! (n>1).
№ 4.17
Дано натуральное число n. Вычислить:
№ 4.18
Числа Фибоначчи (fn) определяются формулами
f0=f1=1, fn = fn-1 + fn-2, при n=2,3,….
Определить f40.
№ 4.19
Дано натуральное n. Вычислить: у=1• 3• 5•…• (2n — 1).
№ 4.20
Дано натуральное n. Вычислить: y=2• 4• 6•… • (2n).
№ 4.21
Вычислить:
№ 4.22
Вычислить: у= sin 1 + sin l,l + sin l,2 +… sin 2.
№ 4.23
Даны натуральные числа n и k. Вычислить:
№ 4.24
Дано натуральное n. Вычислить
