使用 SICStus Prolog 推广斐波那契数列

发布于 2024-09-01 06:25:25 字数 756 浏览 12 评论 0原文

我正在尝试寻找广义斐波那契序列（GFS）查询的解决方案。问题是：是否有第 12 个数字为 885 的 GFS？最初的 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).

...但这并不似乎有效。

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

原文

I'm trying to find a solution for a query on a generalized Fibonacci sequence (GFS). The query is: are there any GFS that have 885 as their 12th number? The initial 2 numbers may be restricted between 1 and 10.

I already found the solution to find the Nth number in a sequence that starts at (1, 1) in which I explicitly define the initial numbers. Here is what I have for this:

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.

For the query mentioned I thought the following would do the trick, in which I reuse the fib method without defining the initial numbers explicitly since this now needs to be done dynamically:

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).

... but this does not seem to work.

Is it not possible this way to define the initial numbers, or am I doing something terribly wrong? I'm not asking for the solution, but any advice that could help me solve this would be greatly appreciated.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

放低过去 2024-09-08 06:25:25

在 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).

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).

回复收藏 0 原文

吐个泡泡 2024-09-08 06:25:25

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

回复收藏 0 原文

芸娘子的小脾气 2024-09-08 06:25:25

我想说你正在做一些非常错误的事情......
当您调用 fib(1, X1) 时，变量 X1 是函数 fib 将返回的数字，在本例中，它将是 1，因为基数案例 fib(1, 1).。

回复收藏 0 原文

巷雨优美回忆 2024-09-08 06:25:25

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

回复收藏 0 原文

祁梦 2024-09-08 06:25:25

考虑使用 fib(N,F1,F2)，这样您就可以替换 fib(Nmin1, Xmin1) 和 fib(Nmin2, Xmin2) 使用简单的 fib(Nmin2, Xmin2, Xmin1)。

回复收藏 0 原文

如若梦似彩虹 2024-09-08 06:25:25

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

如果 F_n 是普通斐波那契数列的第 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_nb = (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 的解

，或者

进行数学计算：

Residues 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。