何さんが実際に作問したなかで、自分でも気に入っている問題はこうだ。「ここに100段の階段があります。一歩で1段か2段か3段進むとして、100段登り切るパターンは何通りありますか。この問題を解くプログラムをできるだけ短い行数で書きなさい」――。さて皆さんはこの問題を解けるだろうか。
解いてみた(自分で解きたい人のために空白をあけてます)
class F:
def f(self, num):
if num < 1:
return 0
res = self.f(num - 3) + self.f(num - 2) + self.f(num - 1)
if num < 4:
res += 1
return res
if __name__ == '__main__':
f = F()
print f.f(100)
ただし、これを普通のPCで計算するといつまでも結果が帰ってこないので、f.f(n) の値をキャッシュする
class F:
def __init__(self):
self.cache = {}
def f(self, num):
if self.cache.has_key(num):
return self.cache[num]
if num < 1:
return 0
res = self.f(num - 3) + self.f(num - 2) + self.f(num - 1)
if num < 4:
res += 1
self.cache[num] = res
return res
if __name__ == '__main__':
f = F()
print f.f(100)
答え:180396380815100901214157639 通り
解説
…を試みる
n段の時の組み合わせを求める関数F(n)を考える(nは自然数)
100段上るときの最期の1歩のパターンは1段、2段、3段があるので、
F(100) = F(99) + F(98) + F(97) となる
一般化すると F(n) = F(n - 1) + F(n - 2) + F(n - 3)
ただしこれは4以上のとき。
なぜ4以上かというと、1 <= n <= 3 のとき、1歩で到達することをカウントしてないし、
nに0以下の数字が入ることが考えられてない。
ので、n <= 0 のとき F(n) = 0 とすれば
1 <= n <= 3 のときは F(n - 1) + F(n - 2) + F(n - 3) + 1
まとめると、
F(n) = 0 (n <= 0のとき)
F(n) = F(n - 1) + F(n - 2) + F(n - 3) + 1 (1 <= n <= 3のとき)
F(n) = F(n - 1) + F(n - 2) + F(n - 3) (n >= 4のとき)
…って感じかなぁ