Пролог, треугольные числа, аккумуляторы и хвостовая рекурсия - PullRequest
Новая
       45

Пролог, треугольные числа, аккумуляторы и хвостовая рекурсия

1 голос
/ 19 февраля 2011

Я работаю над домашним заданием, состоящим из 2 частей. Первый - написать программу Prolog, которая проверяет, принадлежит ли определенная пара X, Y a http://en.wikipedia.org/wiki/Triangular_number. Например: (2, 3) = true; (4, 10) = правда и так далее.

Первое решение использует «обычную» рекурсию, и я решил это следующим образом: 

triangle(0, 0).
triangle(X, Y) :- X > 0, Y > 0, A is X - 1, B is Y - X, triangle(A, B).

Вторая часть заключается в том, чтобы решить эту проблему с помощью хвостовой рекурсии / аккумулятора, используя предикат треугольника / 3. Хотя я использовал аккумулятор в другом задании, в котором его использование было совершенно очевидным, поэтому у меня есть общее представление о том, как использовать аккумулятор, я весьма озадачен тем, как его использовать в этом контексте.

Итак, я не ищу алгоритм, я бы скорее решил его сам, но больше практического совета о том, как применять аккумулятор в этом контексте.

1 Ответ

3 голосов
/ 19 февраля 2011

Начало всегда одинаковое, т. Е. Первые три строки - это то, что вы пишете для каждого хвостового рекурсивного предиката (с [] вместо 0 для предикатов списка).

Оттуда вы можете идти без особых изменений: 

 triangle_t(X, Y) :- triangle_t(X, 0, Y).
 triangle_t(0, Y, Y).
 triangle_t(X, Acc, Y) :-
          X > 0,
          A is X - 1,
          AccX is Acc + X,
          triangle_t(A, AccX, Y).

Вот немного статистики для большого X: 

64 ?- time(triangle(1000000,500000500000)).
% 4,000,000 inferences, 0.50 CPU in 0.52 seconds (96% CPU, 8012769 Lips)
true.

65 ?- time(triangle_t(1000000,500000500000)).
% 3,000,001 inferences, 0.41 CPU in 0.44 seconds (92% CPU, 7396405 Lips)
true.

Итак, в то время как ваш собственный предикат в основном уже хвостовой рекурсивен (поскольку рекурсивный вызов - последнее, что нужно сделать), версия с аккумулятором все еще экономит время, поскольку вам не нужна проверка для Y > 0. Если вы введете эту строку в предикат triangle_t, они снова будут иметь точно такие же характеристики времени выполнения: 

67 ?- time(triangle_t(1000000,500000500000)).
% 4,000,001 inferences, 0.53 CPU in 0.53 seconds (100% CPU, 7541432 Lips)
true.

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

...