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

Question

这是一道面试题：

给定一个在 [1,5] 中生成随机数的函数，我们需要使用该函数在 [1,9] 范围内生成一个随机数。我想了很多，但无法写出满足随机性的方程。人们请回答。这可能对未来的一些采访有帮助。

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 索引随机选择飞镖板上的一个位置，如果我们没有得到好的结果，我们会继续投掷飞镖。

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

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

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