Project Euler 015を解いてみる。「格子経路」
Project Euler 015
2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.
->次の問題
考え方
中学か高校の数学でやったことのある問題ですね。
どんなルートを通るにしても右に20回、下に20回の計40回の移動をすることは確定しているので、
40個の動作の中から「下へ行く」をする20箇所を選ぶ組み合わせ問題
と考えられます。
{}_{40} C_{20} = \frac{40!}{20!20!}
コード
euler015.py
def main():
"""
go downが20回、go rightが20回の計40回の動作がある。
40個の動作の中からgo downをする20箇所を選ぶ組み合わせ問題と考えられる。
40C20 = (40*39* ・・・ *22*21) / (20*19* ・・・ *3*2)
:return:
"""
n = 20
ans = 1
for i in range(n + 1, n * 2 + 1):
ans *= i
for i in range(2, n+1):
ans //= i
print(ans)
if __name__ == '__main__':
from time import time as t
start = t()
main()
print(t() - start, 'sec')
paizaにて実行
結果
137846528820
9.775161743164062e-06 sec
計算量も大したことはないので、とくにひねりもなくそのまま計算しました。
Author And Source
この問題について(Project Euler 015を解いてみる。「格子経路」), 我々は、より多くの情報をここで見つけました https://qiita.com/radiol/items/11bec6b4c1bed153eb37著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .