Aritalab:Lecture/Algorithm/Fibonacci
m (→もっと速いアルゴリズム) |
m |
||
Line 6: | Line 6: | ||
==一般解== | ==一般解== | ||
− | F(n)=x<sup>n</sup> | + | 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 | ||
この二次方程式の解をα, βとします。 | この二次方程式の解をα, βとします。 | ||
: α = (1 + √5)/2, β = (1 - √5)/2 | : α = (1 + √5)/2, β = (1 - √5)/2 | ||
− | α | + | αは黄金比とも呼ばれ、名刺の縦横比に対応します。 |
+ | |||
+ | {| 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>*α<sup>n</sup> + C<sub>2</sub>*β<sup>n</sup> | : C<sub>1</sub>*α<sup>n</sup> + C<sub>2</sub>*β<sup>n</sup> | ||
Line 19: | Line 32: | ||
: 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 | ||
− | + | を解くと | |
− | : C<sub>1</sub>=1/(α-β)=1/√5, C<sub>2</sub>=-1/(α-β)=-1/√5 | + | : C<sub>1</sub>=1/(α-β)=1/√5, C<sub>2</sub>=-1/(α-β)=-1/√5 |
すなわち一般項は | すなわち一般項は | ||
: F(n) = (1/√5)(α<sup>n</sup> - β<sup>n</sup>) | : F(n) = (1/√5)(α<sup>n</sup> - β<sup>n</sup>) |
Revision as of 17:26, 28 December 2011
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によるとパルテノン神殿やピラミッドにも出てくる数字だそうです。黄金比の長方形から短辺を一辺とする正方形を取り除くと、残りの長方形も黄金比になっています。
|
二つの解はいずれも漸化式を満たし、これらの線形和
- 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[] 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個分しか必要ありません。
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; }
もっと速いアルゴリズム
非常に大きな n 、たとえば1兆番目に対して、Fibonacci(n) を求められるでしょうか。 フィボナッチ数の一般形を知っていれば、理論的には可能です。 α = (1 + √5)/2 とすると
- F(n) = (1/√5)(αn - (-α)-n)
でもあります。 これを知っていたら、 αn を求めればよいことがわかります。 α を2乗していけば n ステップで α2n が求まるので、結果として O(log n) ステップで計算可能になります。 これをサブリニア時間 (線形時間より少ない時間しか要しない) アルゴリズムといいます。
ただし、浮動小数点計算を必要とするので、計算機で処理する際には薦められません。