Prolog 中的高效斐波那契

Question

我正在尝试实现可与 CLP 一起有效使用的斐波那契谓词。

:- module(fibonacci, [fibonacci/2]).

fibonacci(N, F) :-
  ( var(N) ; integer(N) ),
  ( var(F) ; integer(F) ),
  ( var(F) ->
    ( integer(N) ->
      fib_1(N, F), !
    ; fib_3(0, N, F)
    )
  ; ( integer(N) ->
      fib_1(N, F0), F0 = F, !
    ; fib_2(0, F, N0), N0 = N, !
    )
  ).

fib_3(I, J, F) :-
  ( I = J, fib_1(I, F) ) ;
  ( I1 is I + 1, fib_3(I1, J, F) ).

fib_2(I, F, J) :-
  fib_1(I, F0),
  ( F = F0 -> 
    J = I, !
  ; ( F0 > F -> !, fail
    ; I1 is I + 1,
      fib_2(I1, F, J)
    )
  ).

fib_1(0, 0).
fib_1(1, 1).
fib_1(2, 1).
fib_1(N, F) :-
  var(F),
  N > 2,
  ( N mod 2 =:= 0 ->
    N0 is div(N, 2),
    N1 is N0 + 1,
    fib_1(N0, F0),
    fib_1(N1, F1),
    F is F0 * (2 * F1 - F0)
  ; N0 is div(N + 1, 2),
    N1 is N0 - 1,
    fib_1(N0, F0),
    fib_1(N1, F1),
    F is F0 * F0 + F1 * F1 
  ).

这不是最漂亮的代码，但它完成了我想要它做的事情。

?- fibonacci(A, 10).
false.

?- fibonacci(A, 13).
A = 7.

?- fibonacci(12, A).
A = 144.

?- fibonacci(12, 144).
true.

?- fibonacci(12, 145).
false.

?- fibonacci(A, B).
A = B, B = 0 ;
A = B, B = 1 ;
A = 2,
B = 1 ;
A = 3,
B = 2 ;
A = 4,
B = 3 ;
A = B, B = 5 .

要使此查询起作用，缺少什么魔药：

fibonacci(_, B), B #< 1000

它是否完全可以纠正，或者 CLP 是完全不同的野兽，每个与 CLP 兼容的谓词需要理解的不仅仅是 integers 和 vars？

Answer 1

您应该避免在使用 clp(FD) 的算法中使用 !，因为它们不能很好地混合。另外 if-then-else 也可能适得其反。我还会关注在使用 clp.

的算法中使用 var/1

这里有一个使用 clp(FD) 和累加器来避免双重递归的解决方案：

fibonacci(0, 0).
fibonacci(1, 1).
fibonacci(N, F):-
  N #> 1,
  zcompare(C, 2, N),
  fibonacci(C, 2, N, 0, 1, F).
  
fibonacci(=, N, N, F1, F2, F):-
  F #= F1+F2.
fibonacci(<, N0, N, F1, F2, F):-
  N1 #= N0+1,
  F3 #= F1+F2,
  F #> F3,
  zcompare(C, N1, N),
  fibonacci(C, N1, N, F2, F3, F).

此外，对于测试，您应该在调用 fibonacci/2 之前对预期数量 发出约束。所以不用 fibonacci(_, B), B #< 1000. 使用 B #< 1000, fibonacci(_, B).

样本运行：

?- fibonacci(10, F). F = 55. ?- B #< 1000, fibonacci(_, B). B = 0 ; B = 1 ; B = 1 ; B = 2 ; B = 3 ; B = 5 ; B = 8 ; B = 13 ; B = 21 ; B = 34 ; B = 55 ; B = 89 ; B = 144 ; B = 233 ; B = 377 ; B = 610 ; B = 987 ; false.

Prolog 中的高效斐波那契

Efficient Fibonacci in Prolog

prolog

fibonacci

clpfd