6

異常な（私が思うに）問題があります。与えられた数F_n（nの値はわかりません）に対して、F_ {n} = F_ {n-1} + F_ {n-2}となるような数F_0、F_1を見つける必要があります。追加の難しさは、このシーケンスをできるだけ長くする必要があることです（F_nの値nが最も高くなる必要があります）。複数のソリューションが存在する場合は、最小のF_0でこれを実行する必要があります。つまり、「独自の」フィボナッチ数列を生成する必要があります。いくつかの例：

in：F_n = 10; out：F_0 = 0; F_1 = 2;

で：F_n = 17; out：F_0 = 1; F_1 = 5;

で：F_n = 4181; out：F_0 = 0; F_1 = 1;

すべてのシーケンスで観察したこと（「フィボナッチルール」を使用）F_nは次のとおりです。

F_n = Fib_n * F_1 + Fib_ {n-1} * F_0

ここで、Fib_nはn番目のフィボナッチ数です。これは特にフィボナッチ数列に当てはまります。しかし、私はこの観察が何かの価値があるかどうかわかりません。nはわかりません。タスクは、F_1、F_0を見つけることなので、何も得られていないと思います。何か案は？

4

5 に答える 5

3

F n-1 = round（F n /φ）

ここで、φ=（√5+ 1）/2です。

証明は読者の練習問題として残されています;^P

更新これは正しくありません。製図板に戻ります。

アップデート2FnとFn-1から逆算してみましょう。

F n-2 = F n -F n-1
F n-3 = F n-1 -F n-2 = F n-1-（F n -F n-1）= 2F n-1 -F n
F n-4 = F n-2 -F n-3 =（F n -F n-1）-（2F n-1 -F n）= 2F n -3F n-1
F n-5 = F n-3 --F n-4 =（2F n-1 -F n）-（2F n--3F n-1）= 5F n- 1--3F n
F n-6 = F n-4 -F n-5 =（2F n -3F n-1）-（5F n- 1-3F n）= 5F n -8F n-1

パターンに気づきましたか？実際のフィボナッチ数列と最後の2つの数から、数列の任意のメンバーを簡単に計算できます。しかし、私たちは最後のメンバーしか知りません。どうすれば最後のメンバーを知ることができますか？

Fn -1に関して要件Fi>0を書き留めましょう。

F n - 2 = Fn -Fn-1 >0⇒Fn -1 <Fn F n -3 = 2Fn -1 - Fn >0⇒Fn -1 > Fn / 2 F n -4 = 2Fn -3Fn - 1⇒Fn -1 <2Fn / 3 F n -5 = 5Fn - 1-3Fn⇒Fn - 1 > 3Fn / 5


したがって、実際のフィボナッチ数列の書面でF n-1に一連の境界があり、それぞれが前の数列よりも厳密です。まだ満足できる最後の境界は、最長のシーケンスに対応するFn -1を決定します。最後の境界を満たす数値が複数ある場合は、シーケンスの長さが偶数か奇数かに応じて、最小または最大のいずれかを使用します。

たとえば、F n = 101の場合、
101 * 5/8 <F n-1 <101 *8/13⇒Fn -1 =63

以前の（誤った）解決策は、F n-1 = 62を意味します。これは近いですが、葉巻はありません。

于 2012-04-14T16:41:13.657 に答える
2

何を探しているのかわかりません。あなたが言及する再帰シリーズは次のように定義されます：

Fn = F{n-1} + F{n-2}

明らかに、凝視値が何でもよい場合は、任意にを選択できます。F{n-1}これにより、が得られF{n-2} ( = Fn=F{n-1})ます。それを知っているとF{n-1} = F{n-2} + F{n-3}、F{n-3}から計算できるようになりますF{n-1} and F{n-2}。これは、数値を無限大までさかのぼることができることを意味します。したがって、「最長の」シーケンスはなく、有効なシーケンスは無限にあります。

F{n}ある意味で、初期値を使用して逆フィボナッチ数列を計算していますF{n-1}。ここでF{i} = F{i+2}-F{i+1}、はi永久に減少します

更新：すべてF{i}が非負の整数である結果にソリューションスペースを制約しようとしている場合は、ほんの一握りの（ほとんどの場合シングルトン）ソリューションしか得られません。

元のフィボナッチ数（Fib{i}）を計算すると、すぐにF{n} < Fib{i-1};が得られます。明らかに、これ以上先に進む必要はありません。次に、とのすべての可能な組み合わせを試すことができます-F{0}非負のとの可能性は有限です（明らかに除外することができます）。次に、平等を満たすものの中でどれが最も高いかを確認します-あなたは同様に得ますF{1}F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0}F{0}F{1}F{0}=F{1}=0iF{0}F{1}

于 2012-04-14T14:31:46.693 に答える
2

あなたの方程式

F_n = Fib_n * F_1 + Fib_{n-1} * F_0

は2つの変数との線形ディオファントス方程式です 。リンクは、解集合の記述を計算するための効率的なアルゴリズムを示します。これにより、解が存在する場合は、および最小で解を見つけることができます。その後、解決策がないことがわかるまで推測を試みることができます。このアプローチは、の多項式です。F_1F_0F_1 >= 0F_0 >= 0F_0n = 0, 1, ...log(F_n)

于 2012-04-14T14:52:26.230 に答える
2

F_n = Fib_n * F_1 + Fib_ {n-1} * F_0

ここで、Fib_nはn番目のフィボナッチ数です。これは特にフィボナッチ数列に当てはまります。しかし、私はこの観察が何かの価値があるかどうかわかりません。nはわかりません。タスクは、F_1、F_0を見つけることなので、何も得られていないと思います。

さて、あなたは最長のシーケンスを探しています、これはあなたが最大化したいことを意味しますn。

フィボナッチ数のルックアップテーブルを作成します。テーブルの前のエントリがであるnような最大のものから始めます。現在、変数はとだけです。線形ディオファントス方程式を解きます。解決策があれば、完了です。そうでない場合は、1ずつ減らして、解決策が見つかるまで再試行してください。Fib_n <= F_nfib_n{n-1}F_1F_0n

注：ソリューションがあるので、ソリューションは常に存在F_2 = 1 * F_1 + 0 * F_0しますF_2 = F_1。

于 2012-04-14T14:54:12.707 に答える
0

行列を使用してフィボナッチ数の計算を模倣します（ただし、初期値は異なります）。[[0 1] [1 1]]をkに累乗すると、[F_ {n}、F_ {n + 1}]を掛けると、[F_ {n + k}、F_ {n + 1+k}]が得られます。

行列の累乗はO（log n）であるため（整数の乗算がO（1）であると仮定）、行列係数が計算を支配し始めるまで、O（log n）時間で計算全体を実行できます。

あなたが働いている数がたまたまどれくらい大きいかはわかりませんが、この行列のn乗は[[F_ {n-1} F_n] [F_n F_ {n+1}]]です。そしてlog（F_n）〜n / 5（したがって、10億番目のフィボナッチ数は約2億桁になります）。

于 2016-10-07T01:16:36.963 に答える