随机数生成有关问题

随机数生成问题

前言

阿里的一道随机数生成的题目，这里进行一下解释

给定了rand7,如何生成rand3？

一个非常直观的思路，就是不断的调用rand7,直到它产生1-3之间的数，然后返回。代码如下：（如果有同学说这里没有3,但是不代表我不能判断和3的大小比较吧）

#include <stdio.h>

int rand_3()
{
	int x;

	while (x = rand_7()) {
		if (x <= 3) {
			return x;
		}
	}
}

接下来，就是判断rand_3是否能等概率的产生1,2,3.也就是我们需要计算产生1,2,3的概率是否都是1/3.

首先，rand_7可以等概率的产生1-7,我们以rand_3生成1为例，假设：

因此，rand_3生成1的概率是P(x=1)= 1/7 + (4/7) * 1/7 + (4/7)^2 * 1/7 + ... + (4/7)^n-1 * 1/7 //等比数列

= 1/7 * ((1 - (4/7)^n) / 1 - 4/7) = 1/7 * 7/3 = 1/3

同理，可验证生成2,3的概率均为1/3

上述证明说明rand3可以等概率的产生1,2,3.从上面的分析，我们可以得出一个更一般的结论：

如果a>b,我们一定可以用rand_a去实现rand_b.其中，rand_a是等可能的生成1-a,rand_b是等可能的生成1-b