フィボナッチ反復：n> 50のフィボナッチ数列の第n項を求めるには0

Question

このコードは、n = 46の後に正解を返しません。これを修正してより高いn項を得るにはどうすればよいですか？

public static long fibonacciIterative(long n) 
    { 
     if(n <= 1) { 
    return n; 
      } 
     int x = 1; 
     int y = 1; 
     for(int i=2; i<n; i++) 
      { 
      int z = x; 
      x+= y; 
      y = z; 
      } 
     return x; 
} 

あなたの肯定的なご意見ありがとうございました。私は質問をした後にコードを実行したらすぐにそれを理解しました。

Answer 1

これは、整数のオーバーフローの可能性が高いためです。変数x,yおよびzにはlongを使用してください。

これは少し先に進んでいますが、最終的にはlongの範囲をオーバーフローします。まだ大きい数字が必要な場合はBigIntegerに行きます。

Answer 2

O(1)の複雑さとの最適な方法は、次のようにJavaであるビネーのフォーミュラ、次のようになります。long` `へ 'X'、` y`と `z`を変更することにより、

static long fibonacciBinet(long n) { 
    if (n <= 1) return n; 
    double sqrt5 = Math.sqrt(5); 
    long x = (long) ((Math.pow(1+sqrt5, n)-Math.pow(1-sqrt5, n))/(Math.pow(2, n)*sqrt5)); 

    return x; 
}