CodeIQ 挑戦の記録 : バイバイマンを数えよう

CodeIQというサイトで問題に挑戦した記録です。

バイバイマンを数えよう

問題文を要約すると、
「バイバイマン」は1日目の大きさが1で、2日目が2、3日目が4と、毎日2倍になる。
但し、10を超えると分裂し、16なら1と6に分裂し同様にバイバイを繰り返す。
100日目までのバイバイマンの数を列挙する。

提出したコード (Ruby 45byte)

a=[1]*4;b=0;100.times{c=a[-4];a<<c*2+b;p b=c}

方針

漸化式は下記の通りになります。

{ f(0)=0 }
{ f(1)=f(2)=f(3)=f(4)=1 }
{ f(n) = 2*f(n-4) + f(n-5) }

これを元に実装して正解しているのでこの漸化式も正しいのでしょう。
しかし、なぜこれが正しいか、自分には説明できません。
どうやって導いたかと言えば、紙と鉛筆でシミュレートし、数値の変化に合いそうな式を勘で当てはめていったという・・・

Rubyの最短まで後8文字で、この8文字はとてつもなく遠いですが、自分としてはまずまずの出来かなと思ってます。
大変楽しめました。
ありがとうございました。> @ozy4dm 様、参加者のみなさん


Sponsored Link