問題

問題

15段の階段があります。階段を一段づつ上ってもOK、一段飛ばしで上ってもOK

として、この階段の上り方は何通りあるでしょうか。

[結] 2008年11月 – 結城浩の日記

数学的な話だと、法則を見つけてスマートに解くということになるのかな？

Common Lispの問題として力技で問いてみました。

Common Lispで回答

スタート時の残りの段数を15として、1段上がったら、残り段数14になる。0になったら、登りきったということになる。残り段数から1か2の引き算を繰り返して0になるのは何通りあるかということになる。

(defun answer (step-count)
(let ((way-count 0))
(labels ((rec (n)
(if (zerop n)
(incf way-count) ;reached.
(loop for i from 1 to 2
until (< n i)
do (rec (- n i))))))
(rec step-count)
way-count)))
(format t "answer is ~d~%" (answer 15))

答を出すのにかなり時間がかかってしまった上に最初は問題を読み間違えてたり、散々な結果でした。slimeを全然上手く使えてないので、vimで書くより返ってもどかしかったのが悔しい。

Webで検索して、結城さんの過去の回答を見ると、フィボナッチ数列。あー言われてみれば。応用の効かない自分の脳味噌が残念でした。

模範回答を実装

* F(1)=1

* F(2)=2

* F(N)=F(N-2)+F(N-1)　　（N≧3）

[結] 2006年4月 – 結城浩の日記

(defun answer (step-count)
(or (plusp step-count)
(error 'step-count-msut-plus-value))
(case step-count
(1 1)
(2 2)
(otherwise (+ (answer (- step-count 2))
(answer (- step-count 1))))))
(format t "answer is ~d~%" (answer 15))

すっきりですね。書くのも簡単でした。問題の分析をちゃんと行なうことで、実装が簡単で堅牢なプログラムを書くことができるというのを肌で感じました。

#でも、二段飛しとか三段飛ばしもOKにする場合は、最初の力技の方が融通が効くなー。(負け惜しみ)