【算法面试高频题】rand7()问题

# 1. 题目
已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10()随机1~10。


# 2. 解析
这道题主要是考察的对概率的理解。

要保证rand10()在整数1-10的均匀分布，可以构造一个1-10*n 的均匀分布的随机整数区间（n为任何正整数）。假设x是这个1-10*n区间上的一个随机整数，那么x%10+1就是均匀分布在1-10区间上的整数。由于(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数（原因见下面的说明），可以将41～49这样的随机数剔除掉，得到的数1-40仍然是均匀分布在1-40的，这是因为每个数都可以看成一个独立事件。

在进入题目之前，我想先给读者举个例子。设想一个简单的例子，假设已知rand2()可以均匀的生成[1,2]的随机数，现在想均匀的生成[1,4]的随机数，该如何做呢？

我想如果你也像我一样第一次接触这个问题，那么很可能会这么考虑——令两个rand2()相加，再做一些必要的边角处理。如下：

rand2() + rand2() = ? ==> [2,4]
   1    +   1     = 2
   1    +   2     = 3
   2    +   1     = 3
   2    +   2     = 4

// 为了把生成随机数的范围规约成[1,n]，于是在上一步的结果后减1
(rand2()-1) + rand2() = ? ==> [1,3]
   0       +   1     = 1
   0       +   2     = 2
   1       +   1     = 2
   1       +   2     = 3


可以看到，使用这种方法处理的结果，最致命的点在于——其生成的结果不是等概率的。在这个简单的例子中，产生2的概率是50%，而产生1和3的概率则分别是25%。原因当然也很好理解，由于某些值会有多种组合，因此仅靠简单的相加处理会导致结果不是等概率的。

仔细观察上面的例子，我们尝试对 (rand2()-1) 这部分乘以 2，改动后如下：

(r

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

60) return 1 + num % 10;
        // 说明刚才生成的在61-63之间，利用随机数再操作一遍
        num = (num - 60 - 1) * 7 + rand7();
        if(num <= 20) return 1 + num % 10;
    }   
}


# 归纳总结 randm()->randn()
已知random_m()随机数生成器的范围是[1, m] 求random_n()生成[1, n]范围的函数，m < n && n <= m*m 一般解法：

int random_n()
{
    int val = 0;
    int t;   //t为n的最大倍数，且满足t<m*m
    do
    {
        val = m * (random_m() - 1) + random_m();
    }while(val > t);
    return val;
}

楼主厉害，学到了

楼主厉害，非常感谢

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies