3

一般化されたフィボナッチ数列 (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).

...しかし、これはうまくいかないようです。

この方法で初期数を定義することはできませんか、それとも何かひどく間違っていますか? 解決策を求めているわけではありませんが、これを解決するのに役立つアドバイスをいただければ幸いです。

4

6 に答える 6

5

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).
于 2010-05-11T19:58:21.077 に答える
1

X0 と X1 が基本ケース 0 と 1 の値である述語 gfs(X0, X1, N, F) を定義します。

于 2010-05-10T19:43:09.463 に答える
0

ひどく間違ったことをしていると思います...を呼び出すfib(1, X1)と、変数X1は関数fibが返す数値であり、この場合は、基本ケースのために1になりますfib(1, 1).。

于 2010-05-09T18:47:40.793 に答える
0

andを simplefib(N,F1,F2)に置き換えられるように検討してください。fib(Nmin1, Xmin1)fib(Nmin2, Xmin2)fib(Nmin2, Xmin2, Xmin1)

于 2010-05-11T19:01:47.270 に答える
0

基本ケースがなければ、fib/2 には解決策がありません。fib2でどのように呼び出しても。注: 再帰を使用する場合は、少なくとも 1 つの基本ケースが必要です。

于 2010-05-10T08:34:17.703 に答える
0

厳密な意味での解決策ではないかもしれませんが、それでも共有します。おそらく唯一の利益は、これを解くのにコンピューターも電卓も必要ないことを示すことです。トリックを知っていれば、ベアマットで行うことができます。

F_n が F_1=F_2=1 で始まる通常の Fibo シーケンスの n 番目の項である場合、一般化されたシーケンスの 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 を取得します。

于 2010-05-14T19:38:01.787 に答える