给定方法 rand7
可生成 [1,7]
范围内的均匀随机整数,试写一个方法 rand10
生成 [1,10]
范围内的均匀随机整数。
你只能调用 rand7()
且不能调用其他方法。请不要使用系统的 Math.random()
方法。
每个测试用例将有一个内部参数 n
,即你实现的函数 rand10()
在测试时将被调用的次数。请注意,这不是传递给 rand10()
的参数。
示例 1:
输入: 1 输出: [2]
示例 2:
输入: 2 输出: [2,8]
示例 3:
输入: 3 输出: [3,8,10]
提示:
1 <= n <= 105
进阶:
rand7()
调用次数的 期望值 是多少 ?- 你能否尽量少调用
rand7()
?
本质数学概率题。
枚举如下:
a 1 2 3 4 5 6 7
b
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 0
4 5 6 7 8 9 0 1
5 6 7 8 9 0 1 2
6 7 8 9 0 1 2 3
7 8 9 0 1 2 3 4
去掉右上角的
6 7 8
7 8 9
8 9 0 后
每个数字的出现次数为4次,0-9的概率相同
所以程序思路就很明了,当结果扫到右上角的时候进行递归调用,直到输出其他结果
a=rand7(); b=rand7();
if(a>4&&b<4) return rand10();
else return (a+b)%10+1;
平均调用2.45次rand7(),
(
PS:解释一下为什么是2.45............拉开看
分布列如下:调用次数为1次,P=40/49;2次P=(9/49)*(40/49); 3次P=(9/49)^2*(40/49); ............N次 P=(9/49)^(n-1)*(40/49);
平均调用次数为期望==(次数*概率)求和==1*40/49+2*(9/49)*(40/49)+(9/49)^2*(40/49)+...............+n*(9/49)^(n-1)*(40/49);
求出后结果为2*49/40=2.45
)
// 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 temp1=rand7(); int temp2=rand7(); if(temp1>4&&temp2<4) return rand10(); return (temp1+temp2)%10+1; } };
标签:输出,调用,示例,int,rand10,Rand10,rand7,470,Rand7 From: https://www.cnblogs.com/zzzlight/p/16916540.html