2009年01月21日

ナノピコ教室:13階段への道(2次元版)

  
13階段への道の問題は、もうひとつあります。
最初の問題は、1次元の階段でしたが、今度は、2次元の階段です。
問題は、左右どちらかに1段ずつ上り、高さ13段(14か所ある)へ到達する総数が一番多い場所とその総数を求めよという問題。

話を単純化するために、高さ5段の階段で考えてみます。

+-+-+-+-+-+-+
|5| | | | | |
+-+-+-+-+-+-+
|4|5| | | | |
+-+-+-+-+-+-+
|3|4|5| | | |
+-+-+-+-+-+-+
|2|3|4|5| | |
+-+-+-+-+-+-+
|1|2|3|4|5| |
+-+-+-+-+-+-+
| |1|2|3|4|5|
+-+-+-+-+-+-+



左下が一番低い場所で、右上が一番高い場所です。
数字がその段数を表しています。
5段の場合は、全部で6か所あり、それぞれの場場所へ行く登り方が何通りあるかを求めればよいわけです。

前回と同じように、F(n)を n段まで登る登り方の総数とすると、

F(5) = F(4) + F(4)

と表せそうですが、端っこの 5 の場合は、

F(5) = F(4)

となってうまくいきません。しばらく考えましたがうまい方法を思いつかなかったので、計算式を導き出す方法は諦めて、すべてコンピュータにやってもらうことにしました。
再帰処理で、できそうです。

 private Dictionary<int, int> dict = new Dictionary<int, int>();

public void Execute() {
Execute(0, 0);
foreach (var k in dict.Keys) {
Console.WriteLine("({0},{1}) : {2}", k / 14, k % 14, dict[k]);
}
}

public void Execute(int x, int y) {
if (x + y == 13) {
int key = y * 14 + x;
if (dict.ContainsKey(key))
dict[key] = dict[key] + 1;
else
dict[key] = 1;
return;
}
Execute(x+1, y);
Execute(x, y+ 1);
}




すべての登り方を試し、13段までたどり着いたら、その位置に対するカウントを1増やすことで、登り方の数を求めています。

13とか14とかマジックナンバーがあるのと Executeという安易な名前にしてあるのは、ご愛敬ということで...

これで実行してみたら、以下のような結果が得られました。

(0,13) : 1
(1,12) : 13
(2,11) : 78
(3,10) : 286
(4,9) : 715
(5,8) : 1287
(6,7) : 1716
(7,6) : 1716
(8,5) : 1287
(9,4) : 715
(10,3) : 286
(11,2) : 78
(12,1) : 13
(13,0) : 1



場所(6,7) or (7,6)の 1716通りが最も登り方が多い場所となります。

ちなみに『ナノピコ教室』の解答編には4つの解き方が書いてありました。
その中に、bool[8192](8192 = 2の13乗)のすべてのパターンについて、trueの個数ごとに分類するというやり方がありました。なるほどそんなやり方があるのか。


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


 

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

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