抢红包算法

Python013

抢红包算法,第1张

红包大家都知道,但发出一个固定金额的红包,由若干个人来抢,需要满足哪些规则?

下面实现了两种抢红包的方法:二倍均值法 和 线段切割法。

设剩余红包金额为M,剩余人数为N,那么有如下公式: 每次抢到的金额 = Random(0, M / N * 2) 。

这个公式,保证了每次随机金额的平均值是相等的,不会因为抢红包的先后顺序而造成不公平。

举个栗子:

假设有10个人,红包总额100元。

100 / 10 * 2 = 20,所以第一个人的随机范围是(0,20),平均可以抢到 10 元。假设第一个人随机到 10 元,那么剩余金额是100 - 10 = 90 元。

90 / 9 * 2 = 20,所以第二个人的随机范围同样是(0,20 ),平均可以抢到 10 元。假设第二个人随机到10元,那么剩余金额是90-10 = 80 元。

80/8X2 = 20, 所以第三个人的随机范围同样是(0,20 ),平均可以抢到10元。

以此类推,除了最后一次,每一次随机范围的均值是相等的。

何谓线段切割法?我们可以把红包总金额想象成一条很长的线段,而每个人抢到的金额,则是这条主线段所拆分出的若干子线段。

如何确定每一条子线段的长度呢?由“切割点”来决定。当 N 个人一起抢红包的时候,就需要确定 N-1 个切割点。因此,我们需要做 N-1 次随机运算,以此确定 N-1 个切割点。随机的范围区间是(1, M)。

当所有切割点确定以后,子线段的长度也随之确定。这样每个人来抢红包的时候,只需要顺次领取与子线段长度等价的红包金额即可。

这就是线段切割法的思路。在这里需要注意以下两点:

参考 《漫画:如何实现抢红包算法?》

红包剩余金额为 M

红包剩余数量为 N

这种算法就是每次都在区间[0,M/N×2] 随机取一个数。假设100元红包发10个人,那么合理的做法应该是每个人领到10元的概率相同。

这样推导下去,每个人领到相同金额的概率应该就是相同的了。

第一次生成随机数: k1=(0,sum/n*2) (左开右开区间内的随机数)

第二次生成随机数:k2 = (0,(sum-k1)/(n-1)*2)

第三次生成随机数:k3 = (0,(sum-k1-k2)/(n-2)*2)

第N次生成随机数:kn = sum-k1-...-kn-1

这个算法可以把总金额想象成一条线段,每个人都有机会切一刀,前面的人切剩下的后面的人再接着切,这样越是前面的人截取的长度(理解成领取到的红包金额)越大的概率就越大。