prolog - 用 SICStus Prolog 概括斐波那契数列

Question

我正在尝试为广义斐波那契数列 (GFS) 的查询找到解决方案。问题是：是否有任何 GFS 的第 12 个数字为 885？前 2 个数字可能被限制在 1 到 10 之间。

我已经找到了在从 (1, 1) 开始的序列中找到第 N 个数字的解决方案，其中我明确定义了初始数字。这就是我所拥有的：

fib(1, 1).
fib(2, 1).

fib(N, X) :-
    N #> 1,
    Nmin1 #= N - 1,
    Nmin2 #= N - 2,
    fib(Nmin1, Xmin1),
    fib(Nmin2, Xmin2),
    X #= Xmin1 + Xmin2.

对于提到的查询，我认为以下方法可以解决问题，其中我重用 fib 方法而不明确定义初始数字，因为现在需要动态完成：

fib(N, X) :-
    N #> 1,
    Nmin1 #= N - 1,
    Nmin2 #= N - 2,
    fib(Nmin1, Xmin1),
    fib(Nmin2, Xmin2),
    X #= Xmin1 + Xmin2.

fib2 :-
    X1 in 1..10,
    X2 in 1..10,
    fib(1, X1),
    fib(2, X2),
    fib(12, 885).

...但这似乎不起作用。

以这种方式定义初始数字是不可能的，还是我做错了什么？我不是在寻求解决方案，但是任何可以帮助我解决此问题的建议将不胜感激。

score 5 · Accepted Answer

Under SWI-Prolog:

:- use_module(library(clpfd)).

fib(A,B,N,X):-
    N #> 0,
    N0 #= N-1,
    C #= A+B,
    fib(B,C,N0,X).
fib(A,B,0,A).

task(A,B):-
    A in 1..10,
    B in 1..10,
    fib(A,B,11,885).

score 1 · Accepted Answer

1

定义一个谓词 gfs(X0, X1, N, F)，其中 X0 和 X1 是基本情况 0 和 1 的值。

于 2010-05-10T19:43:09.463 回答

score 0 · Accepted Answer

也许不是严格意义上的解决方案，但我会永远分享它。可能唯一的收获是表明，这既不需要计算机也不需要计算器来解决。如果你知道诀窍，它可以在熊垫上完成。

如果 F_n 是普通 Fibo 序列的第 n 项，从 F_1=F_2=1 开始，那么广义序列的第 n 项将是 G_n = F_{n-2}*a+F_{n- 1}*b。定义 F_{-1}=1, F_0 = 0

（实际上，通过归纳

G_1 = F_{-1}*a+F_0*b = 1*a+0*b=a
G_2 = F_0 * a + F_1 * b = 0*a + 1*b = b
G_{n+1} = F_{n-1} a + F_n b = (F_{n-3} + F_{n-2} )a + (F_{n-2} + F_{n-1}) *b = G_n + G_{n-1}

)

因此 G_12 = F_10 * a + F_11 * b = 55a + 89b。

现在，您可以使用计算机搜索方程 55a + 89b = 885 的解

或者

算一算：

残基 mod 11（解释）：

55a + 89b = 0 + 88b + b = b；885 = 880 + 5 = 80*11 + 5 = 5

所以 b = 5 mod 11，但由于 1 <= b <= 10，b 实际上是 5。89 * 5 = 445 和 885-445 = 440。现在，除以 55 并得到 a=8。

score 0 · Accepted Answer

考虑一下fib(N,F1,F2)，您将能够用 simple替换fib(Nmin1, Xmin1)and 。fib(Nmin2, Xmin2)fib(Nmin2, Xmin2, Xmin1)

score 0 · Accepted Answer

我会说你做错了什么......当你调用fib(1, X1)时，变量 X1 是函数fib将返回的数字，在这种情况下，它将是 1，因为基本情况fib(1, 1).。

score 0 · Accepted Answer

没有基本情况， fib/2 没有解决方案；无论你在 fib2 中如何称呼它。注意：如果使用递归，则至少需要一种基本情况。

prolog - 用 SICStus Prolog 概括斐波那契数列

6 回答 6

Related

Reference