关于面试中经常出现的根据一个随机数构造另外的随机数的解法

1 year ago

source link: https://www.leftpocket.cn/post/interview/rand/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

之前做了一些Tencent及几家公司的面试题，发现有一种关于产生随机数的类型的题目。看到多有大牛们做出来，而且效率很高，也有不知道怎么做的，最近根据几个产生随机数的题目整理一下，发现所有的类似题目的解法类似，故分享一下。

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

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

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

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

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()，代码如下：

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()即可。各位可以自己试试。另外，看见一个大牛的方法，似乎比以上更为简单，现贴出代码，供各位欣赏：

其实跟上面的方式类似，只是它是先截取，再计算。把顺序调换了一下。

int rand10()
{
	int temp1;
	int temp2;
	do
	{
		temp1 = rand7();
	}while(temp1>5);
	do
	{
		temp2 = rand7();
	}while(temp2>2);
	return temp1+5*(temp2-1);
}

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

<全文完>

欢迎关注我的微信公众号：码农在新加坡，有更多好的技术分享。