なんかすげー面白そうな番組が始まったんですね。テレビは来週から見始めるとして、Danさんのエントリに問題が載ってたので解いてみよう。ついでに最近Javaと共に勉強しているPythonの修行にも丁度良さそうなので、プログラムはPythonで書いてみる。

自分で解いてみたい方は以下はネタバレになりますのでご注意を。

問題

15段の階段があります。階段を一段づつ上ってもOK、一段飛ばしで上ってもOKとして、この階段の上り方が何通りあるか答えなさい。

要するに、一回に1段か2段進めるという訳ですね。そして上るまでの歩数に注目すると、「最多で15歩、最小で8歩」ということになる。

15歩のときの昇るときの様子は以下のように表せる。
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 15

8歩で昇るときの様子の一例は以下のように表せる。
2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 = 15

この8歩の方に注目してみれば、「8歩で昇るパターン」には8通りあることはすぐ分かると思います。つまり1段昇るのを1歩目〜8歩目のどこにもってきても良いからです。15のパターンは上に上げた1つのパターンしかありません。

さて8歩や15歩と同じように、9歩〜14歩でもこのように「1と2の組み合わせ」で15になるパターンがいくつあるのかを考えれば、この問題の答えが見つかりそうです。

とりあえず、プログラムを使って超強引に解いてみます。超強引とは15歩〜8歩、つまり1と2の数が15個〜8個の足し算に対して答えが15になるパターンを数えていきます。

def ListSum(L):
t = 0
for i in L:
t += i
return t
def PlusOne(L):
L[0] = L[0] + 1
for i in range(len(L)):
if L[i] == 3:
L[i] = 1
L[i + 1] = L[i + 1] + 1
def Kaidan(Dan):
hit = 0
for j in range(Dan,int(Dan - 0.5) / 2,-1):
L = [1] * j
flg = 1
while flg:
sum = ListSum(L)
if sum == Dan:
hit += 1
if sum == j * 2:
flg = 0
if flg == 1:
PlusOne(L)
print hit
if __name__ == '__main__':
Kaidan(15)

解法、プログラム共に全然エレガントじゃない（笑）。しかも実行してみると分かると思うけど、20段くらいで使い物にならない速度です。

速度が遅い原因は「ありえないパターン」についても調べまくっているからであると思う。ありえないパターンとは、例えば8歩で昇るパターンの場合、1が2つ入ることはありえない。1が1つじゃないと15まで届きませんからね。

この辺を考慮して、次回改善策を披露します。

他の人は数学的に解いてるなあ…

番組のホームページは以下。「99.9%は仮説」の著者、竹内薫氏も出演している模様。
http://www.fujitv.co.jp/b_hp/komanechi/index.html