ddef coin_new():
while True:
a = coin()
if coin() != a:
return a
完整測試代碼：
def coin():
return 0 if random.randint(1,10) > 4 else 1
def coin_new():
while True:
a = coin()
if coin() != a:
return a
if __name__ == '__main__':
a = 0
b = 0
n = 100000
for _ in range(n):
if coin_new():a += 1
if coin():b += 1
print(f"1:{a/n},1:{b/n}")
def coin_new():
while True:
a, b = coin(), coin()
if a b: return 0
if a | b: return 1
P(0) = 0.3，P(1) = 0.7
每拋一次硬幣，會得到二進(jìn)制數(shù)的一位，連續(xù)拋 4 次硬幣，可以等概率生成 [0, 15] 的每個數(shù)，記為 x。去掉 [10, 15]，剩下 [0, 9] 的每個數(shù)依然是等概率的。如果 x ∈ [ 0 , 2 ] x \in [0, 2] x∈[0,2]，返回 0； x ∈ [ 4 , 9 ] x \in [4, 9] x∈[4,9]，返回 1； x ≥ 10 x ≥ 10 x≥10，重復(fù)上述過程。
def coin_new():
while True:
x = 0
for _ in range(4):
x = (x 1) + coin()
if x = 2: return 0
if x = 9: return 1
總結(jié)
每拋一次硬幣，會得到二進(jìn)制數(shù)的一位，連續(xù)拋 k 次硬幣，可以等概率生成 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1] 的每個數(shù)在 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1][ 中，選取 m 個數(shù)返回 0，n 個數(shù)返回 1，則 0、1 的概率分別為 m m + n \frac{m}{m+n} m+nm 、 n m + n \frac{n}{m+n} m+nn。
關(guān)于 k 的選擇，最少需要滿足 N = 2 k − 1 N = 2^k-1 N=2k−1，N 是生成對應(yīng)概率分布至少需要多少個不同數(shù)字。比如要生成 1/3、2/3 的分布，至少需要 3 個不同數(shù)字，則 N = 3, k = 2；要生成 3/10、7/10 的分布，至少需要 10 個數(shù)字，則 N = 10, k = 4。
k 最多則沒有限制，我們總可以通過拋更多次硬幣來解決問題，只需要把無用的數(shù)字舍棄即可。但我們的目的是盡可能減少無用數(shù)字的比例，因為每次遇到無用數(shù)字時，都需要重新生成新的數(shù)字。
def rand10():
while True:
x = (rand7() - 1) * 7 + (rand7() - 1)
if 1 = x = 40:
return x % 10 + 1
x = (x % 40) * 7 + rand7() # 1~63
if x = 60: return x % 10 + 1
x = (x - 61) * 7 + 7 # 1~21
if x = 20: return x % 10 + 1
每次 while 執(zhí)行的時候，只有 1 個無用數(shù)字（21）會被舍棄，重新執(zhí)行的概率很低。
RandM 生成 RandN
已知 RandM() 可以等概率的生成 [0, M-1] 范圍的隨機(jī)整數(shù)，那么執(zhí)行 k 次，每次都得到 M 進(jìn)制的一位，可以等概率生成 [ 0 , M k − 1 ] [0, M^k-1] [0,Mk−1] 范圍的隨機(jī)整數(shù)，記為 x。
RandN 至少需要 N 個均勻隨機(jī)整數(shù)，因此只需要取 k，使得 M k − 1 > = N M^k-1 >= N Mk−1>=N 即可，此時有多種方式得到 RandN：
一種是只在 x ∈ [ 0 , N − 1 ] x \in [0, N-1] x∈[0,N−1] 時返回 x，另一種是利用取余運(yùn)算，在保證等概率的前提下，盡可能多的利用生成的數(shù)字，從而減少舍棄的數(shù)字比例，降低 while 重復(fù)執(zhí)行的概率。
