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

Я работаю над домашним заданием, состоящим из 2-х частей. Первый - написать программу на Прологе, которая проверяет, принадлежит ли определенная пара X, Y к 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. Хотя я использовал аккумулятор в другом задании, в котором использование было довольно очевидным, поэтому у меня есть общее представление о том, как использовать аккумулятор, я очень озадачен тем, как использовать его в этом контексте.

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


accumulator triangular prolog tail-recursion
person Oxymoron    schedule 19.02.2011    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Начало всегда одно и то же, т.е. первые три строки - это в основном то, что вы пишете для каждого хвостового рекурсивного предиката (с [] вместо 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-го треугольного числа.

person Felix Dombek    schedule 19.02.2011
comment
Ах, спасибо тебе за это. Мне было интересно узнать о хвостовой рекурсивности моего «нормального» рекурсивного решения, поскольку, как вы говорите, я вызываю треугольник / 2 после выполнения арифметических операций. Спасибо, что указали на этот предикат времени :) - person Oxymoron; 19.02.2011