通过rand生成1-7之间的随机数(5)

Question

我想写一个算法来生成1-7之间的随机数,给出一个生成1-5之间随机数的方法.

我想到了一个解决方案rand(5)/ 5*7 ??

我认为这应该有效.

谁能告诉我一个最佳解决方案？

我在某处读到了这个解决方案,但我不知道他们怎么想保持"int num = 5*(rand5() - 1)+(rand5() - 1);" .我知道它会在1-7之间生成一个随机数,但是他们如何看待这种逻辑或者他们想要表达的内容并没有进入我的脑海.任何人都可以对此有所了解.

public static int rand7() {
while (true) {
    int num = 5 * (rand5() - 1) + (rand5() - 1);
    if (num < 21) 
        return (num % 7 + 1);
}
}

Answer 1

您发布的代码是接受拒绝算法的示例.表达方式

5 * (rand5() - 1) + (rand5() - 1);

生成一个均匀分布在0到24之间的随机数.第一项是0到4之间随机数的5倍,产生{0,5,10,15,20}集合中的一个概率相等.第二个是0到4之间的随机数.因为这两个随机数可能是独立的,所以加上它们会得到一个均匀分布在0到24之间的随机数.第二个数字"填补"第一项产生的数字之间的差距.

然后,测试拒绝任何21或更高的数字,并重复该过程.当一个数字通过测试时,它将是一个均匀分布在0到20(含)之间的随机数.然后将该范围分成7个数字(0到6之间),% 7并在返回之前添加一个.由于区间[0,20]中有21个数字,并且21可被7整除,因此0和6之间的数字将以相同的概率发生.

在表格中:

A           B              num
rand5()-1   rand5()-1      5 * A + B        num % 7 + 1
---------   ---------      ---------        -----------
0           0              0                1
1           0              5                6
2           0              10               4
3           0              15               2
4           0              20               7
0           1              1                2
1           1              6                7
2           1              11               5
3           1              16               3
4           1              21               reject
0           2              2                3
1           2              7                1
2           2              12               6
3           2              17               4
4           2              22               reject
0           3              3                4
1           3              8                2
2           3              13               7
3           3              18               5
4           3              23               reject
0           4              4                5
1           4              9                3
2           4              14               1
3           4              19               6
4           4              24               reject

请注意,最后一列恰好有[1,6]范围内的每个数字中的三个.

理解逻辑的另一种方法是用base-5算法来思考.由于rand5()生成1到5(含)之间的随机整数,我们可以用来rand5() - 1为base-5数生成随机数.我们试图生成数字1到7(或等价地,0到6),所以我们需要至少两个基数为5的数字才能得到7个数字.因此,让我们生成一个随机的,两位数的基数为5的数字,逐位数字.这是什么5*(rand5() - 1) + (rand5() - 1).然后我们可以一遍又一遍地做到这一点,直到我们得到一个0到6之间的数字(0和11 ₅).但是,拒绝减少我们正在生成的两位数字会更有效率.我们可以通过使用最多(但不包括)最大的两位数,基数为5的数字来实现这一点,该数字是7的倍数.恰好是41 ₅,即21 ₁₀.(我们排除41 ₅本身,因为我们从0开始,而不是1.)因为我们想要一个0到6之间的数字,所以我们使用减少范围% 7.(我们可以还除以3,由于存在正好三个,在[0,40 7-整数范围₅ ].然而,使用求余运算符清楚地表明,我们的目标的范围[0,6]. )

PS您提出的解决方案不起作用.虽然它似乎具有正确的范围,但表达式只能生成五个不同的数字,因此它可能不正确.它也可以产生0(当rand5()返回1时).如果你正在处理浮点随机数生成,那么这样的简单扩展将是一个很好的方法.(但是,您需要在缩放之前切换到0,然后再切换回1以获得范围的正确下限.我认为,表达式将是1 + 7 * (rand5() - 1) / 5.但是rand5()返回一个整数,而不是浮点数.)