Project Euler 53

プロジェクトオイラー
http://projecteuler.net/index.php

Q53.
nCr(1≤n≤100)の100万を超える項の個数

ふつうにやると、こう。


from math import factorial

def combination(n, r):
return factorial(n) / factorial(r) / factorial(n - r)

N = 100
M = 1000000
counter = 0
for n in range(1, N + 1):
for r in range(0, n + 1):
if combination(n, r) > M:
counter += 1
print counter

これだと多倍長整数を使ってしまうので、パスカルの三角形を上から計算していき、100万を超えたら0を記録する。足し算をするどちらかが0でも0にする。そうして0を数える。



N = 100
M = 1000000

def comb(prev, n, i):
if i == 0:
return prev[0]
if i == n:
return prev[n-1]
elif prev[i-1] == 0 or prev[i] == 0:
return 0
else:
c = prev[i-1] + prev[i]
if c > M:
return 0
else:
return c

def count_exceed_M(C, n):
C.append([ comb(C[n-1], n, i) for i in range(n + 1) ])
return sum(map(lambda x: x == 0, C[n]))

counter = 0
C = [ [ 1 ] ]
print sum(map(lambda n: count_exceed_M(C, n), range(1, N + 1)))