2

フィボナッチ数列アルゴリズムの反復バージョンを実行していました。私はこの次のコードを見つけました

int Fibonacci(int n)
{
   int f1 = 0;
   int f2 = 1;
   int fn;
   for ( int i = 2; i < n; i++ )
   {
      fn = f1 + f2;
      f1 = f2;
      f2 = fn;
   }
}

頭に浮かんだばかげた質問。上記の関数は、前の2つの数値を追加し、3番目の数値を返し、次の反復に備えて変数を準備します。このようなものになるとどうなりますか。「前の3つの数の合計であるシリーズの数を返す」上記のコードを変更してそのような数を見つける方法u

4

4 に答える 4

6

ヒントとして、上記のアルゴリズムは、いくつかの変数を介して数値を「循環」させることによって機能することに注意してください。上記のコードでは、各ポイントで保存しています

 F_0    F_1
  a      b

次に、ループ内でそれらを1ステップずつ「シフト」します。

 F_1    F_2
  a      b

次に、次のループ反復でそれらを再度「シフト」します。

 F_2    F_3
  a      b

アルゴリズムの合計を更新する場合は、最後の3つの値を次のように保存することを検討してください。

 T_0    T_1    T_2
  a      b      c

次に、それらを再度シフトします。

 T_1    T_2    T_3
  a      b      c

次に、それらを再度シフトします。

 T_2    T_3    T_4
  a      b      c

この直感をコードに変換することは良い練習になるので、それらの詳細はあなたに任せます。

とはいえ、フィボナッチと「トリボナッチ」シーケンスのn番目の項を計算する方法ははるかに高速 です。この記事では、行列の乗算を使用して上記のループよりも高速に項を計算する非常に巧妙なトリックについて説明します。このアルゴリズムを実装するコードがここにあります。

お役に立てれば！

于 2012-06-18T21:38:07.950 に答える
4

再帰が好きです。私をサディストと呼んでください。

static int rTribonacci (int n, int a, int b, int c) {
    if (n == 0) return a;
    return rTribonacci (n-1, b, c, a + b + c);
}

int Tribonacci (int n) { return rTribonacci(n, 0, 0, 1); }
于 2012-06-19T00:58:50.330 に答える
3

私は通常、宿題のように「においがする」質問には答えませんが、他の誰かがすでに答えているので、これは私がすることです。

int Tribonacci(int n)
{
    int last[3] = { 0, 0, 1 }; // the start of our sequence

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[i % 3] + last[(i + 1) % 3] + last[(i + 2) % 3];

    return last[n % 3];
}

ループを次のように変更することで、すべての醜いモジュラー演算（last []配列の循環的な性質を明確にするために残した）を回避するために少し改善することができます。

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[0] + last[1] + last[2];

templatetypedefが言ったように、それはもう少しそして率直に言って最適化することができます、そのようなシーケンスを計算するためのはるかに良い方法があります。

于 2012-06-19T00:18:16.010 に答える
0

再帰を使用する場合は、他のパラメーターは必要ありません。

int FibonacciN(int position)
{   if(position<0) throw new ArgumentException("invalid position");
    if(position==0 || position ==1) return position;
    return FibonacciN(position-1) + FibonacciN(position-2);
}
于 2014-02-07T19:01:40.563 に答える