使用给定的随机数生成函数来找到一个随机数生成器

Question

这是一个面试题：

给定一个函数，该函数在[1,5]范围内生成随机数，我们需要使用该函数来生成一个在[1,9]范围内的随机数。 我思考了很多，但无法写出满足随机性要求的方程。 希望有人能回答。也许在今后的面试中会有所帮助。

- doctore

---

你也想要均匀概率分布吗？ - S J

我想这就是随机性的意思。 - doctore

考虑到问题的提出方式，我相当确定它必须产生一个均匀分布。否则，提出这个问题就没有意义。 - Joey

你可以拥有一个不具有均匀概率分布的随机数生成器。一个简单的例子是掷两个六面骰子。它肯定是随机的，但你掷出12的可能性比掷出7要小得多。 - Kevin

这个问题已经被回答了：https://dev59.com/h3VC5IYBdhLWcg3w9GA9 - Lasse V. Karlsen

Answer 1

源自"将1-5的随机数扩展为1-7的方法"。

它假设rand5()是一个返回在1到5（含）范围内的统计随机整数的函数。

int rand9()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 8, 9, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 8, 9, 0, 0 },
        { 0, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result= vals[i-1][j-1];
    }
    return result;
}

它是如何工作的？可以这样想：想象一下在纸上打印出这个二维数组，将它固定在飞镖板上，并随机投掷飞镖。如果你打中了一个非零值，那么它就是一个介于1和9之间的统计随机值，因为非零值的数量相等。如果你打中了零，就继续投掷飞镖，直到你打中一个非零值。代码就是这样做的：i和j索引随机选择飞镖板上的位置，如果我们没有得到好的结果，就不断地投掷飞镖。

在最坏的情况下，这可能会持续运行很长时间，但从统计学角度来看，最坏的情况永远不会发生。 :)

- S J

---

答案来自https://dev59.com/h3VC5IYBdhLWcg3w9GA9?lq=1。 - S J

有点好奇，如果我们有一个生成在 [1,5] 范围内随机数的函数，这是否意味着我们最多只能创建另一个生成 [1,25] 范围内随机数的函数？那么 [1,26] 呢？有可能吗？ - CSnerd

Answer 2

int rand9()
{
    int t1,t2,res = 10;
    do {
        t1 = rand5();
        do {
            t2 = rand5();
        }while(t2==5);
        res = t1 + 5* (t2%2);
    }while(res==10);
    return res;
}

现在数字1到9的概率都是1/9。

解释一下：

t1有1/5的概率是1到5。

t2也是如此，但当t2等于5时被丢弃。所以t2有1/4的概率是1到4。也就是说，t2%2有1/2的概率是0到1，即有1/2的概率是奇数或偶数。

因此，t1 + 5*(t2%2)有5/10的概率是1到5，另外5/10的概率是6到10。但是10再次被丢弃，所以剩下的9个数字的概率是1/9。

- vvy

---

这也不是随机的，数字2和4出现的次数是其他数字的两倍，而9则没有出现。 - Lasse V. Karlsen

我已将“res = t1*(1+ t2%2)”更改为“res = t1+ 5* t2%2”，现在它可以正常工作了。 - vvy

不，它不会。目前的代码产生从1到6的数字（而不是7-9），2-5出现的频率是1和6的两倍。我在这里有一个LINQPad程序，你可以尝试一下，它会向你展示：https://www.dropbox.com/s/p7m9sb4jqto9f15/SO17190340.linq - Lasse V. Karlsen

@LasseV.Karlsen 你是对的，我发现我在 t2%2 外面漏掉了括号，这不是我的原意。当我加上它们并使用 (1+rand()%5) 作为 rand5() 在我的 gcc 中测试该函数时，它能够正常工作。我修复了我的代码并添加了一些说明。 - vvy

Answer 3

你需要使用拒绝抽样。也就是说，拒绝不符合目标分布的结果。在你的情况下，你可以使用两个连续调用你的rand15函数的低三位（如果必要，减去1），将它们连接起来，并拒绝那些超出你目标区间的结果，重试直到找到一个在范围内的数字。

- Joey