题目:已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
示例 1:
输入: 1
输出: [7]
示例 2:
输入: 2
输出: [8,4]
示例 3:
输入: 3
输出: [8,1,10]
提示:rand7 已定义。
传入参数: n 表示 rand10 的调用次数。
思路:
(这题刚一看什么鬼,再一看有点思路,再深入要每个数出现概率相同,又不会了,最后看了评论区一个大佬写的,这思路给跪了。生而为人为何他们如此优秀,感叹一下,继续向大佬学习,继续刷题,加油!!!)
要想将随机数扩展到1~10,调用两次rand7,进行累加是必须的,只是得对数数进行筛选。因为最后要求概率相同。
这里令a = rand7() b = rand7() 让a取值范围为[1,6],然后奇偶数各一半,概率1/2, 让b取值为[1,5],到这里也许会好奇这是干嘛,怎么变成1~10?
因为这里让a为偶数时,最后输出b+0,即1~5 每个数概率为 1/2 * 1/5 = 1/10
a为奇数时,最后输出b+5,即6~10 每个数的概率为 1/2 * 1/5 = 1/10
结果: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
a,b | a=偶数,b=1 | a=偶数,b=2 | a=偶数,b=3 | a=偶数,b=4 | a=偶数,b=5 | a=奇数,b=1 | a=奇数,b=2 | a=奇数,b=3 | a=奇数,b=4 | a=奇数,b=5 |
概率 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 | 1/2 * 1/5 = 1/10 |
代码:
// 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 a = rand7();
int b = rand7();
while(a==7){
a=rand7();
}
while(b>5){
b=rand7();
}
return (a&1?0:5)+b;
}
};