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

Question

我的任务是：

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

• f(0) = 0
• f(1) = 1
• f(n) = f(n-2) + 2*f(n-1)（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.