数学ガールを読むぞぉ 5 - 漸化式

Scheme

Schemeのお陰で息を吸うように再帰でプログラミング出来るようになりました。

フィボナッチの定義をそのまま写せば、

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else
          (+ (fib (- n 2))
             (fib (- n 1))))))

(fib 10) ; 55

簡単ですね。

が・・・

(fib 1000) ; 終了せず

2^1000回くらい計算するので終わりません。コンピューターには無限がなぁ〜い。


そこで、漸化式を一般項に直して高速化したい訳なんですが・・・むじぃので大体諦めちゃうんだよね・・。


再帰を反復に直すだけで泣きそうなのに、一般項に直せるかっつーの！！

ということで

漸化式を一般項に直す練習。

等差数列の 漸化式 <-> 一般項

n 0 1 2 3 4 5
F(n) 1 3 5 7 9 11

という奴を考える

漸化式は、
F(0) = 1
F(n) = F(n-1) + 2

一般項は、
F(n) = 1 + 2n

となるので、

初項a,公差dの等差数列は、

漸化式                  一般項
F(0) = a           <-> F(n) = a + dn
F(n) = F(n-1) + d

という関係があることがわかる。

漸化式はO(N)の計算回数を必要とするが、一般項ならO(1)となる。スンバラシイ！！

等比数列の 漸化式 <-> 一般項

n 0 1 2 3 4 5
F(n) 2 3 5 9 17 31

というので考える。

漸化式は
F(0) = 2
F(n) = 2F(n-1) - 1


しかし、今のままでは、「一般項に辿り着けない」


そこで、αを使って理想型を目指す。

F(0) = a
F(n) - α　= r(F(n-1) - α)

こんなん。aが初項、rが公比。

両辺から1を引くと理想型になる

F(n) - 1 = 2(F(n-1) - 1)

すると、F(n)とF(n-1)の関係がわかりやすくなるよね。

一般項は

F(n) = (a - α)r^n + α

という形になるから、

F(n) = 2^n + 1

漸化式                              一般項
F(0) = a
F(n) = rF(n-1) + s
  V
 変 換(α = rα + s)
  V
F(0) = a                      <->  F(n) = (a - α)r^n + α
F(n) - α　= r(F(n-1) - α)

落ち着いてみれば簡単だったり。


漸化式から、一般項(閉じた式)に直す過程がなんとなく掴めてきた。

数列F(n),F(n-1)との関係を解き明かして、パターンに当てはめればいいと。

参考書の続きがむじいので、後で。

フィボナッチ数列の母関数の閉じた式

参考書に飽きてきたので進んでみる。

フィボナッチ数列の母関数の閉じた式を求めていく。

フィボナッチの定義の一部。

F(n) = F(n-2) + F(n-1)

を変形して、

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

ゼロ。うんうん。

これを「フィボナッチにおけるパターン」とする訳だ。アタマイイナ。


xでゴニョゴニョして・・・ズバズバーっと消えて・・・整理して・・・出た!!


F(x) = \frac{x}{1 - x - x^2}


なんとなくわかった気になった。