回答編集履歴
1
追記
test
CHANGED
|
@@ -37,3 +37,27 @@
|
|
|
37
37
|
|
|
38
38
|
|
|
39
39
|
定義通り、積み上げ式はわかりました。行列計算を調べてみましょう。
|
|
40
|
+
|
|
41
|
+
|
|
42
|
+
|
|
43
|
+
|
|
44
|
+
|
|
45
|
+
**補足**
|
|
46
|
+
|
|
47
|
+
|
|
48
|
+
|
|
49
|
+
フィボナッチ数の一般項は、もとはオイラーが発見したそうです。（証明は難しいです）
|
|
50
|
+
|
|
51
|
+
F(n) = (Φ^n - (1-Φ)^n)/sqrt(5) ただし Φ = (1+sqrt(5))/2
|
|
52
|
+
|
|
53
|
+
|
|
54
|
+
|
|
55
|
+
一般項の近似式は次のようになります。計算量を考えるとしたらこれでいいと思います。
|
|
56
|
+
|
|
57
|
+
F(n) ≒ Φ^n/sqrt(5) 第二項(1-Φ)^n/sqrt(5)の絶対値は、最大で0.447..なので省略
|
|
58
|
+
|
|
59
|
+
|
|
60
|
+
|
|
61
|
+
第二項の性質を使って一般項を求め直すと次のようになります。これは一種のトリックです。
|
|
62
|
+
|
|
63
|
+
F(n) = floor((1/5)*Φ^n + (1/2)) floor はガウス関数。ただし正のフィボナッチ数のみ。
|