Aritalab:Lecture/Algorithm/Fibonacci
(→アルゴリズム) |
m |
||
Line 1: | Line 1: | ||
− | == | + | ==フィボナッチ数列の定義== |
− | + | ||
フィボナッチ数列を関数の形に書くと、以下のように定義されます。 | フィボナッチ数列を関数の形に書くと、以下のように定義されます。 | ||
* F(0) = 0 | * F(0) = 0 | ||
Line 7: | Line 6: | ||
==一般解== | ==一般解== | ||
− | 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> | ||
から | から | ||
Line 16: | Line 15: | ||
二つの解はいずれも漸化式を満たし、これらの線形和 | 二つの解はいずれも漸化式を満たし、これらの線形和 | ||
: C<sub>1</sub>*α<sup>n</sup> + C<sub>2</sub>*β<sup>n</sup> | : C<sub>1</sub>*α<sup>n</sup> + C<sub>2</sub>*β<sup>n</sup> | ||
− | + | もちょうど漸化式を満たします。(試してみてください。) | |
− | ここで初期条件を満たすように、C<sub>1</sub>, C<sub>2</sub> | + | ここで初期条件を満たすように、C<sub>1</sub>, C<sub>2</sub>を定めましょう。 |
: C<sub>1</sub>α+C<sub>2</sub>β=1, | : C<sub>1</sub>α+C<sub>2</sub>β=1, | ||
: C<sub>1</sub>α<sup>2</sup>+C<sub>2</sub>β<sup>2</sup>=1 | : C<sub>1</sub>α<sup>2</sup>+C<sub>2</sub>β<sup>2</sup>=1 | ||
Line 30: | Line 29: | ||
<pre> | <pre> | ||
int Fibonacci(int n) { | int Fibonacci(int n) { | ||
− | if (n | + | if (n == 0) return 0; |
+ | if (n == 1) return 1; | ||
int a = Fibonacci(n-1); | int a = Fibonacci(n-1); | ||
int b = Fibonacci(n-2); | int b = Fibonacci(n-2); | ||
Line 42: | Line 42: | ||
ですから、[[Aritalab:Lecture/Basic/Towers of Hanoi|ハノイの塔の解法]]から | ですから、[[Aritalab:Lecture/Basic/Towers of Hanoi|ハノイの塔の解法]]から | ||
: T(n) > C * (2<sup>n</sup>-1)/2 | : T(n) > C * (2<sup>n</sup>-1)/2 | ||
− | + | であることがわかります。つまり求めたいフィボナッチ数 n に対し、指数時間かかるアルゴリズムになります。 | |
+ | これでは <tt>Fibonacci(30)</tt> を求めることすらできないでしょう。 | ||
===記憶領域を用いたアルゴリズム=== | ===記憶領域を用いたアルゴリズム=== | ||
Line 48: | Line 49: | ||
int Fibonacci(int n) { | int Fibonacci(int n) { | ||
int[] memory = new int[n+1]; | int[] memory = new int[n+1]; | ||
− | memory[0] = memory[1] = 1; | + | memory[0] = 0; |
+ | memory[1] = 1; | ||
for(int i=2; i < n+1; i++) | for(int i=2; i < n+1; i++) | ||
memory[i] = memory[i-1] + memory[i-2]; | memory[i] = memory[i-1] + memory[i-2]; | ||
Line 54: | Line 56: | ||
} | } | ||
</pre> | </pre> | ||
− | サイズnの記憶領域(<tt>memory</tt>) | + | サイズnの記憶領域(<tt>memory</tt>)を用意するだけで、実行には n に比例する時間しか要しません。 |
− | + | これを線形時間アルゴリズムといいます。 | |
+ | 上のプログラムは、n に比例するサイズの記憶領域を取っていますが、実際は <tt>Fibonacci(n)</tt> の直前2個分しか必要ありません。 | ||
===もっと速いアルゴリズム=== | ===もっと速いアルゴリズム=== | ||
− | + | 非常に大きな n 、たとえば1兆番目に対して、<tt>Fibonacci(n)</tt> を求められるでしょうか。 | |
+ | フィボナッチ数の一般形を知っていれば、理論的には可能です。 | ||
α = (1 + √5)/2 とすると | α = (1 + √5)/2 とすると | ||
: F(n) = (1/√5)(α<sup>n</sup> - (-α)<sup>-n</sup>) | : F(n) = (1/√5)(α<sup>n</sup> - (-α)<sup>-n</sup>) | ||
− | + | でもあります。 | |
+ | これを知っていたら、 α<sup>n</sup> を求めればよいことがわかります。 | ||
+ | α を自乗していけば n ステップで α<sup>2<sup>n</sup></sup> が求まるので、結果として | ||
+ | [[Aritalab:Lecture/Basic/BigO|O(log n)]] ステップで計算可能になります。 | ||
+ | これをサブリニア時間 (線形時間より少ない時間しか要しない) アルゴリズムといいます。 | ||
+ | |||
+ | |||
ただし、不動小数の計算を必要とするので、計算機で処理する際には薦められません。 | ただし、不動小数の計算を必要とするので、計算機で処理する際には薦められません。 |
Revision as of 17:43, 19 October 2010
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用紙の縦横比に対応します。 二つの解はいずれも漸化式を満たし、これらの線形和
- C1*αn + C2*βn
もちょうど漸化式を満たします。(試してみてください。) ここで初期条件を満たすように、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[] memory = new int[n+1]; memory[0] = 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 に比例する時間しか要しません。 これを線形時間アルゴリズムといいます。 上のプログラムは、n に比例するサイズの記憶領域を取っていますが、実際は Fibonacci(n) の直前2個分しか必要ありません。
もっと速いアルゴリズム
非常に大きな n 、たとえば1兆番目に対して、Fibonacci(n) を求められるでしょうか。 フィボナッチ数の一般形を知っていれば、理論的には可能です。 α = (1 + √5)/2 とすると
- F(n) = (1/√5)(αn - (-α)-n)
でもあります。 これを知っていたら、 αn を求めればよいことがわかります。 α を自乗していけば n ステップで α2n が求まるので、結果として O(log n) ステップで計算可能になります。 これをサブリニア時間 (線形時間より少ない時間しか要しない) アルゴリズムといいます。
ただし、不動小数の計算を必要とするので、計算機で処理する際には薦められません。