背景
之前做了一些Tencent及几家公司的面试题，发现有一种关于产生随机数的类型的题目。看到多有大牛们做出来，而且效率很高，也有不知道怎么做的，最近根据几个产生随机数的题目整理一下，发现所有的类似题目的解法类似，故分享一下。
这里给出三道题目，希望你看完之后能够豁然开朗，再也不用怕类似的题目。
题目一、如何用一个1-8随机数生成器制作一个1-7随机数生成器？
这是我在知乎上看到的一道题，实际上这到底相当简单。从大的随机数制作小的随机数是很简单的。
这种最简单，因为需要生成的随机数是一个子集，所以直接把不在某个范围的去掉就行了。生成的数也是随机的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func rand7() int32 {
var result int32
for {
res := rand8()
if res <= 7 {
result = res
break
}
}
return result
}
// 1->8
func rand8() int32 {
return 1 + rand.Int31n(8)
}
|
题目二、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。
利用随机函数rand()函数生成一个等概率随机生成整数1到5的函数Rand5()，然后根据Rand5()生成Rand7()，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func rand5() int32 {
return 1 + rand.Int31n(5)
}
func rand7() int32 {
var (
n int32
tmp1, tmp2 int32
)
for {
tmp1 = rand5()
tmp2 = rand5()
n = (tmp1-1)*5 + tmp2 //n是可以取1～25的随机数
if n <= 21 {
break
}
}
return 1 + n%7
}
|
算法的关键就是两次运用rand5()
那我们又是怎么保证结果的每一个数字的随机概率是一样的呢。
很简单：
- (tmp1-1)*5，结果只有5种可能:(0,5,10,15,20), 每个的概率是20%
- tmp2，结果也是5种可能：(1,2,3,4,5)，每个的概率是20%
- 我们任选一个数字，比如13，它只有一种构造的可能，那就是10+3，也就是
20%*20%=0.04
这个算法的核心就是 x5，这个5也就是rand5的最大值，它保证了两个随机数的值为任意一个数字的可能性只有一种，可以保证概率的相等性。
我们千万别用两个随机数简单相加，因为相加后，某个数字出现的可能就不只一种了。
比如：rand5+rand5
- 任取一个数字7，可能是2+5，3+4，4+3，5+2，四种可能。概率是6/25=24%
- 任取一个数字10，可能只可能是5+5，一种可能。概率是1/25=4%
题目三、已知rand7() 可以产生 1~7 的7个数（均匀概率），利用rand7() 产生rand10()
解法与上面类似，同样只用两个rand7()生成rand10()即可。各位可以自己试试。
另外，看见一个大牛的方法，似乎比以上更为简单，现贴出代码，供各位欣赏：
其实跟上面的方式类似，只是它是先截取，再计算。把顺序调换了一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int rand10()
{
int temp1;
int temp2;
do
{
temp1 = rand7();
}while(temp1>5);
do
{
temp2 = rand7();
}while(temp2>2);
return temp1+5*(temp2-1);
}
|
个人觉得两种方法有异曲同工之妙，所以大多数利用一个等概率随机数构造另外一个等概率随机数，只需两次使用概率函数即可。
<全文完>
|
