Aritalab:Lecture/Algorithm/Fibonacci

From Metabolomics.JP
Jump to: navigation, search

Contents

フィボナッチ数列

定義

フィボナッチ数列を関数の形に書くと、以下のように定義されます。

  • F(0) = 0
  • F(1) = 1
  • F(n+2) = F(n) + F(n+1)

一般解

F(n)=xnと仮定します。これが、F(n+2)=F(n+1)+F(n)を満たすので

xn+2=xn+1+xn

から

x2=x+1

この二次方程式の解をα, βとします。

α = (1 + √5)/2,   β = (1 - √5)/2

αは黄金比とも呼ばれ、OA用紙の縦横比に対応します。 二つの解はいずれも漸化式を満たし、これらの線形和

C1n + C2n

も漸化式を満たします。 ここで初期条件を満たすように、C1, C2を定めます。

C1α+C2β=1,
C1α2+C2β2=1

より、

C1=1/(α-β)=1/√5, C2=-1/(α-β)=-1/√5

すなわち一般項は

F(n) = (1/√5)(αn - βn)

と書けます。

アルゴリズム

定義そのままのアルゴリズム

int Fibonacci(int n) {
  if (n <= 2) return 1;
  int a = Fibonacci(n-1);
  int b = Fibonacci(n-2);
  return (a+b);
}

このアルゴリズムは、Fibonacci(n)関数の実行時間をT(n)と書くと

T(n) = T(n-1)+T(n-2)+ C

を満たしています。ここでcは定数とします。

T(n-1) + T(n-2) + C > 2 T(n-2) + C

ですから、ハノイの塔の解法から

T(n) > C * (2n-1)/2

であることがわかります。つまり数nに対して指数時間かかるアルゴリズムになります。

記憶領域を用いたアルゴリズム

int Fibonacci(int n) {
  int[] memory = new int[n+1];
  memory[0] = memory[1] = 1;
  for(int i=2; i < n+1; i++)
    memory[i] = memory[i-1] + memory[i-2];
  return memory[n];
}

サイズnの記憶領域(memory)を用意するだけで、実行にはnに比例する時間しか要しません。 また、本当に必要な記憶領域はFibonacci(n)の直前2個分しか必要ありません。

もっと速いアルゴリズム

フィボナッチ数の一般形を知っていると仮定します。 α = (1 + √5)/2 とすると

F(n) = (1/√5)(αn - (-α)-n)

であることを知っていたら、αnを高速に求めればよいのでO(log n)ステップで計算可能になります。 ただし、不動小数の計算を必要とするので、計算機で処理する際には薦められません。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox