|
470 用Rand7()实现Rand10()
数学概率题，copy一个评论区大佬的
链接
讲一个万能的方法，可以无脑等概率生成任何数！
几乎不需要用到概率知识！ 几乎不需要用到概率知识！ 几乎不需要用到概率知识！
【步骤】
下面将需要生成的随机数中最大值记为n
先去生成一个等概率产生0和1的方法：rand2() 。
不要去纠结为什么返回值不是1和2，因为方便二进制位运算。
实现：调用 rand7() ，1,2,3 返回1，4,5,6 返回2，7 重来。
将n转为二进制，看看是几位的二进制。
例如本题的 10 ，二进制为 1010 。也就是说仅仅需要4位二进制数就能表示10进制的10。 用这个 rand2() 方法生成n的每个二进制位。
创建一个数为 rand2() ，每次左移一位再加 rand2() 。
如果出现不符合题意的情况，再次调用 rand10() 。
例如如上步骤可能生成 0000 , 1011 、…… 、1111 （分别为0,11、 …… 、15），显然这些都是不在[1,10]中的正整数，所以只能重新生成。
【重难点】
主要理解二进制的每一位出现0和1的可能性都是相同的，所以能生成的每一个数概率都是相同的。
【JAVA代码】
/**
-
The rand7() API is already defined in the parent class SolBase. -
public int rand7(); -
@return a random integer in the range 1 to 7
*/
class Solution extends SolBase { public int rand10() {
int ans = rand2();
for (int i = 0; i < 3; i++) {
ans <<= 1;
ans ^= rand2();
}
return (ans <= 10 && ans > 0) ? ans : rand10();
} public int rand2() {
int ans = rand7();
return ans == 7 ? rand2() : ans % 2;
}
}
【拓展思考】
怎么用一个不等概率生成0和1的方法 rand() 等概率的生成任意数？
注：只是生成0和1的概率不相等，但是每次生成0或1的概率永远是恒定的。（例如生成0概率永远为10%，生成1概率永远为90%）
【思路】
同样是用二进制生成一个能等概率生成0和1的方法 rand2() 。
用 rand() 方法生成的二进制为 01 或 10 分别表示0和1，生成的二进制为 00 或 11 重复上述过程。 其余同本题步骤。
【重难点】
主要理解出现的4种情况中只有 01 或 10 两种情况是等概率的，其余两种情况应该要舍弃。
【代码】
无代码，自己可以动手尝试一下
其中 rand() 函数可以把本题的 rand7() 做改动，1-3返回1，4-7返回2。
【说明】
本人仅为算法爱好者，以上思路均来自左程云老师（侵删）。
如有描述不清楚的地方或者更多算法问题，请留言，看见后第一时间回复。
希望能和大家共同进步！！！
|