Aritalab:Lecture/Algorithm/Fibonacci - Revision history

Adm: /* もっと速いアルゴリズム */

2013-07-30T04:12:22Z

‎もっと速いアルゴリズム

2013-07-30T04:10:20Z

‎一般解

2013-07-30T04:07:48Z

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

2013-07-30T04:06:59Z

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

2013-07-30T04:05:01Z

‎一般解

2013-07-30T03:53:39Z

‎一般解

2013-07-30T03:52:29Z

‎一般解

2013-07-30T01:28:23Z

‎フィボナッチ数列の定義

2013-07-11T02:30:23Z

‎もっと速いアルゴリズム

2013-07-11T02:29:34Z

‎もっと速いアルゴリズム

@@ Line 105: / Line 105: @@
 非常に大きな 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> の項は 0 に近づくので計算が不要です。
+これを知っていたら、 &alpha;<sup>n</sup> を求めればよいことがわかります。
 <pre>

@@ Line 17: / Line 17: @@
 この二次方程式の解を&alpha;, &beta;とします。
 : &alpha; = (1 + √5)/2, &nbsp; &beta; = (1 - √5)/2
-&alpha;は黄金比とも呼ばれ、名刺の縦横比に対応します。&beta; は負の値です。
+&alpha;は黄金比とも呼ばれ、名刺の縦横比に対応します。&beta; は1より小さな負の値です。
 {| class="wikitable" style="width:20%; float:right"

@@ Line 82: / Line 82: @@
 上のプログラムは、n に比例するサイズの記憶領域を取っています。
-次のプログラムは <tt>Fibonacci(n)</tt> の直前2個分しか必要ありません。
+次のプログラムは数値2個分の記憶域しか必要としません。
 （こちらは入力を n とすると n+1 番目のフィボナッチ数を返します。）
 <pre>

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

@@ Line 34: / Line 34: @@
 : C<sub>1</sub>*&alpha;<sup>n</sup> + C<sub>2</sub>*&beta;<sup>n</sup>
 もちょうど漸化式を満たします。（試しに計算してみてください。）
 ここで初期条件 F(0) = 0, F(1) = 1 を満たすように、C<sub>1</sub>, C<sub>2</sub>を定めましょう。
-: C<sub>1</sub>&alpha;+C<sub>2</sub>&beta;=1,
+: C<sub>1</sub>+C<sub>2</sub>=0,
-: C<sub>1</sub>&alpha;<sup>2</sup>+C<sub>2</sub>&beta;<sup>2</sup>=1
+: C<sub>1</sub>&alpha;+C<sub>2</sub>&beta;=1
 を解くと
 : 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>)
-と書けます。
+と書けます。実際に検証してみましょう。
 ==アルゴリズム==

@@ Line 1: / Line 1: @@
 ==フィボナッチ数列の定義==
-フィボナッチ数列を関数の形に書くと、以下のように定義されます。
+フィボナッチ数列は
 * F(0) = 0
 * F(1) = 1

@@ Line 109: / Line 109: @@
 計算例
 Fibonacci(4)
 > 987.0002026342034
@@ Line 115: / Line 117: @@
 </pre>
-このプログラムでは、2<sup>n</sup> - 1 番目のフィボナッチ数を高速に計算します。結果として
+このプログラムでは、2<sup>n</sup> 番目のフィボナッチ数を高速に計算します。結果として
 [[Aritalab:Lecture/Algorithm/BigO|O(log n)]] ステップで計算可能になります。
 これをサブリニア時間 （線形時間より少ない時間しか要しない） アルゴリズムといいます。
 ただし、浮動小数点計算を必要とするので、計算機で処理する際には薦められません。