Программирование с накопителями

При реализации рекурсии данные помещаются в стек всякий раз, когда выполняется рекурсивный вызов. Чем больше глубина рекурсии, тем больше требуется стековой памяти. Итеративные программы работают в фиксированном объеме памяти, не зависящем от числа итераций. Итеративные вычисления можно смоделировать, используя в рекурсивных определениях с одним рекурсивным вызовом в правой части дополнительные аргументы-переменные для передачи промежуточных значений. Эти переменные называются накопителями ( аккумуляторами ).

ПРОГРАММА 4.

Итеративное определение факториала (вариант 1).

factorial(N,FactN):- fact(N,FactN,1,1).

fact(N,FactN,I,P):- /* накопитель I - аналог счетчика */

I<N /* накопитель P – промежуточное значение факториала*/

I1 is I+1, /* - значение факториала */

P1 is P*I1,

fact(N,FactN,I1,P1).

fact(N,FactN,N,FactN).

ЗАДАНИЕ 3.3

Выполните программу 4 в режиме трассировки. Введите запрос:

?-factorial(3,F).

ПРОГРАММА 5.

Итеративное определение факториала (вариант 2, более эффективный).

factorial(N,FactN):- fact(N,FactN,1).

fact(N,FactN,P):-

N>0,

P1 is P*N,

N1 is N-1,

fact(N1,FactN,P1).

fact(0,FactN,FactN).

ЗАДАНИЕ 3.4

Выполните программу 5 в режиме трассировки. Введите запрос и нарисуйте для него дерево вывода:

?-factorial(4,F).

РЕКУРСИВНЫЕ ОБЪЕКТЫ

Другим типом рекурсии в Прологе является рекурсия по данным.

ПРОГРАММА 6.

Рекурсивное определение списка студентов.

/*группа номер 1,состоящая из студентов 'Шекспир','Мольер','Чехов'*/

kurs(1,gruppa('Шекспир',gruppa('Мольер',gruppa('Чехов',empty)))).

kurs(2,gruppa('Гильберт',gruppa('Эйлер',gruppa('Лейбниц',

gruppa('Кантор',empty))))).

ЗАДАНИЕ 3.5

Запустите программу 6, введите запросы:

?-kurs(1,X).

?-kurs(N,gruppa(X,Y)).

?-kurs(N1,gruppa(X, gruppa(Y,Z))).

ЗАДАНИЕ 3.6

Напишите программу для определения n -го числа Фибоначчи без накопителей и с накопителями. Числа Фибоначчи определяются следующим законом: первые два числа равны единице, а каждое последующее равно сумме двух предыдущих. То есть получим ряд 1,1,2,3,5,8,13,21,34,...

ЗАДАНИЕ 3.7

Напишите программу для определение суммы нечетных (четных) чисел из n первых чисел Фибоначчи.

ЗАДАНИЕ 3.8

Дано число. Проверить, является ли оно суммой нечетных (четных) чисел из n первых чисел Фибоначчи. Найти число n.

ЗАДАНИЕ 3.9

Напишите программу для вычисления функции Аккермана, определенной на множестве пар неотрицательных чисел.