Aritalab:Lecture/Algorithm/Fibonacci

From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
Jump to: navigation, search
(記憶領域を用いたアルゴリズム)
m (もっと速いアルゴリズム)
 
(17 intermediate revisions by one user not shown)
Line 1: Line 1:
 
==フィボナッチ数列の定義==
 
==フィボナッチ数列の定義==
フィボナッチ数列を関数の形に書くと、以下のように定義されます。
+
フィボナッチ数列は
 +
 
 +
: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 +
 
 +
と続きます。前にある2つの数字の和が続いています。これを関数の形に書くと、以下になります。
 +
 
 
* F(0) = 0
 
* F(0) = 0
 
* F(1) = 1
 
* F(1) = 1
Line 6: Line 11:
  
 
==一般解==
 
==一般解==
F(n)=x<sup>n</sup>と仮定します。これが、F(n+2)=F(n+1)+F(n) を満たすので
+
F(n)=x<sup>n</sup> と仮定します。これがちょうど F(n+2)=F(n+1)+F(n) を満たすことに注意します。
 
: x<sup>n+2</sup>=x<sup>n+1</sup>+x<sup>n</sup>
 
: x<sup>n+2</sup>=x<sup>n+1</sup>+x<sup>n</sup>
から
+
両辺を x<sup>n</sup> で割ります。
 
: x<sup>2</sup>=x+1
 
: x<sup>2</sup>=x+1
 
この二次方程式の解を&alpha;, &beta;とします。
 
この二次方程式の解を&alpha;, &beta;とします。
 
: &alpha; = (1 + √5)/2, &nbsp; &beta; = (1 - √5)/2
 
: &alpha; = (1 + √5)/2, &nbsp; &beta; = (1 - √5)/2
&alpha;は黄金比とも呼ばれ、OA用紙の縦横比に対応します。
+
&alpha;は黄金比とも呼ばれ、名刺の縦横比に対応します。&beta; は1より小さな負の値です。
 +
 
 +
{| class="wikitable" style="width:20%; float:right"
 +
! 黄金比
 +
|-
 +
| Wikipediaによるとパルテノン神殿やピラミッドにも出てくる数字だそうです。黄金比の長方形から短辺を一辺とする正方形を取り除くと、残りの長方形も黄金比になっています。
 +
 
 +
{| class="wikitable" style="width:160px; height:100px"
 +
| style="width:100px; background:lightgray"|
 +
| style="width:60px; background:gold"|
 +
|}
 +
 
 +
|}
 +
 
 
二つの解はいずれも漸化式を満たし、これらの線形和
 
二つの解はいずれも漸化式を満たし、これらの線形和
 
: C<sub>1</sub>*&alpha;<sup>n</sup> + C<sub>2</sub>*&beta;<sup>n</sup>
 
: C<sub>1</sub>*&alpha;<sup>n</sup> + C<sub>2</sub>*&beta;<sup>n</sup>
 
もちょうど漸化式を満たします。(試しに計算してみてください。)
 
もちょうど漸化式を満たします。(試しに計算してみてください。)
ここで初期条件を満たすように、C<sub>1</sub>, C<sub>2</sub>を定めましょう。
+
 
: C<sub>1</sub>&alpha;+C<sub>2</sub>&beta;=1,
+
ここで初期条件 F(0) = 0, F(1) = 1 を満たすように、C<sub>1</sub>, C<sub>2</sub>を定めましょう。
: C<sub>1</sub>&alpha;<sup>2</sup>+C<sub>2</sub>&beta;<sup>2</sup>=1
+
: C<sub>1</sub>+C<sub>2</sub>=0,
より、
+
: C<sub>1</sub>&alpha;+C<sub>2</sub>&beta;=1
: C<sub>1</sub>=1/(&alpha;-&beta;)=1/√5, C<sub>2</sub>=-1/(&alpha;-&beta;)=-1/√5
+
を解くと
 +
: C<sub>1</sub>=1/(&alpha;-&beta;)=1/√5, &nbsp; C<sub>2</sub>=-1/(&alpha;-&beta;)=-1/√5
 
すなわち一般項は
 
すなわち一般項は
 
: F(n) = (1/√5)(&alpha;<sup>n</sup> - &beta;<sup>n</sup>)
 
: F(n) = (1/√5)(&alpha;<sup>n</sup> - &beta;<sup>n</sup>)
と書けます。
+
と書けます。実際に検証してみましょう。
 +
: (1/√5)(&alpha;<sup>2</sup> - &beta;<sup>2</sup>) = (1/√5){(&alpha;+1) - (&beta; + 1)} = 1 = F(2)
 +
: (1/√5)(&alpha;<sup>3</sup> - &beta;<sup>3</sup>) = (1/√5)(&alpha;(&alpha;+1) - &beta;(&beta; + 1)} = 1 + 1 = F(3)
 +
確かに成り立っていますね。
  
 
==アルゴリズム==
 
==アルゴリズム==
Line 51: Line 73:
 
   mem[0] = 0;
 
   mem[0] = 0;
 
   mem[1] = 1;
 
   mem[1] = 1;
   for(int i=2; i < n+1; i++)
+
   for(int i=2; i < n+1; i&#43;&#43;)
 
     mem[i] = mem[i-1] + mem[i-2];
 
     mem[i] = mem[i-1] + mem[i-2];
 
   return memory[n];
 
   return memory[n];
Line 58: Line 80:
 
サイズnの記憶領域(<tt>memory</tt>)を用意するだけで、実行には n に比例する時間しか要しません。
 
サイズnの記憶領域(<tt>memory</tt>)を用意するだけで、実行には n に比例する時間しか要しません。
 
これを線形時間アルゴリズムといいます。
 
これを線形時間アルゴリズムといいます。
上のプログラムは、n に比例するサイズの記憶領域を取っていますが、実際は <tt>Fibonacci(n)</tt> の直前2個分しか必要ありません。
+
上のプログラムは、n に比例するサイズの記憶領域を取っています。
  
 +
次のプログラムは数値2個分の記憶域しか必要としません。
 +
(こちらは入力を n とすると n+1 番目のフィボナッチ数を返します。)
 
<pre>
 
<pre>
 
  int Fibonacci(int n) {
 
  int Fibonacci(int n) {
 
   int num1 = 1, num2 = 1, tmp = 1;
 
   int num1 = 1, num2 = 1, tmp = 1;
   for(int i = 1; i < n; i++) {
+
   for(int i = 1; i < n; i&#43;&#43;) {
 
     tmp = num1 + num2;
 
     tmp = num1 + num2;
 
     num1 = num2;
 
     num1 = num2;
Line 70: Line 94:
 
   return tmp;
 
   return tmp;
 
  }
 
  }
 +
 +
実行例
 +
Fibonacci(15) ... 16番目
 +
> 987
 +
Fibonacci(31) ... 32番目
 +
> 2178309
 
</pre>
 
</pre>
  
Line 75: Line 105:
 
非常に大きな n 、たとえば1兆番目に対して、<tt>Fibonacci(n)</tt> を求められるでしょうか。
 
非常に大きな n 、たとえば1兆番目に対して、<tt>Fibonacci(n)</tt> を求められるでしょうか。
 
フィボナッチ数の一般形を知っていれば、理論的には可能です。
 
フィボナッチ数の一般形を知っていれば、理論的には可能です。
&alpha; = (1 + √5)/2 とすると
+
&alpha; = (1 + √5)/2, &beta; = (1 - √5)/2 とすると
: F(n) = (1/√5)(&alpha;<sup>n</sup> - (-&alpha;)<sup>-n</sup>)
+
: F(n) = (1/√5)(&alpha;<sup>n</sup> - &beta;<sup>n</sup>)
でもあります。
+
で、&beta; は 1 より小さな値です。n が大きくなれば、&beta;<sup>n</sup> の項は 0 に近づくため、計算が不要です。
 
これを知っていたら、 &alpha;<sup>n</sup> を求めればよいことがわかります。
 
これを知っていたら、 &alpha;<sup>n</sup> を求めればよいことがわかります。
&alpha; を自乗していけば n ステップで &alpha;<sup>2<sup>n</sup></sup> が求まるので、結果として
+
 
 +
<pre>
 +
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(1)
 +
> 1.1708203932499368
 +
Fibonacci(4)
 +
> 987.0002026342034
 +
Fibonacci(5)
 +
> 2178309.0000000913
 +
</pre>
 +
 
 +
このプログラムでは、2<sup>n</sup> 番目のフィボナッチ数を高速に計算します。結果として
 
[[Aritalab:Lecture/Algorithm/BigO|O(log n)]] ステップで計算可能になります。
 
[[Aritalab:Lecture/Algorithm/BigO|O(log n)]] ステップで計算可能になります。
 
これをサブリニア時間 (線形時間より少ない時間しか要しない) アルゴリズムといいます。
 
これをサブリニア時間 (線形時間より少ない時間しか要しない) アルゴリズムといいます。
  
 
+
ただし、浮動小数点計算を必要とするので、計算機で処理する際には薦められません。
ただし、不動小数の計算を必要とするので、計算機で処理する際には薦められません。
+

Latest revision as of 13:12, 30 July 2013

Contents

[edit] フィボナッチ数列の定義

フィボナッチ数列は

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

と続きます。前にある2つの数字の和が続いています。これを関数の形に書くと、以下になります。

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

[edit] 一般解

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

αは黄金比とも呼ばれ、名刺の縦横比に対応します。β は1より小さな負の値です。

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

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

C1n + C2n

もちょうど漸化式を満たします。(試しに計算してみてください。)

ここで初期条件 F(0) = 0, F(1) = 1 を満たすように、C1, C2を定めましょう。

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

を解くと

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

すなわち一般項は

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

と書けます。実際に検証してみましょう。

(1/√5)(α2 - β2) = (1/√5){(α+1) - (β + 1)} = 1 = F(2)
(1/√5)(α3 - β3) = (1/√5)(α(α+1) - β(β + 1)} = 1 + 1 = F(3)

確かに成り立っていますね。

[edit] アルゴリズム

[edit] 定義そのままのアルゴリズム

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) を求めることすらできないでしょう。

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

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 に比例するサイズの記憶領域を取っています。

次のプログラムは数値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(15) ... 16番目
> 987
Fibonacci(31) ... 32番目
> 2178309

[edit] もっと速いアルゴリズム

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

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

で、β は 1 より小さな値です。n が大きくなれば、βn の項は 0 に近づくため、計算が不要です。 これを知っていたら、 αn を求めればよいことがわかります。

 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(1)
> 1.1708203932499368
Fibonacci(4)
> 987.0002026342034
Fibonacci(5)
> 2178309.0000000913

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

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

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox