sillydaddy 最近的时间轴更新
sillydaddy

sillydaddy

V2EX 第 472822 号会员,加入于 2020-02-27 19:30:20 +08:00
今日活跃度排名 3145
让人困惑的浮点精度和误差
问与答  •  sillydaddy  •  17 小时 42 分钟前  •  最后回复来自 UN2758
6
react 怎样处理父元素的 blur 事件啊??
React  •  sillydaddy  •  12 天前  •  最后回复来自 sillydaddy
7
网易邮箱看样子要沉,要抓紧时间备份啊
分享发现  •  sillydaddy  •  20 天前  •  最后回复来自 firefox12
24
有没有一种知识管理工具,满足这些特性?
问与答  •  sillydaddy  •  78 天前  •  最后回复来自 vsitebon
38
发现公司这样做,竟然可以不用违反劳动法
职场话题  •  sillydaddy  •  104 天前  •  最后回复来自 rick2c
38
sillydaddy 最近回复了
6 小时 35 分钟前
回复了 susanzhou 创建的主题 奇思妙想 一天一年(历史内容创业)
“这样至少能写 10 年”,哈哈,好主意
1 天前
回复了 Vlings 创建的主题 奇思妙想 寻程序员极客
@Vlings 拜托!! 不要什么都发“奇思妙想”节点!!

@Livid 建议挪动节点
5 天前
回复了 masker 创建的主题 生活 好模糊的返乡政策
@IGJacklove 哈哈,不粘锅! 你为什么这么有创意呢
7 天前
回复了 catvoo 创建的主题 互联网 ??反咬一口
没脸没皮,没心没肺!!
@kaiki
@chengfeng1992
@XiaoxiaoPu
@JeffGe
@fbxshit

想了一下,找到了一个我认为正确的方法。
但基本原理很简单,就是类似前面提到的,在多边形内随机采样取点。

先看一下为什么发红包跟多边形取点会关联起来,举例来说,发红包的条件可以表示为:
x+y+z=11,(给 3 个人发 11 元红包)
x>=2, x<=8, y>=2, y<=8, z>=2, z<=8,
(给每个人发的红包在 2 和 8 之间)

用几何的观点来看,这几个条件表示的是,使用一个立方体(x,y, z 的范围都在 2 ~ 8 之间),去截取一个平面,平面的方程为 x+y+z=11 。平面被立方体截取的部分(在立方体内的),就是满足题目要求的解。然后求一个随机解就变成了在被截取的平面上随机采样采点。

如果把这个图形画出来,会发现平面被立方体所截得的图形是一个等边三角形。三个顶点分别是(2,2,7),(2,7,2),(7,2,2)

所以,现在的问题变成了:已知一个三角形(凸多边形),怎么才能做到均匀采样其内部的点?
这个就要感谢凸集的美好性质了:凸集内部的任何一点都可以唯一表示成凸集顶点的线性组合。
假设三角形的三个顶点分别是 P0, P1, P2,那么三角形内部的任一点,可以唯一表示为 a*P0+b*P1+c*P2,其中 a+b+c=1 。
所以要想随机采样三角形内部的点,只要随机取 a,b,c 这三个数,保证和为 1 即可。

上面是 3 维的简单情形,如果发红包给更多的人,就变成了更高维的,但原理是一样的。原来的平面变成了高维平面,原来的立方体变成了高维立方体。关键是求出立方体在平面上截得的顶点。找到所有的顶点后,对这些顶点线性组合就 ok 了。
@chengfeng1992,#28,采样不均匀的话,把结果重排还是不均匀吧。


@cassyfar,#37,最小值最大值只是一个约束吧,并不一定要求一定要取到最小或最大值。
@chengfeng1992
我前面说的主要不是最后一个值越界的问题,而是结果不随机的问题。
你可以运行一下自己的程序,多次运行以后,计算出各个人得到的红包平均数,看是不是相等的。如果不相等说明红包算法随机性有问题。

我可以举个肉眼可见的例子,
x=11,y=3,a=1,b=5,意思就是 11 元红包分给 3 个人,最小 1 元,最大 5 元。
简单看一下 3 个人分得的红包分布
1,5,5
2,4.5,4.5
3,4,4
4,3.5,3.5
5,3,3
可以看出来,后面抽红包的两个人,他们的平均期望值是 4,而第一个人的期望只有 3 。
这说明这种算法不是均匀随机的。
@sillydaddy
@XiaoxiaoPu
好吧,那篇文章我也看不懂!!
但楼上的方法都是错的,这点我可以坚持。
贴个现成的答案吧。楼上的方法都不对。

“生成满足约束的随机数的方法”
https://blog.csdn.net/maintony/article/details/88540320
关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1137 人在线   最高记录 5497   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 22ms · UTC 21:29 · PVG 05:29 · LAX 13:29 · JFK 16:29
♥ Do have faith in what you're doing.