题目来源:https://leetcode-cn.com/problems/implement-rand10-using-rand7/
大致题意:
给一个 rand7() 函数,实现一个 rand10() 函数
思路
一开始我想的是,可以将 rand7() * 10 / 7 得到 1-10 之间的数。但是这个方法显然不对:
- 如何得到 3 ?显然没法得出
于是借用了别人的方法。
rand7() 可以等概率生成 1-7 之间的随机整数。再加上一个 rand7() 就可以生成 2 - 14 之间的随机整数,但不是等概率生成,比如 3 可以通过 1+2 和 2+1 生成,但是 14 只可以通过 7+7。
显然这样行不通。
不过可以用这个方法的改进版:
- 使用一个随机函数可与均匀的生成 0 和 7,然后加上 rand7(),且当和大于 10 时重新执行,直至不大于 10
- 这样生成 1- 7 的概率是 0.5 * 1/7,生成 8 - 10 的概率也是如此
- 我们可以通过 (rand7() - 1) * 7 来生成 [0, 7, 14, 21, 28, 35, 42]
- 这样 (rand7() - 1) * 7 + rand7() 生成 1-10 的概率都为 1/7 * 1/7,然后当和大于 10 时重新执行,直至不大于 10
代码:
public int rand10() {
int num;
do {
num = (rand7() - 1) * 7 + rand7();
} while (num > 10);
return num;
}