CLP（FD）-ying 递归求解 Fibonacci Lukas 数列是否可行？

Question

CLP（FD）-ying 递归求解 Fibonacci Lukas 数列是否可行？

9

有一些实例可以使用递归谓词进行CLP(FD)转换，从而使谓词变得双向。这种方法的限制是什么？例如，以下计算是否可以进行CLP(FD)转换：

Fn: n-th Fibonacci Number
Ln: n-th Lucas Number (starting with 2)

通过这个双重递归步骤：

F2n = Fn*Ln
L2n = (5*Fn^2+Ln^2)//2

而这是递增的递归步骤：

Fn+1 = (Fn+Ln)//2
Ln+1 = (5*Fn+Ln)//2

传统Prolog 实现已经能处理从n到Fn的问题。是否可以将其转换为CLP（FD）程序，同时保留快速递归，并且使其双向，例如找出Fn=377时的索引n？如果可以，如何实现？如果不行，为什么？

再见

- user502187

fibluc/3的运行速度大约比fib/2快20%。这可能是因为fib/2使用了call/n和类似教科书的编程风格。请查看你的答案中的注释。但我猜想两种算法都会遇到相同的CLP（FD）问题。 - user502187

现在我仔细一看，似乎这是不同外观的相同算法。我将删除我的答案。 - user1812457

@Boris 我认为你的 fib/2 确实不同，它是一个众所周知的斐波那契数算法，不会在计算过程中生成卢卡斯数。参见这里：https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form 但我猜它也是通过加倍和递增来实现的。 - user502187

1

是的，确实，这就是我想表达的意思。 - user1812457

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lurker · Accepted Answer

是的，可以通过限制值来完成。您还可以将递归移动为尾部递归，但这不是解决方案所必需的：

fibluc(0, 0, 2).
fibluc(1, 1, 1).
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 1,
    M #= N-1,
    F #= (F1 + L1) // 2,
    L #= (5*F1 + L1) // 2,
    fibluc(M, F1, L1).
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 0,
    M #= N // 2,
    F #= F1 * L1,
    L #= (5*F1*F1 + L1*L1) // 2,
    fibluc(M, F1, L1).

将产生：

?- fibluc(10, X, Y).
X = 55,
Y = 123 ;
false.

?- fibluc(N, 55, Y).
N = 10,
Y = 123 ;
false.

?- fibluc(N, X, 123).
N = 10,
X = 55 ;
false.

?- fibluc(N, 55, 123).
N = 10 ;
false.

?- fibluc(N, 55, 125).
false.

?- fibluc(N, X, Y).
N = X, X = 0,
Y = 2 ;
N = X, X = Y, Y = 1 ;
N = 3,
X = 2,
Y = 4 ;
N = 7,
X = 13,
Y = 29 ;
N = 15,
X = 610,
Y = 1364 ;
N = 31,
X = 1346269,
Y = 3010349 ;
N = 63,
X = 6557470319842,
Y = 14662949395604 ;
...

这可以被修改以生成对于未实例化的 N 增加值的结果。这里有一个在 Linux 下使用 SWI Prolog 7.1.33 运行的计时、复合查询示例：

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).
% 11,337,988 inferences, 3.092 CPU in 3.100 seconds (100% CPU, 3666357 Lips)
X = 354224848179261915075,
Y = Z, Z = 792070839848372253127,
N = 100 ;
% 1,593,620 inferences, 0.466 CPU in 0.468 seconds (100% CPU, 3417800 Lips)
false.

?-

使用SWI Prolog 7.2.3版本和相同的代码以及复合查询时，代码需要运行非常长的时间。我等待了至少15分钟仍未终止，现在它还在运行中...我可能会在明天检查一下:)。然而，我已经重新排列了以上代码，将递归调用移回到原始代码所在的位置，如下所示：

fibluc(0, 0, 2).
fibluc(1, 1, 1).
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 1,
    M #= N-1,
    fibluc(M, F1, L1),
    F #= (F1 + L1) // 2,
    L #= (5*F1 + L1) // 2.
fibluc(N, F, L) :-
    N in 2..1000,        % Pick a reasonable value here for 1000
    [F, L] ins 1..sup,
    N rem 2 #= 0,
    M #= N // 2,
    fibluc(M, F1, L1),
    F #= F1 * L1,
    L #= (5*F1*F1 + L1*L1) // 2.

在这种情况下，返回了良好的结果。

?- time((fibluc(100, X, Y), fibluc(N, X, Z))).
% 10,070,701 inferences, 3.216 CPU in 3.222 seconds (100% CPU, 3131849 Lips)
X = 354224848179261915075,
Y = Z, Z = 792070839848372253127,
N = 100 ;
% 1,415,320 inferences, 0.493 CPU in 0.496 seconds (100% CPU, 2868423 Lips)
false.

请注意，CLP（FD）的性能在不同的Prolog解释器之间可能会有很大的差异。有趣的是，在SWI Prolog中，处理尾递归案例的能力在7.1.33版本时暂时存在。