77

劣線形時間でn番目のフィボナッチ数を計算するアルゴリズムはありますか？

4

16 に答える 16

101

ピルシーの行列累乗への言及から、行列の

M = [1 1]
    [1 0]

それから

fib ( n ) = M n 1,2

乗算を繰り返して行列を累乗するのはあまり効率的ではありません。

行列累乗への 2 つのアプローチは、O ( ln n ) ステップでM nを生成する分割統治法、または一定時間である固有値分解ですが、浮動小数点の精度が制限されているためエラーが発生する可能性があります。

浮動小数点実装の精度よりも正確な値が必要な場合は、次の関係に基づいて O ( ln n ) アプローチを使用する必要があります。

M n = ( M n /2 ) 2 nが偶数の場合
   = M · M n -1 nが奇数の
場合

Mの固有値分解により、 Λが対角であり、

 M   = U  Λ  U -1  
 M n = ( U  Λ  U -1 ) n 
    = U  Λ  U -1  U  Λ  U -1  U  Λ  U -1 ... n 回
    = U  Λ  Λ  Λ ... U -1  
    = U  Λ  n  U -1
対角行列Λをn乗することは、 Λの各要素をn乗するという単純な問題である ため、 Mをn乗する O(1) メソッドが得られます。ただし、Λの値は整数ではない可能性が高いため、何らかのエラーが発生します。

2x2 行列のΛを次のように定義します。

Λ = [ λ 1 0 ]
  = [ 0 λ 2 ]

各λを見つけるために、次を解きます

| | M - λ I | = 0

を与える

| | M - λ I | = -λ ( 1 - λ ) - 1

λ² - λ - 1 = 0

二次式を使用して 

λ = ( -b ± √ ( b² - 4ac ) ) / 2a
     = ( 1 ± √5 ) / 2
 { λ 1 , λ 2 } = { Φ, 1-Φ } ここで、Φ = ( 1 + √5 ) / 2

ジェイソンの答えを読んだことがあれば、これがどこに行くのかがわかります。

固有ベクトルX 1およびX 2を解く:

X 1 = [ X 1,1 , X 1,2 ]の場合

 M。 _ X 1 1 = λ 1 X 1

 X 1,1 + X 1,2 = λ 1  X 1,1 
 X 1,1       = λ 1  X 1,2

=>
 X 1 = [ Φ, 1 ]
  X 2 = [ 1-Φ, 1 ]

これらのベクトルはUを与えます:

U = [ X 1,1 , X 2,2 ]
    [ X 1,1、X 2,2 ]

  = [ Φ, 1-Φ ]
    [ 1, 1 ]

Uを使用して反転

A    = [ ab ]
      [ CD ]
=>
A -1 = ( 1 / | A | ) [ d -b ]
                   [ -ca ]

したがって、U -1は次のように与えられます。

U -1 = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
                               [ -1Φ ]
U -1 = ( √5 ) -1   [ 1 Φ-1 ]
               [ -1Φ ]

サニティーチェック：

UΛU -1 = ( √5 ) -1 [ Φ 1-Φ ] . [Φ0]。【1Φ-1】
                     [ 1 1 ] [ 0 1-Φ ] [ -1 Φ ]

Ψ = 1-Φ、もう一方の固有値とする

Φ は λ²-λ-1=0 の根なので
だから -ΨΦ = Φ²-Φ = 1
および Ψ+Φ = 1

UΛU -1 = ( √5 ) -1 [Φ Ψ ] . [Φ0]。[ 1 -Ψ ]
                 [ 1 1 ] [ 0 Ψ ] [ -1 Φ ]

       = ( √5 ) -1 [Φ Ψ ] . [ Φ -ΨΦ ]
                 [ 1 1 ] [ -Ψ ΨΦ ]

       = ( √5 ) -1 [Φ Ψ ] . [Φ1]
                 [ 1 1 ] [ -Ψ -1 ]

       = ( √5 ) -1 [ Φ²-Ψ² Φ-Ψ ]
                  [ Φ-Ψ 0 ]

       = [ Φ+Ψ 1 ]    
         [ 1 0 ]

       = [ 1 1 ]
         [ 1 0 ]

       = M

したがって、サニティチェックは保持されます。

これで、 M n 1,2を計算するために必要なものがすべて揃いました。

M n = U Λ n U -1 
   = ( √5 ) -1 [Φ Ψ ] . [Φ n   0 ] . [ 1 -Ψ ]
              [ 1 1 ] [ 0 Ψ n ] [ -1 Φ ]

   = ( √5 ) -1 [Φ Ψ ] . [ Φ n   -ΨΦ n ]
              [ 1 1 ] [ -Ψ n    Ψ n Φ ]

   = ( √5 ) -1 [Φ Ψ ] . [ Φ n    Φ n -1 ]
              [ 1 1 ] [ -Ψ n   -Ψ n -1 ] ΨΦ = -1 として

   = ( √5 ) -1 [ Φ n +1 -Ψ n +1       Φ n -Ψ n ]
              [ Φ n -Ψ n       Φ n -1 -Ψ n -1 ]

それで

 fib ( n ) = M n 1,2 
        = (Φ n - (1-Φ) n ) / √5

これは、他の場所で与えられた式と一致します。

これは再帰関係から導き出すことができますが、エンジニアリング コンピューティングとシミュレーションでは、大きな行列の固有値と固有ベクトルを計算することは重要な作業です。これにより、連立方程式の安定性と調和が得られるだけでなく、行列を効率的に高べき乗にすることができるからです。

于 2009-10-06T17:00:58.227 に答える
66

番目のnフィボナッチ数は、

f(n) = Floor(phi^n / sqrt(5) + 1/2)

どこ

phi = (1 + sqrt(5)) / 2

+原始的な数学演算 ( 、-、*および/) がであると仮定すると、O(1)この結果を使用して時間内のnth フィボナッチ数を計算できます (式の累乗のため)。O(log n)O(log n)

C# の場合:

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
于 2009-10-06T13:20:18.563 に答える
57

正確な数値 (int/float ではなく「bignum」) が必要な場合は、

それは不可能だ！

上記のように、フィボナッチ数の公式は次のとおりです。

fib n = フロア (ファイn /√5 + 1 / 2 )

fib n ~= ファイn /√5

は何桁fib nですか？

numDigits (fib n) = log (fib n) = log (phi n /√5) = log phi n - log √5 = n * log phi - log √5

numDigits (fib n) = n * const + const

お(ん)です

要求された結果はO ( n ) であるため、 O ( n ) 時間未満で計算することはできません。

答えの下位桁のみが必要な場合は、行列累乗法を使用して準線形時間で計算できます。

于 2009-10-11T08:54:09.737 に答える
34

SICPの演習の 1 つはこれに関するもので、ここで説明されている答えがあります。

命令型スタイルでは、プログラムは次のようになります。

関数 Fib ( count )
     a ← 1
     b ← 0
     p ← 0
     q ← 1

    While  count > 0 Do 
        If Even( count ) Then 
             p ← p ² + q ²
              q ← 2 pq + q ²
              count ← count ÷ 2
         Else 
             a ← bq + aq + ap 
             b ← bp + aq 
             count ← count - 1
         End If
    終了

    Return  b 
End 関数
于 2009-10-06T14:45:25.853 に答える
24

整数の行列を累乗することによっても行うことができます。マトリックスがある場合

    / 1  1 \
M = |      |
    \ 1  0 /

thenが行列の添字で、が行列の累乗である場合、 は 番目のフィボナッチ数に(M^n)[1, 2]等しくなります。固定サイズの行列の場合、正の整数べき乗への累乗は、実数と同じ方法で O(log n) 時間で実行できます。n[]^

編集:もちろん、必要な回答の種類によっては、一定時間のアルゴリズムで回避できる場合があります。他の式が示すように、n第 フィボナッチ数は で指数関数的に増加しnます。64 ビットの符号なし整数を使用しても、94 エントリのルックアップ テーブルだけで範囲全体をカバーできます。

2番目の編集:最初に固有分解で行列指数を実行することは、以下のJDunkerlyのソリューションとまったく同じです。この行列の固有値は(1 + sqrt(5))/2と(1 - sqrt(5))/2です。

于 2009-10-06T13:46:38.193 に答える
5

ウィキペディアには閉じた形のソリューションがあります http://en.wikipedia.org/wiki/Fibonacci_number

またはC＃で：

    public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) / 2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
        return (int)fn;
    }
于 2009-10-06T13:18:35.910 に答える
4

非常に大きなものでは、この再帰関数が機能します。次の式を使用します。

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

大きな整数を操作できるライブラリが必要です。https://mattmccutchen.net/bigint/の BigInteger ライブラリを使用します。

フィボナッチ数の配列から始めます。fibs[0]=0、fibs[1]=1、fibs[2]=1、fibs[3]=2、fibs[4]=3 などを使用します。この例では、最初の 501 の配列を使用します（0を数えます）。最初の 500 個のゼロ以外のフィボナッチ数は、http: //home.hiwaay.net/~jalison/Fib500.htmlで確認できます。適切な形式にするには少し編集が必要ですが、それほど難しいことではありません。

次に、この関数 (C) を使用して任意のフィボナッチ数を見つけることができます。

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) // Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) // numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else // numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

これを 25,000 番目のフィボナッチ数などでテストしました。

于 2013-12-26T22:43:35.247 に答える
3

これは、log(n) 回再帰する私の再帰バージョンです。再帰的な形で読むのが最も簡単だと思います：

def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

fib(n),fib(n-1)n が奇数の場合はを使用して計算できfib(n-1),fib(n-2)、n が偶数の場合は をfib(n),fib(n-1)使用して計算できるため、機能しますfib(n/2),fib(n/2-1)。

基本ケースと奇数ケースはシンプルです。偶数の場合を導き出すには、a、b、c を連続するフィボナッチ値 (例: 8,5,3) として開始し、a = b+c で行列に書き込みます。知らせ：

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

そこから、最初の 3 つのフィボナッチ数の行列に、連続する 3 つのフィボナッチ数の行列を掛けると、次の数に等しいことがわかります。したがって、次のことがわかります。

      n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

そう：

      2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

右辺を簡約すると、偶数の場合になります。

于 2014-06-10T14:26:44.253 に答える
1

Rを使用

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765
于 2010-07-17T12:16:39.310 に答える
1

固定小数点演算は不正確です。Jason の C# コードは、n = 71 (308061521170129 ではなく 308061521170130) 以降に対して間違った答えを返します。

正解を得るには、計算代数システムを使用します。Sympy はそのような Python 用のライブラリです。http://live.sympy.org/にインタラクティブなコンソールがあります。この関数をコピーして貼り付けます

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

次に、計算します

>>> f(10)
55

>>> f(71)
308061521170129

を調べてみてくださいphi。

于 2013-08-07T10:40:50.427 に答える
0

ここで分割統治アルゴリズムを参照してください

リンクには、この質問に対する他の回答のいくつかで言及されている行列累乗の疑似コードがあります。

于 2013-08-07T06:12:28.093 に答える