Prolog, nombres triangulaires, accumulateurs et récursivité de la queue

Question

Je travaille sur une affectation de devoirs, composée de 2 parties. La première consiste à écrire un programme Prolog qui vérifie si une certaine paire x, y appartient à un http://en.wikipedia.org/wiki/tangular_number. Par exemple: (2, 3) = true; (4, 10) = True et cetera.

La première solution utilise une récursivité «ordinaire», et j'ai résolu ceci comme ceci:

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

La deuxième partie consiste à résoudre ceci en utilisant une récursivité de queue / un accumulateur, en utilisant un prédicat triangle / 3. Bien que j'aie utilisé un accumulateur dans une autre assignation, dans laquelle l'utilisation était assez évidente, j'ai donc une idée générale de la façon d'utiliser un accumulateur, je suis assez perplexe sur la façon de l'utiliser dans ce contexte.

Donc, je ne cherche pas un algorithme, je préfère de loin le résoudre moi-même, mais plus un conseil pratique sur la façon d'appliquer un accumulateur dans ce contexte.

Answer 1

Le début est toujours le même, c'est-à-dire que les trois premières lignes sont essentiellement ce que vous écrivez pour chaque prédicat récursif de queue (avec un [] au lieu d'une 0 pour les prédicats de la liste).

De là, vous pouvez continuer sans beaucoup de changements:

 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).

Voici quelques statistiques pour les grands 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.

Ainsi, alors que votre propre prédicat est essentiellement déjà récursif à queue (parce que l'appel récursif est la dernière chose à faire), la version avec un accumulateur gagne toujours du temps car vous n'avez pas besoin du chèque pour Y > 0. Si vous introduisez cette ligne dans le triangle_t prédicat, ils ont à nouveau exactement les mêmes caractéristiques d'exécution:

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

Notez également que vous pouvez désormais utiliser le prédicat pour générer le numéro triangulaire n'h.