読者です 読者をやめる 読者になる 読者になる

Engineer as a Lifestyle @tenkoma

tenkoma's testing blog

楽天の入社問題

何さんが実際に作問したなかで、自分でも気に入っている問題はこうだ。「ここに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のとき)

…って感じかなぁ