代码之家 › 专栏 › 技术社区 › Christophe Herreman

用SICStus-Prolog推广Fibonacci序列

clpfd sicstus-prolog fibonacci prolog

Christophe Herreman · 技术社区 · 15 年前

我已经找到了在一个从(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(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).

... 但这似乎行不通。

用这种方法来定义初始值是不可能的,还是我做错了什么?我不是在寻求解决办法,但任何能帮我解决问题的建议都将不胜感激。

6 回复 | 直到 12 年前

ony 15 年前

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

starblue 15 年前

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

do_the_math 15 年前

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

如果F是普通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
a+F\

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

或者

explanation ):

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

Jivings 15 年前

我觉得你做错了什么事。。。当你打电话的时候 fib(1, X1) ,变量X1是函数 fib 将返回,在这种情况下,它将是1,因为基本情况 fib(1, 1).

Michael 15 年前

注意:如果使用递归,则至少需要一个基本情况。

ony 15 年前

fib(N,F1,F2) 所以你可以替换 fib(Nmin1, Xmin1) 和 fib(Nmin2, Xmin2) 用简单的 fib(Nmin2, Xmin2, Xmin1)