Search on the blog

2010年9月2日木曜日

フィボナッチあれこれ

世の中には、フィボナッチ数列がたくさん。。
例えば、うさぎのつがいの問題。これはあまりにも有名。

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

最初、見たとき意味分かりませんでした。そもそも”つがい”って何??笑
雄と雌の1組のことを”つがい”と言うらしいです。(英語では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の畳を敷き詰めるとき、敷き詰め方は何通りあるでしょうか?

どちらの問題も有名どころです。。アルゴリズマーの中では、常識の範疇です。
上記2つの問題も最初問題を把握するために簡単な例を解いてみて(ボトムアップ的思考)、そのあと、問題の意味を把握したら、n番目の状態とn-1番目、n-2番目の関係を考えてみる(トップダウン的思考)というやり方をするとすぐに分かると思います。


0 件のコメント:

コメントを投稿