Упражнения

1. Следующая ниже программа - улучшенная версия вычисления факториа-

ла.

/* Программа CH07EX08.PRO */

predicates

factorial(integer, real)

factorial(integer, real, integer, real)

/* Если числа превосходят 32767 - они объявляются вещественны-

ми */

factorial(N,FactN,NewI,NewP).

clauses

factorial(N, FactN) :-

factorial(N, FactN, 1, 1).

factorial(N, FactN, N, FactN) :- !.

factorial(N, FactN, I, P) :-

NewI = I+1,

NewP = P*NewI,

factorial(N, FactN, NewI, NewP).

Загрузите и выполните эту программу.

2. Напишите программу с хвостовой рекурсией, которая будет работать

как CH07EX02.PRO, но без поиска с возвратом.

3. Напишите программу с хвостовой рекурсией, которая печатает табли-

цу степеней числа 2, как показано ниже:

N 2^N

--- -----

1 2

2 4

3 8

4 16

... ...

10 1024

Остановите программу при N = 10.

4. Напишите программу с хвостовой рекурсией, которая допускает ввод

числа и способна завершаться двумя способами. Она должна начинаться

умножением числа на себя до тех пор, пока не достигнет числа 81 или

числа, большего чем 100. Если достигнуто число 81, то печатается

"YES", если же число больше 100 - печатается "NO".

Рекурсивные структуры данных

Рекурсивными могут быть не только предложения, но и структуры дан-

ных. Турбо Пролог является единственным широко используемым языком прог-

раммирования, который позволяет определить типы рекурсивных данных. Тип

данных является рекурсивным, если он допускает структуры, содержащие та-

кие же структуры, как и они сами.

Наиболее важным рекурсивным типом данных является список, но мы не

будем рассматривать списки в этой главе. Подробности обработки списков,

как встроенного в Пролог средства, мы обсудим в Главе 8. В этой главе мы

определим рекурсивный тип данных, опишем его и используем для написания

удивительно быстрой сортирующей программы.

Структурой вводимого нами типа данных является дерево (Рис.7). Важ-

но, чтобы каждая ветвь дерева сама являлась деревом, поэтому структура

рекурсивна.

|

|

|

Cathy

/ \

/ \

/ \

/ \

/ \

Michael Melody

/ \ / \

/ \ / \

Charles Hazel Jim Eleanor

Рисунок 7.1: Часть фамильного дерева