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

Question

这是一道面试题:

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

Answer 1

改编自“Expand a random range from 1–5 to 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 索引在飞镖板上随机选择一个位置，如果我们没有得到好的结果，我们就继续扔飞镖。

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