Rand7实现Rand10

题目:

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

进阶:

  1. rand7()调用次数的期望值是多少?
  2. 你能否尽量少调用rand7()

提示:

  • rand7已定义。

解析:

  利用rand7我们可以得到1 ~ 7的数字,所以能否利用rand7我们可以生成一个范围更大的且每个数字等概率的随机数呢?
  答案是能,我们能用7*(rand7()-1)等概率生成0, 7, 14, 21, 28, 35, 42再加上rand7()-1生成的0 ~ 6,于是就构成了0~48总共49个数字的等概率数字。剔除最后9个,剔除原因是因为最后9个数字构不成一组10个,算上的话会降低数字10被选中的概率。

  • rand7()调用期望值:

期望 = \sum_{i=1}^n 2n(\frac{40}{49}\cdot(\frac{9}{49})^{n-1}) = 2\cdot\frac{49}{40} = 2.45

代码:

int rand10() {
    while(true){
        int num = 7 * (rand7() - 1) + (rand7() - 1);
        if(num < 40)
            return num % 10 + 1;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容