プロジェクトオイラー
http://projecteuler.net/index.php
Q151.
省略
封筒の状態とその状態を取る確率を計算していく。最初にA2〜A5の紙が1枚ずつ入っている。それが確率1である。次の状態は、どの紙を取るかで変わってくる。しかし、それぞれの状態の確率は1/4である。違うパスで同じ状態を取ることもあるので、その確率はパスで足し合わせる。
class envelope:
def __init__(self):
self.a = { }
def add(self, stat, p):
n = self.encode(stat)
if self.a.has_key(n):
self.a[n] += p
else:
self.a[n] = p
def gen_stat(self):
for stat in self.a.keys():
yield self.decode(stat)
def get_probability(self, stat):
n = self.encode(stat)
return self.a[n]
def num(self):
return len(self.a)
def batch(self, stat, size):
n = self.encode(stat)
n -= 1 << (5 - size) * 4
n += ((1 << (5 - size) * 4) - 1) / 15
return self.decode(n)
# internal function
def encode(self, a):
n = 0
for size in a:
n += 1 << (5 - size) * 4
return n
def decode(self, n):
a = [ ]
for size in range(5, 1, -1):
a += [ size ] * (n & 15)
n >>= 4
return as = 0
a = envelope()
a.add([2,3,4,5], 1.0)
for i in range(14):
b = envelope()
for stat in a.gen_stat():
n = len(stat)
p = a.get_probability(stat)
for size in stat:
stat_next = a.batch(stat, size)
b.add(stat_next, p / n)
if len(stat) == 1:
s += p
a = b
print "%.6f" % s
