<p>我对@desired_login的观点很感兴趣,但我想我应该尝试计算排列,而不是迭代它们:</p>
<pre><code>import sys
if sys.hexversion >= 0x3000000:
rng = range # Python 3.x
else:
rng = xrange # Python 2.x
def P(n, k):
"""
Calculate permutations of (n choose k) items
"""
if 2*k > n:
k = n - k
res = 1
for i in rng(k):
res = res * (n-i) // (i+1)
return res
Ps = 0.837 # Probability of Susie winning one match
Px = 0.980 # Target probability
# Probability of Susie winning exactly k of n matches
win_k = lambda n,k: P(n, k) * Ps**k * (1.0-Ps)**(n-k)
# Probability of Susie winning k or more of n matches
win_k_or_more = lambda n,k: sum(win_k(n, i) for i in rng(k, n+1))
def main():
# Find lowest k such that the probability of Susie winning k or more of 2*k - 1 matches is at least Px
k = 0
while True:
k += 1
n = 2*k - 1
prob = win_k_or_more(n, k)
print('Susie wins {} or more of {} matches: {}'.format(k, n, prob))
if prob >= Px:
print('At first to {} wins, Susie has >= {} chance of winning the match.'.format(k, Px))
break
if __name__=="__main__":
main()
</code></pre>
<p>对于Px=0.98,这将导致</p>
^{pr2}$
<p>对于这个算法,运行时类似于O(n^3),而对于其他算法则是O(2^n)。在</p>