Project Euler - Problem 53

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　ProjectEuler.net（英語サイト）

Problem 53
12345から3つ選ぶ選び方は10通りである.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10.
一般に, r≦n についてnCr = n!/(r!(n-r)!) である.
ここで, n! = n×(n-1)×...×3×2×1, 0! = 1と階乗を定義する.
n = 23になるまで, これらの値が100万を超えることはない:
23C10 = 1144066.
1≦n≦100について, 100万を超えるnCrは何通りか?

－－－－－


私の解答例は以下です。畳んでいます。

def h(n):
	if n<=1: return 1
	else: return h(n-1)*n

def g(n, m): return h(n)//h(n-m)//h(m)

def f(n, m):
	s = 0
	for i in xrange(1, n+1):
		for j in xrange(1, i+1):
			if g(i, j)>m: s += 1
	return s

print f(100, 1000000)

１．関数h(n)
・nの階乗を返します。problem20と同じです。


２．関数g(n, r)
・順列nCrの値を返します。problem15と同じです。


３．関数f(m):
・順列nC*のすべての組み合わせ値のうちmを超える組の件数を返します。


・s = 0
　sは件数カウンターです。0クリアしておきます。


・for i in xrange(1, n+1):
　ループ関数iは順列nCr、n個のうちr個選ぶ組み合わせのnです。


・for j in xrange(1, i+1):
　ループ関数jは順列nCr、n個のうちr個選ぶ組み合わせのrです。


・if g(i, j)>m: s += 1
　関数g(i,j)で順列値を求めその値がmを超える場合、件数カウンターsをカウントアップします。


・return s
　iとjのループが終わったら、件数カウンターsを返します。

４．関数の外
　関数f(100,1000000)を呼び出し、その戻り値を出力します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
4075