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

Question

Je travaille sur un devoir, composé 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/Triangular_number. Par exemple: (2, 3) = true; (4, 10) = vrai et cetera.

La première solution utilise la récursivité « ordinaire », et j'avons résolu ce 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 est de résoudre ce en utilisant la récursion arrière/un accumulateur, en utilisant un prédicat triangle/3. Bien que j'aie utilisé un accumulateur dans une autre affectation, 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 quant à la façon de l'utiliser dans ce contexte. Donc, je ne cherche pas un algorithme, je préfère résoudre cela moi-même, mais plus d'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 correspondent à ce que vous écrivez pour chaque prédicat récursif de queue (avec [] au lieu de 0 pour les prédicats de liste).

De là, vous pouvez aller 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 un grand 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 fondamentalement déjà la queue récursif (parce que le appel récursif est la dernière chose à faire) la version avec un accumulateur permet encore d'économiser du temps car vous n'avez pas besoin de la vérification pour Y > 0. Si vous introduisez cette ligne dans le triangle_t prédicat, ils ont exactement les mêmes caractéristiques d'exécution à nouveau:

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 maintenant utiliser le prédicat pour générer le nombre triangulaire n'th.