またまたフィボナッチ，お前オレのこと好きだろ？

Ray Through Glasses
http://acm.uva.es/p/v103/10334.html
図を見れば問題の意味は分かると思う．なんとなくだが，光が反射する板が2枚合って，光が反射する回数nが与えられたときに，何通りの反射の仕方があるかを求める問題．動作をそのまま再帰関数で定義して，メモライズすると一瞬で解けるわけだが，多倍長が必要．ライブラリからコピーしてペーストして，はいaccept．

ところで，小さな数に対する出力を見るとフィボナッチ数列になっている．うは，またお前か．どういうことだろうか．

この問題において，ある時点における光の曲がり方の数は，そのときの光の向きと，その直前に曲がった位置によって，1通りか2通りかに決まる．したがって，n回曲がったときの場合の数は，n-1回曲がったときのうち，曲がり方が1通りのものの数と2通りのものの数によって決まる．これを，nのときの曲がり方の数をa(n)として，さらにその中で，その直後の曲がり方が1通りしかないものの数をa1(n)，2通りのものの数をa2(n)とすると（若干意味不明だが），

a(n)=a1(n-1)+a2(n-1)*2

となる．この式は当たり前のことを言ってるだけで，1通りしかないときは1つずつしか出てこないし，2通りあるときは2倍の数だけ出てくるってことだ．これがフィボナッチ数列になってるのはすぐには分からないけど，とりあえず，a(n)=a1(n)+a2(n)であることに注意すると，

a(n)=a1(n-1)+a2(n-1)*2
　　　 =a1(n-1)+a2(n-1)+a2(n-1)
　　　 =a(n-1)+a2(n-1)・・・?

と計算できる．この式も見たまま読める．しかしまだフィボナッチは出てこない．そこで次のような考察が必要になる．

ある時点における曲がり方の数は，その直前の曲がり方で決まる．実際に書いてみると分かるが，直前の曲がり方が1通りだった場合は，その次には2通りの方法で曲がれるようになる．何故なら光の方向が変わるから．逆に直前の曲がり方が2通りだった場合は，そのうちの1つは1通りしか曲がり方がなく，もう1つは同じく2通りの曲がり方があるようになる．ここで重要なのは，直前がどんな曲がり方だったとしても，2通りに曲がれる場合が必ず生まれることである．つまり，ある時点において2通りに曲がれる場合の数は，その前の時点での全ての場合の数に等しい．式で書くと，

a2(n)=a(n-1)・・・?

ついでに言うとa1(n)=a2(n-1)であるから，

a1(n)+a2(n)=a(n-1)+a2(n-1)

となって，?の式と同じになった．考え方は違うけど，正しいことが分かる．

そいで，?に?を代入して，

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

となり，ここでやっとフィボナッチさんのお出ましである．なんまいだなんまいだ．

こういう考察は面白いんだけど，正直問題を解くためには全く必要のないことなので，無駄っちゃ無駄だ．でもまあ，良しとしておこう．だってフィボナッチだもん ヾ(゜ω゜= )ゞ