每日算法系列【LeetCode 470】用 Rand7() 实现 Rand10()-阿里云开发者社区

每日算法系列【LeetCode 470】用 Rand7() 实现 Rand10()

2022-06-24 156

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。不要使用系统的 Math.random() 方法。

题目描述

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

不要使用系统的 Math.random() 方法。

思考

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

题解

刚看到这题觉得挺有意思的，再看一脸懵逼，这怎么做？后来看了题解才懂了，原来是这个意思。

题目要求只能给你用 rand7 函数，也就是均匀生成 1 到 7 之间的整数。但是现在要求你生成 1 到 10 之间的整数，那么肯定只生成一次是不够的，因为状态数都不够嘛，那就生成多次看看。

如果生成两次，那么就得到了两个 1 到 7 之间的整数，然后怎么转换为 1 到 10 呢。如果这两个数两两组合，那么可以得到 49 种状态，可以用来表示 1 到 49 这 49 个数字，如果想要让 1 到 10 均匀分布，那么每个数字最多只能分配 4 次。具体分配情况如下所示：

1  2  3  4  5  6  78  9  10 1  2  3  45  6  7  8  9  10 12  3  4  5  6  7  89  10 1  2  3  4  56  7  8  9  10 .  ..  .  .  .  .  .  .

所以平均只需要 2.45 次就可以均匀的采样到 1 到 10 之间的整数啦。那么这背后的数学原理是什么呢？其实就是拒绝采样。

蒙特卡洛方法大家应该都很熟悉了，就是采样来求分布，比如求一个直径为 1 的圆的概率，我们可以用一个边长为 1 的正方形包住它，然后随机往里面扔豆子，扔 10000 个，看最后有多少落在了圆里面，那么除以 10000 就是圆的面积了。

代码

c++

// The rand7() API is already defined for you.
   // int rand7();
   // @return a random integer in the range 1 to 7
class Solution {public:
    int rand10() {
    int r1, r2, num;
    do {
    r1 = rand7(); 
    r2 = rand7();
    num = (r1 - 1) * 7 + r2; 
    } while (num > 40);
    return (num - 1) % 10 + 1;    }
 };