gpt4 book ai didi

prolog - CLP(FD)-ying斐波那契卢卡斯数的同时递归可能吗?

转载 作者:行者123 更新时间:2023-12-04 04:24:51 25 4
gpt4 key购买 nike

在有些instances中,可以对递归谓词进行CLP(FD)处理,其好处是谓词可以双向转换。这种方法的局限性是什么?例如,以下computation CLP(FD)-fied是否可以:

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 realization从n到Fn已经起作用。是否可以将其转换为保留快速递归并同时使其双向进行的CLP(FD)程序,例如找出Fn = 377的索引n?如果是,怎么办?如果不是,为什么呢?

再见

最佳答案

是的,可以通过约束值来完成。您也可以将递归更改为尾递归,尽管不需要获取解决方案:

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未实例化时,可以对其进行修改以生成用于增加 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.

注意,在不同的Prolog解释器之间,CLP(FD)的性能可能有很大差异。有趣的是,在SWI Prolog中,版本7.1.33暂时具有处理尾部递归情况的功能。

关于prolog - CLP(FD)-ying斐波那契卢卡斯数的同时递归可能吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36264421/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com