Problem53 - Project Euler

30分プログラム、その327。Problem53 - Project Euler。

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

組み合わせでは, 以下の記法を用いてこのことを表す: ⁵C₃ = 10.

一般に, r ≤ n についてⁿC_r = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1と階乗を定義する.
n = 23になるまで, これらの値が100万を超えることはない: ²³C₁₀ = 1144066.
1 ≤ n ≤ 100について, 100万を超えるのnCrは何通りか?

単純にn=1から走査したら、あっさりとけた。これでいいや。

使い方

$ time python problem53.py 
....
(100, 96)
4075
python problem53.py  0.83s user 0.08s system 9% cpu 10.065 total

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem53.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/06/28 23:16:43
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

def fact(n):
    if n == 0:
        return 1
    else:
        return n*fact(n-1)

def combi(n,r):
    return fact(n) / (fact(r) * fact(n-r))

def main():
    res = 0
    for n in xrange(1,101):
        for r in xrange(1,n+1):
            if combi(n,r) > 1000000:
                print (n,r)
                res+=1
    return res

print main()

参考

• 過去の30分プログラム
• Problem 53 - PukiWiki