如何在prolog中的列表中存储递归函数的值

Question

我的任务是：

给定函数f的以下定义，创建Prolog程序来计算所有0<i<32.

• f（0）=0
• f（1）=1
• 对于n>1，f（n）=f（n-2）+2*f（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
?-

看，救命：我想要完整的答案。

Answer 2

无需存储超过前两个数字！

这是我从臀部快速而肮脏的镜头：

p3（N，F）：-（N=：=0->F=0；N=：=1->F=1；N>1->N0是N-2，p3_（N0,0,1，F）)。p3_（N，F0，F1，F）：-F2是F0+2*F1，（N=：=0->F2=F；N0是N-1，p3_（N0，F1，F2，F）)。

示例查询：

？-介于（25，35，N），p3（N，F）之间。N=25，F=1311738121；N=26，F=3166815962；N=27，F=7645370045；N=28，F=18457556052；N=29，F=44560482149；N=30，F=107578520350；N=31，F=259717522849；N=32，F=627013566048；N=33，F=1513744654945；N=34，F=3654502875938；N=35，F=8822750406821。

稍大的东西：

?- p3(111,F).
F = 1087817594842494380941469835430214208491185.
?- p3(123,F).
F = 42644625325266431622582204734101084193553730205.
?- p3(169,F).
F = 17280083176824678419775054525017769508908307965108250063833395641.

足够快吗？

?- time((between(0,1000,N), p3(N,_), false)).
% 2,006,005 inferences, 0.265 CPU in 0.265 seconds (100% CPU, 7570157 Lips)
false.

Answer 3

虽然它比其他答案慢得多，但我喜欢这个具有函数精神的答案：

:- use_module(library(lambda)).
f(N, FN) :-
    cont_f(N, _, FN, _^Y^_^U^(U = Y)).
cont_f(N, FN1, FN, Pred) :-
    (   N < 2 ->
        call(Pred, 0, 1, FN1, FN)
    ;
        N1 is N - 1,
        P = X^Y^Y^U^(U is X + 2*Y),
        cont_f(N1, FNA, FNB, P),
        call(Pred, FNA, FNB, FN1, FN)
    ).

Answer 4

记忆很有用，我用它来加速Erathostenes筛的素数计算

?- time((between(0,1000,N), prob3(N,_), false)).
% 10,939 inferences, 0.011 CPU in 0.012 seconds (99% CPU, 951780 Lips)
:- dynamic memo/2.
prob3(0, 0).
prob3(1, 1).
prob3(N, R) :- memo(N, R), !.
prob3(N, R) :-
    N > 1, N2 is N-2, N1 is N-1, prob3(N2,R2), prob3(N1,R1), R is R2+2*R1, assertz(memo(N, R)).