关于红包算法的问题

2016-07-24 23:28:39 +08:00
 Exin

微信抢红包大家都很熟悉。

现在考虑这样一种情况:将 100 元的红包分为 10 份,每份最低 5 元最高 15 元,金额精确到 0.01 元。那么如果算法没问题的话,每个人的期望值自然是平均值,即 100 元 /10 人=10 元 /人。

最先想到的算法:

在 5~15 内生成随机数,即为当前用户的红包值。这种方式会出现分配后余额不足以按要求继续分配(剩余过多或过少)的情况,导致之后的红包内容均为最大值或最小值。这似乎也是微信红包的算法。

后来考虑了一种避免后期红包数值统一于极值的方式:

根据红包总份数 N 生成 N 个 0~1 内的随机数,按照各随机数在这些随机数之和中所占的比重,分配可分配的那部分金额(总金额 - 最小值 * 份数)。当出现不符合分配要求的情况时,对已求得的每个随机数进行求根运算(也可以是其他运算,只要减小方差就行)并重新求和。(代价是必须一次性得出所有红包的分配方案)

然后问题来了:

我统计了上述两种方法都结果,均没有出现众数集中在平均值的结果:

算法 1:

算法 2:

按我的理解,众数应当接近于期望值才比较理想。求大神指导下问题所在,以及有没有更好的算法

3540 次点击
所在节点    问与答
44 条回复
cszhiyue
2016-07-25 23:23:15 +08:00
@Exin 忽略了边界
已经修正
Exin
2016-07-26 00:20:32 +08:00
@cszhiyue 谢谢
你的算法最“特别”的地方在于用了高斯随机数,我一直在弄 0~1 均匀分布的随机因子,难怪想破头

我该去看看如何实现高斯随机数了
RqPS6rhmP3Nyn3Tm
2016-07-26 02:41:45 +08:00
这不就是正态分布图吧
Exin
2016-07-26 10:44:59 +08:00
@BXIA 正态分布是左右对称的吧,我想要的是不对称但平滑简单的曲线。 41L 的比较接近,但是最大那边的图形还是让我不太满意

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/294633

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX