我正在努力優(yōu)化我的代碼以解決以下問題：給你 N 個盒子，索引從 1 到 N。每個盒子要么沒有硬幣，要么包含一枚硬幣?？蘸凶拥臄?shù)量和裝有一枚硬幣的盒子的數(shù)量分別用n0和n1表示。您隨機抽取盒子的子集，其中每個子集都有相同的被選擇概率?？占图媳旧肀灰暈樽蛹?。給定 n0 和 n1，隨機子集中硬幣總數(shù)為偶數(shù)的概率是多少？約束：N = n0 + n1 < 100000例子1輸入：n0 = 1，n1 = 0輸出：1.0解釋：有兩個子集：[]和[0]。兩人的總和相等。2輸入：n0 = 0，n1 = 2輸出：0.5解釋：有四個子集：[]、[1]、[1] 和 [1, 1]。[] 與 [1,1] 之和為偶數(shù)。到目前為止，我嘗試在 Python 3.8 中實現(xiàn)，但我認為它工作正常，但計算更大的數(shù)字需要很長時間。prob = 0n0 = 1n1 = 4for j in range(0, n1+1): if (j % 2 == 0): prob += comb(n1, j)total_prob = (2**n0 * prob) / (2 ** (n0+n1))total_prob
2 回答
青春有我
TA貢獻1784條經(jīng)驗 獲得超8個贊
假設您的算法是正確的，則可以按如下方式分析確定total_prob。
這個總結(jié)：
prob = 0
for j in range(0, n1+1):
if (j % 2 == 0):
prob += comb(n1, j)
正在計算二項式系數(shù)的偶數(shù)項，即：
comb(n1, 0) + comb(n1, 2) + ... + comb(n1, J)
where J is even and J>=n1
J > n1 沒問題，因為對于 J > n1，comb(n1, J) = 0（nCr 的定義）
這個總和就是來源：
prob = 2**(n1 - 1)
代入total_prob方程中的prob：
total_prob = (2**n0) *(2**(n1-1)) / (2 ** (n0+n1))
total_prob = 2**(n0 + n1 - 1)/(2**(n0+n1))
total_prob = 0.5 (always)
拉丁的傳說
TA貢獻1789條經(jīng)驗 獲得超8個贊
import math
def comb(n, k): # Calculates the combination based on n and k values
return math.factorial(n) // math.factorial(n - k) //math.factorial(k)
def question(n0, n1): # probability that the total number of coins in the random subset is even
"""probability of sums of even / total probability"""
p = 0
for i in range(0, n1+1):
if (i % 2 == 0):
p += comb(n1, i)
return p / (2 ** n1)
添加回答
舉報
0/150
提交
取消