1

私は 2 つの部分からなる宿題に取り組んでいます。1 つ目は、特定のペア X、Y がhttp://en.wikipedia.org/wiki/Triangular_numberに属しているかどうかをチェックする Prolog プログラムを作成することです。例: (2, 3) = true; (4, 10) = true など。

最初の解決策は「通常の」再帰を使用し、私はこれを次のように解決しました:

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

2 番目の部分は、三角形/3 述語を使用して、末尾再帰/アキュムレータを使用してこれを解決することです。私は別の割り当てでアキュムレータを使用しましたが、その使用は非常に明白でした。そのため、アキュムレータの一般的な使用方法については理解していますが、このコンテキストでの使用方法については非常に困惑しています。

したがって、私はアルゴリズムを探しているのではなく、むしろ自分で解決したいと思っていますが、このコンテキストでアキュムレータを適用する方法についてのより実用的なアドバイスです。

4

1 に答える 1

3

先頭は常に同じです。つまり、最初の 3 行は基本的に、すべての末尾再帰述語 ( for リスト述語の[]代わりに aを使用) に対して記述するものです。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 番目の三角数を生成できることにも注意してください。

于 2011-02-19T14:32:07.527 に答える