という訳で、前回のエントリの解法を見直す。

各歩数のパターンにて、1段飛ばしで昇る回数は以下のように決まっている。

15歩のパターンのとき　→　1段飛ばしで昇ることはない
14歩のパターンのとき　→　1回だけ1段飛ばしで昇る
13歩のパターンのとき　→　2回だけ1段飛ばしで昇る
・
・
・

というような具合である。つまり

1段飛ばしする回数 = 段数 – 歩数

となる。

ここで8歩のパターンの一つをもう一度足し算で表してみる。

2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 = 15

とすると、これは「8個の中から7つを選ぶパターンがいくつあるか」という問題と同義であることに気付く。つまり「8歩中、7つの1段飛ばしをどこに入れれば良いのか」というのを数えていけば良い。

これはいわゆる以下の式で求められる。x歩パターンのとき、n個の1段飛ばしがあるとすると、

となります。懐かしいですね。これを15歩から8歩の各パターンで計算してあげ足し合わせれば、15段を昇るパターンがいくつあるのかを計算できそうです。この方針でプログラムを書いてみました。

def factorial(x):
if x == 1:
return 1
else:
ans = x * factorial(x - 1)
return ans
def Kaidan(Dan):
hit = 0
a = 0
for j in range(Dan,int(Dan - 0.5) / 2,-1):
a = Dan - j
if a == 0 or a == j:
ptn = 1
else:
ptn = factorial(j) / (factorial(j - a) * factorial(a))
hit += ptn
print hit
if __name__ == '__main__':
Kaidan(15)

これだと現実的な速度です（笑）。

しかしこの問題の答えが再帰構造になっているのって、実際に計算値を並べていけば気付くけど、なぜそうなっているのかが全然理解出来ない。誰か教えて下さい。