Aritalab:Lecture/Algorithm/Fibonacci

From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
Jump to: navigation, search
m (記憶領域を用いたアルゴリズム)
m (記憶領域を用いたアルゴリズム)
Line 83: Line 83:
 
   return tmp;
 
   return tmp;
 
  }
 
  }
 +
 +
実行例
 +
> Fibonacci(30)
 +
> 1346269  (F_{31} に相当)
 +
> Fibonacci(31)
 +
> 2178309
 
</pre>
 
</pre>
  

Revision as of 11:24, 11 July 2013

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

両辺を xn で割ります。

x2=x+1

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

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

αは黄金比とも呼ばれ、名刺の縦横比に対応します。

黄金比
Wikipediaによるとパルテノン神殿やピラミッドにも出てくる数字だそうです。黄金比の長方形から短辺を一辺とする正方形を取り除くと、残りの長方形も黄金比になっています。

二つの解はいずれも漸化式を満たし、これらの線形和

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 == 0) return 0;
  if (n == 1) 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 に対し、指数時間かかるアルゴリズムになります。 これでは Fibonacci(30) を求めることすらできないでしょう。

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

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

サイズnの記憶領域(memory)を用意するだけで、実行には n に比例する時間しか要しません。 これを線形時間アルゴリズムといいます。 上のプログラムは、n に比例するサイズの記憶領域を取っていますが、次のプログラムは Fibonacci(n) の直前2個分しか必要ありません。 (こちらは入力を n とすると n+1 番目のフィボナッチ数を返します。)

 int Fibonacci(int n) {
   int num1 = 1, num2 = 1, tmp = 1;
   for(int i = 1; i < n; i++) {
     tmp = num1 + num2;
     num1 = num2;
     num2 = tmp;
   }
   return tmp;
 }

実行例
> Fibonacci(30)
> 1346269  (F_{31} に相当)
> Fibonacci(31)
> 2178309

もっと速いアルゴリズム

非常に大きな n 、たとえば1兆番目に対して、Fibonacci(n) を求められるでしょうか。 フィボナッチ数の一般形を知っていれば、理論的には可能です。 α = (1 + √5)/2 とすると

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

でもあります。 これを知っていたら、 αn を求めればよいことがわかります。しかも (-α)-n の項は 0 に近づくので計算が不要です。

 double Fibonacci(int n) {
    double a = (1 + Math.sqrt(5)) / 2;
    for (int i =0; i < n; i++)
      a = a * a;
    a = a / Math.sqrt(5);
    return a;
 }

計算例
Fibonacci(5)
> 2178309.0000000913
Fibonacci(6)
> 1.0610209857722998E13

このプログラムでは、2n - 1 番目のフィボナッチ数を高速に計算します。結果として O(log n) ステップで計算可能になります。 これをサブリニア時間 (線形時間より少ない時間しか要しない) アルゴリズムといいます。

ただし、浮動小数点計算を必要とするので、計算機で処理する際には薦められません。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox