会社で少し盛り上がった Project Euler をやってみる 015

Problem 015

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
(↑「田」みたいな図形で左上の格子点から右下の格子点までのルート)
では, 20×20 のマス目ではいくつのルートがあるか.

---

Answer 015 (Python)

import sys


class Problem15:

    def main(self, n):
        tensor = [list(range(n + 1)) for i in range(n + 1)]
        for i in range(n + 1):
            for j in range(n + 1):
                if i > 0 and j > 0:
                    tensor[i][j] = tensor[i-1][j] + tensor[i][j-1]
                elif i > 0:
                    tensor[i][j] = tensor[i-1][j]
                elif j > 0:
                    tensor[i][j] = tensor[i][j-1]
                else:
                    tensor[i][j] = 1
        print(tensor[n][n])


if __name__ == '__main__':
    num = 20
    if len(sys.argv) == 2:
        num = sys.argv[1]
    p = Problem15()
    p.main(int(num))

---

(参考) Project Euler とは

Project Euler はプログラミングで数学の問題を解くサイトです。問題は600問以上あるので、勉強に使うのも良し、楽しむのも良しです。

サイトに登録すれば、解答を submit することができ、その場であっているか判定してくれます。

また、問題だけであれば、日本語に翻訳された Wiki もあるのでそちらを見ながらやると捗ると思います。

Project Euler(日本語訳)