假设有一个源源吐出不同球的机器,只有装下10个球的袋子,每一个吐出的球,要么放入袋子,要么永远扔掉。如何做到机器吐出每一个球之后,所有吐出的球都等概率被放进袋子里。
i为球的序号。i从1开始,小于等于10的时候直接进袋子。i大于10的时候,10/i的几率进袋子;在袋子中的球,1/10的几率淘汰。
代码用golang编写。代码如下:
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().Unix())
times := 100000 //10000次试验
bagBallNum := 10 //袋子中的10个球
ballTotal := 23 //总共吐了多少个球
ballCounts := make([]int, ballTotal+1)
for i := 0; i < times; i++ {
balls := make([]int, bagBallNum)
for j := 0; j < bagBallNum; j++ {
balls[j] = j + 1
}
for j := bagBallNum + 1; j <= ballTotal; j++ {
//10/j的几率放入袋子
if rand.Intn(j) < bagBallNum {
balls[rand.Intn(bagBallNum)] = j
}
}
for j := 0; j < bagBallNum; j++ {
ballCounts[balls[j]]++
}
}
//多次实验,所有球出现的次数应该大体一样
for i := 1; i < ballTotal+1; i++ {
fmt.Println(i, ":", ballCounts[i])
}
}
执行结果如下: