フィボナッチあれこれ

世の中には、フィボナッチ数列がたくさん。。

例えば、うさぎのつがいの問題。これはあまりにも有名。

うさぎのつがいがいる。このつがいは1か月経つと、大人になる。そして2か月経つと子供を産み始める。さて、0か月目に1組のつがいが居たとして、nか月後にはつがいは何組になるでしょうか？

最初、見たとき意味分かりませんでした。そもそも”つがい”って何？？笑

雄と雌の１組のことを”つがい”と言うらしいです。（英語ではbreeding pairです。）

では、さっそく考えてみましょう。

0か月目: 1組。

1か月目: 1組が大人になる。でもまだ1組のまま。

2か月目: 大人になったつがいが子供を産むので2組。

3か月目：2か月目に生まれたつがいが大人になる。最初からいるつがいは子供を産むので、3組。

4か月目: 2か月目に生まれたつがいと最初からいるつがいが子供を産むので2組増えて5組。

……

はい、nか月目にいるつがいの数をn=0から列挙すると、

1,1,2,3,5,...

うむむ。なんかフィボナッチっぽい香りがしますね。。

それでは、より一般化して考えてみましょう。nか月目にいるつがいの数をf(n)とします。

f(n) = nか月目にいるつがいの数

= (n-1)か月目の時点で存在しているつがいの数 + nか月目に生まれるつがいの数

　　 = (n-1)か月目の時点で存在しているつがいの数 + (n-1)か月目の時点で大人であるつがいの数

=(n-1)か月目の時点で存在しているつがいの数 + (n-2)か月目の時点で存在しているつがいの数 　　= f(n-1) + f(n-2)

上の考え方は、かなり大事です。

トップダウン的な思考で、より一般的な現象を把握します。

上の式より、

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

なので、フィボナッチですね。プログラムで解くときは、メモ化再帰か動的計画です。個人的にはフィボナッチは、メモ化再帰で解くのが好きです。フィボナッチに限らず漸化式系の問題一般に適用できるからです。

他にも、フィボナッチ数列になる現象はいろいろあります。

例えば、

あなたは、1段、または、2段ずつ階段を上れます。n段目まで上がる場合何通りの上り方があるでしょうか？

2*nの長方形の形をした部屋があります。この部屋に1*2の畳を敷き詰めるとき、敷き詰め方は何通りあるでしょうか？

どちらの問題も有名どころです。。アルゴリズマーの中では、常識の範疇です。

上記２つの問題も最初問題を把握するために簡単な例を解いてみて（ボトムアップ的思考）、そのあと、問題の意味を把握したら、n番目の状態とn-1番目、n-2番目の関係を考えてみる（トップダウン的思考）というやり方をするとすぐに分かると思います。