从最基础的讲起如何做到均匀的生成随机数 |
您所在的位置:网站首页 › 怎么让随机数在一个范围内 › 从最基础的讲起如何做到均匀的生成随机数 |
题目描述:470. 用 Rand7() 实现 Rand10() 因为是第一次接触到这样的题目,毫无思绪,对官方题解也是“不知道为什么要这么做”。看过一些题解之后才逐渐明白,现在让我自己来写题解,我打算先从简单的开始讲起。 Part 1假设已知rand2()可以均匀的生成[1,2]的随机数,现在想均匀的生成[1,4]的随机数,该如何考虑? 我想如果你也像我一样第一次接触这个问题,那么很可能会这么考虑——令两个rand2()相加,再做一些必要的边角处理。如下: rand2() + rand2() = ? ==> [2,4] 1 + 1 = 2 1 + 2 = 3 2 + 1 = 3 2 + 2 = 4// 为了把生成随机数的范围规约成[1,n],于是在上一步的结果后减1 (rand2()-1) + rand2() = ? ==> [1,3] 0 + 1 = 1 0 + 2 = 2 1 + 1 = 2 1 + 2 = 3可以看到,使用这种方法处理的结果,最致命的点在于——其生成的结果不是等概率的。在这个简单的例子中,产生2的概率是50%,而产生1和3的概率则分别是25%。原因当然也很好理解,由于某些值会有多种组合,因此仅靠简单的相加处理会导致结果不是等概率的。 因此,我们需要考虑其他的方法了。 仔细观察上面的例子,我们尝试对 (rand2()-1) 这部分乘以 2,改动后如下: (rand2()-1) × 2 + rand2() = ? ==> [1,3] 0 + 1 = 1 0 + 2 = 2 2 + 1 = 3 2 + 2 = 4神奇的事情发生了,奇怪的知识增加了。通过这样的处理,得到的结果恰是[1,4]的范围,并且每个数都是等概率取到的。因此,使用这种方法,可以通过rand2()实现rand4()。 也许这么处理只是我运气好,而不具有普适性?那就多来尝试几个例子。比如: (rand9()-1) × 7 + rand7() = result a b为了表示方便,现将rand9()-1表示为a,将rand7()表示为b。计算过程表示成二维矩阵,如下: 可以看到,这个例子可以等概率的生成[1,63]范围的随机数。再提炼一下,可以得到这样一个规律: 已知 rand_N() 可以等概率的生成[1, N]范围的随机数 那么: (rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数 即实现了 rand_XY() part2那么想到通过rand4()来实现rand2()呢?这个就很简单了,已知rand4()会均匀产生[1,4]的随机数,通过取余,再加1就可以了。如下所示,结果也是等概率的。 rand4() % 2 + 1 = ? 1 % 2 + 1 = 2 2 % 2 + 1 = 1 3 % 2 + 1 = 2 4 % 2 + 1 = 1事实上,只要rand_N()中N是2的倍数,就都可以用来实现rand2(),反之,若N不是2的倍数,则产生的结果不是等概率的。比如: rand6() % 2 + 1 = ? 1 % 2 + 1 = 2 2 % 2 + 1 = 1 3 % 2 + 1 = 2 4 % 2 + 1 = 1 5 % 2 + 1 = 2 6 % 2 + 1 = 1 rand5() % 2 + 1 = ? 1 % 2 + 1 = 2 2 % 2 + 1 = 1 3 % 2 + 1 = 2 4 % 2 + 1 = 1 5 % 2 + 1 = 2 Part 3ok,现在回到本题中。已知rand7(),要求通过rand7()来实现rand10()。 有了前面的分析,要实现rand10(),就需要先实现rand_N(),并且保证N大于10且是10的倍数。这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。 而实现rand_N(),我们可以通过part 1中所讲的方法对rand7()进行改造,如下: (rand7()-1) × 7 + rand7() ==> rand49() 但是这样实现的N不是10的倍数啊!这该怎么处理?这里就涉及到了“拒绝采样”的知识了,也就是说,如果某个采样结果不在要求的范围内,则丢弃它。基于上面的这些分析,再回头看下面的代码,想必是不难理解了。 class Solution extends SolBase { public int rand10() { while(true) { int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数 if(num |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |