背景

这要追溯到大四找工作的时候，做面试题，然后有一类关于产生随机数的类型的题目。感觉题目很巧妙，这里整理一下。

这里给出三道题目，希望你看完之后能够豁然开朗，再也不用怕类似的题目。

题目一、如何用一个1-8随机数生成器制作一个1-7随机数生成器？

这是我在知乎上看到的一道题，实际上这道题很简单，从大的随机数制作小的随机数是很简单的。

这种最简单，因为需要生成的随机数是一个子集，所以直接把不在某个范围的去掉就行了。生成的数也是随机的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 先构造一个1-8的随机数生成器，我们使用标准自带的rand函数生成[0,7]然后生成[1,8]
func rand8() int32 {
	return 1 + rand.Int31n(8)
}

func rand7() int32 {
	var result int32
	for {
		res := rand8()
		if res <= 7 {
			result = res
			break
		}
	}
	return result
}

扩展

如果是需要制作一个1-3的随机数生成器呢？ 当然我们也可以把大于3的都去掉，但是去掉的比例越多，循环的次数就越多，效率也就越差。

所以我们可以小于8的3的整数倍的最大值6。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func rand7() int32 {
	var result int32
	for {
		res := rand8()
		if res <= 6 {
			result = res/2  //1-6是随机的，除以一个能整除的数，得到的数也是随机的。
			break
		}
	}
	return result
}

题目二、如何用一个1-7随机数生成器制作一个1-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);
}

个人觉得两种方法有异曲同工之妙，所以大多数利用一个等概率随机数构造另外一个等概率随机数，只需两次使用概率函数即可。

<全文完>