プロジェクトオイラー
http://projecteuler.net/index.php
Q205.
ピーターは1〜4が書かれた4面のサイコロを9個使う。コリンは1〜6が書かれた6面のサイコロを使う。全部振って総和が大きいほうが勝ちとする。ピーターが勝つ確率は？
畳み込みを使って、総和の確率の配列をあらかじめ計算しておく。べき乗のバイナリ法を使うと少し速くなると思われる。
def convolute(a, b):
c = [ 0 ] * (len(a) + len(b) - 1)
for i in range(len(a)):
for j in range(len(b)):
c[i+j] += a[i] * b[j]
return cdef pow_convolute(a, e):
if e == 1:
return a[:]
b = pow_convolute(a, e / 2)
if e % 2 == 1:
return convolute(a, convolute(b, b))
else:
return convolute(b, b)dice4 = [ 0 ] + [ 1. / 4 ] * 4
dice6 = [ 0 ] + [ 1. / 6 ] * 6
peter = pow_convolute(dice4, 9)
colin = pow_convolute(dice6, 6)
print sum(map(lambda i: peter[i] * sum(colin[0:i]), range(9, len(peter))))
