list - 如何将递归函数的值存储在序言的列表中？

Question

我的任务是:

Given the following definition of function f, create a Prolog program to compute f(i) for all 0 < i < 32.

• f(0) = 0
• f(1) = 1
• f(n) = f(n-2) + 2*f(n-1) for n > 1

到目前为止我的代码是:

problemThree(0, 0).
problemThree(1, 1).
problemThree(N, NF) :-
    N > 1,
    A is N - 2,
    B is N - 1,
    problemThree(A, AF),
    problemThree(B, BF),
    NF is AF + 2*BF.

它正在工作，但显示 N > 20 的值需要很长时间。

请让我知道如何将值存储在列表中以使程序更快。

Answer 1

这是将序列生成为列表的 DCG 方法:

prob3(1, F0, F1) --> [F0, F1].
prob3(N, F0, F1) --> {N > 1, F2 is 2*F1 + F0, N1 is N-1}, [F0], prob3(N1, F1, F2).

prob3(0, [0]).
prob3(N, FS) :-
    phrase(prob3(N, 0, 1), FS).

?- prob3(10, L).
L = [0, 1, 2, 5, 12, 29, 70, 169, 408, 985] ;
false.

?- prob3(169, L).
L = [1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025,
..., 17280083176824678419775054525017769508908307965108250063833395641] ;
false

?- time((prob3(1000, L),false)).
% 3,011 inferences, 0.005 CPU in 0.005 seconds (100% CPU, 628956 Lips)
false.

请注意，对于长列表答案，SWI Prolog 将缩写输出，例如:

?- prob3(20, L).
L = [0, 1, 2, 5, 12, 29, 70, 169, 408|...]

这只是 SWI Prolog 的一种方式，它不会让大量输出弄乱屏幕。在这里，您可以回复 w它将给出整个结果:

?- prob3(20, L).
L = [0, 1, 2, 5, 12, 29, 70, 169, 408|...] [write]   % PRESSED 'w' here
L = [0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428] ;
false

?-

见，Help: I want the whole answer .