何さんが実際に作問したなかで、自分でも気に入っている問題はこうだ。「ここに100段の階段があります。一歩で1段か2段か3段進むとして、100段登り切るパターンは何通りありますか。この問題を解くプログラムをできるだけ短い行数で書きなさい」――。さて皆さんはこの問題を解けるだろうか。
解いてみた(自分で解きたい人のために空白をあけてます)
#!/usr/bin/env python 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) の値をキャッシュする
#!/usr/bin/env python 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のとき)
…って感じかなぁ