使用给定的随机数生成函数查找随机数生成器

Question

这是一个面试问题：

给定一个在1,5中生成随机数的函数，我们需要使用此函数来生成1,9范围内的随机数。我想了很多，但无法写出满足随机性的方程。人们请answer.This可能会在未来的一些面试中有所帮助。

Answer 1

改编自"Expand a random range from 1–5 to 1–7“

它假定rand5()是一个返回从1到5(包括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索引随机选择了飞镖棋盘上的一个位置，如果我们没有得到好的结果，我们就继续扔飞镖。

这可以在最坏的情况下永远运行，但从统计上讲，最坏的情况永远不会发生。:)

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，too.but，t2==5，discarded.so，t2有1/4的概率为1到4，也就是说，1/2的概率为奇数或偶数，这使得t2%2有1/2的概率为0到1。

因此，t1 + 5*(t2%2)的概率为5/10为1到5，5/10为6到10。但10再次被丢弃，因此其余9个数字的概率为1/9。

Answer 3

您需要使用rejection sampling。也就是说，拒绝不适合您的目标分布的结果。在您的示例中，您可以使用对rand15函数的两次连续调用的低三位(如果需要，则为−1)，将它们连接起来，并拒绝目标间隔之外的那些结果，然后重试，直到找到一个在目标间隔内的数字。