2021-04-06:假设有一个源源吐出不同球的机器,只有装下10个球的袋子,每一个吐出的球,要么放入袋子,要么永远扔掉。如何做到机器吐出每一个球之后,所有吐出的球都等概率被放进袋子里。

福大大架构师每日一题 · · 131 次点击 · · 开始浏览    

2021-04-06:假设有一个源源吐出不同球的机器,只有装下10个球的袋子,每一个吐出的球,要么放入袋子,要么永远扔掉。如何做到机器吐出每一个球之后,所有吐出的球都等概率被放进袋子里。

福大大 答案2021-04-06:

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])
    }

}

执行结果如下:


image.png

左神java代码


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

131 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传