V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xing393939
V2EX  ›  数学

请教一个抽奖的算法

  •  
  •   xing393939 · 196 天前 · 1055 次点击
    这是一个创建于 196 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假设抽奖有两个奖品 A 和 B ,中奖概率都是 50%,我的实现是用随机数来确定每次抽奖中哪个,但是问题是会有误差,比如某次的抽奖统计结果是:A 被抽中 500 次,B 被抽中 471 次。产品经理认为误差有点大,他想要比较精准的概率。

    我现在想实现一个绝对公平的抽奖算法,例如,第一次抽奖可以是随机的,比如中了 B ,那么第二次一定中 A ,第三次一定中 B ,循环往复。

    而这种在只有两个奖品的时候,还是好实现的,问题是奖品可能是三个,四个......,中奖概率也是可以任意分配的,这样的有什么好的算法去实现吗?

    第 1 条附言  ·  196 天前
    我按照自己的想法实现了一个,大家觉得可以吗:

    https://gist.github.com/xing393939/8c487e53b573b9f2795d6eac54e9830b
    15 条回复    2023-11-17 13:13:21 +08:00
    brader
        1
    brader  
       196 天前   ❤️ 1
    数学概率就是这样的啊,只有次数足够大的时候,概率才会比较接近。
    如果非要人为干预的话,你可以设计一个加权概率来纠偏,比如你的理想概率是 a%、b%、c%,然后你还有一个当前的实际概率 a1%、b1%、c1%,那你计算到,比如 a1%比 Z%a 小了超过一定阈值,你就给 a 这个概率加权,要细分,就分多个档次,偏的越多,加权越多
    brader
        2
    brader  
       196 天前
    @brader 手误,Z%a 纠正为 a%
    ricwangcom
        3
    ricwangcom  
       196 天前
    这还需要算法?按请求顺序下发奖品不就行了[狗头],ABABABABABABABABABABABAB
    xing393939
        4
    xing393939  
    OP
       196 天前
    @brader 谢谢,我也是这样想的,我是想问问有没有专门解决这类问题的经典算法。
    R18
        5
    R18  
       196 天前
    奖品总数是固定的吗?如果是这样,就生成好队列。每次都取一个出来,取到哪个是哪个。
    murmur
        6
    murmur  
       196 天前
    如果是公司内部抽奖,领导主动放弃参与,员工随机抽,这就是最公平的
    如果是活动对外抽奖,外人一定不会中特等奖,只能中参与奖

    哪里有绝对公平
    murmur
        7
    murmur  
       196 天前
    你的需求来看不像抽奖,倒像是原神的保底,如果第一次歪了第二个金一定是当期 up
    bsg1992
        8
    bsg1992  
       196 天前   ❤️ 1
    游戏的暴击 PRO 算法 可以参考一下,稍微改一下就能满足你这个需求
    chairuosen
        9
    chairuosen  
       196 天前
    count%2===0?A:B
    whosesmile
        10
    whosesmile  
       196 天前
    你可以设置一个奖品数组:P = [A,B,C,D],然后用随机数选取 [0 - length),选到了就将对应的奖品移除,重置 P 值

    上面是假定每个奖品只有一个,如果你有 500 个 A ,500 个 B ,类似的处理为:
    P = [{A:500}, {B:500}],每次随机 [0, length),然后将对应的奖品数 -1,当触发临界值即 0 时,同样移除,重置 PP
    whosesmile
        11
    whosesmile  
       196 天前
    @whosesmile 抽奖程序如果有并发,肯定要同步锁哈,不然数据对不上;然后 P 的初始化,或者重建,通过库存确定就行了。
    whileFalse
        12
    whileFalse  
       196 天前 via Android
    有那么难吗...
    if random()*(a_remain + b_remain) < a_remain
    then
    a_remain --
    print("A")
    else
    b_remain --
    print("B")
    leonshaw
        13
    leonshaw  
       196 天前
    算出前面已经抽出的每种奖品频率,取目标概率减频率最大的那个
    sillydaddy
        14
    sillydaddy  
       195 天前
    不要改,拿概率论怼给他:

    投掷 1000 次硬币,标准差是 sqrt(1000*0.5*0.5)=15.8 ,那么投掷出正面次数与 500 次之差在 1 个标准差之内的概率大概是 68%,在 2 个标准差之内的概率大概是 95%,在 3 个标准差之内的概率大概是 99.7%。

    具体可以看下面这个正态分布图:
    https://www.shuxuele.com/data/standard-normal-distribution-table.html

    你给的结果,正好卡在 1 个标准差那条线上,是非常正常的情况。如果是 3 个标准差,那么结果就是 A 或 B 抽中 530 ,B 或 A 抽中 440 ,出现类似这种情况的概率大概是 0.3%。
    所以不要那么弱势!!
    sillydaddy
        15
    sillydaddy  
       194 天前
    @sillydaddy 我在上面的回复有点武断。

    今天又思考了一下这个问题,发现有一个很简单的方法,就是增加抽奖的次数。比如你想抽 1000 次分配给 A 和 B ,但觉得抽 1000 次的标准差(你说的误差)太大,那就可以抽 10000 次,然后用 10000 次抽奖的最终结果除以 10 。比如 10000 次里面 A 得 5050 次,B 得 4950 ,分别除以 10 ,得到 A 得 505 次,B 得 495 次。为什么举这个数字呢,因为投掷 10000 次硬币,标准差就是 50 。相比投掷 1000 次时的标准差 15 ,并不是增大到 10 倍,而是只有 3 倍左右。

    除以 10 这个操作,相当于把标准正态分布的图像在 x 轴方向上压扁了,然后在 1 个标准差内的概率就增大了。如果想实时显示抽奖过程,那就累积 A 或 B 的中奖次数,每累积到 10 次,就算作真实中奖 1 次。当抽完 10000 次,A 和 B 真实中奖总次数就是 1000 次。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5204 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 05:50 · PVG 13:50 · LAX 22:50 · JFK 01:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.