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

Question

这是一个面试问题:

给定在[1,5]中生成随机数的函数,我们需要使用此函数生成范围[1,9]中的随机数.我考虑了很多,但我无法写出一个满足ramdomness的等式.人们请回答.这可能在将来的某些采访中有所帮助.

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

在最坏的情况下,这可以永远运行,但从统计上来说,最坏的情况永远不会发生.:)