2009年01月18日

ナノピコ教室:13階段への道 

  
問題
13段ある階段を下から上まで登る登り方の総数を求めてください。
ただし、登り方は、1段あるいは1段おきの2通りが許されているものとします。
----

頭の働きが悪い僕は、すぐには計算式が思い浮かびません。
ためしに、階段の段数を少なくして考えてみました。

1段 : 1通り
2段 :2通り
3段 :3通り
4段 :5通り
8段 :8通り

とここまでやってわかりました。ああなるほど、N段までの上り方総数は、
N-1段までの数と、N-2段までの数を足せば良いのか。

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

の式をコードに落とせばできそうです。
これって、フィボナッチ数列の問題だったんですね。
で、書いたコードは以下の通りです。

  static int StepN(int n) {
if (n == 1)
return 1;
if (n == 2)
return 2;
return StepN(n - 1) + StepN(n - 2);
}



StepN(13)で呼び出してみたら、377が返ってきました。

『ナノピコ教室』の解答編には、さらに計算量を少なくできる分割統治法について書いてありました。奇数と偶数の場合に分けることで、計算量を少なくできるようです。途中まで読み進んだのですが、根気が続かなく理解するのを断念しました。

※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellがC#で解いたものです。


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51731332