前言
阿里的一道随机数生成的题目，这里进行一下解释
题目
给定了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为例，假设：
- 第一次生成1的概率是1/7
- 第二次生存1的概率是4/7 * 1/7，因此第一次肯定是生成了大于3的数例如4,5,6,7,概率是4/7
- 同理，第三次生成1的概率是(4/7)^2 * 1/7
因此，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
扩展
现在给定两个生成随机数的函数rand_a和rand_b，rand_a和rand_b分别产生1-a和1-b的随机数，a和b不相等，现在让你用rand_a实现rand_b，方法如下：
- 如果a>b，则可以直接采用上述方法
- 如果a<b, 则构造rand_a^2=a * (rand_a - 1) + rand_a，表示生成1-a^2的随机数，如果a^2还小于b，那么继续构造rand_a^3=a * (rand_a^2 - 1) + rand_a
举例说明
阿里2014年笔试题目，是给定生成1-7的随即函数rand_7，看是否能生成其它随机数？
我们先看一下是否能等概率生成1-49,构造rand_49 = 7 * (rand_7 - 1) + rand_7 （ps：别问我7从哪里来的，rand_7既然能随即生成1-7,我当然可以获得到7了）
rand_7 - 1能等概率的生成0, 1, 2, 3, 4, 5, 6，每个数的生成概率都是1/7,所以*7之后，可以等概率的生成0,7,14,21,28,35,42,每个数的概率都是1/7
既然0,7,14,21,28,35,42每个数的概率都是1/7,当每个数都加上+rand_7之后，则1-49是等概率产生的，1/7 × 1/7 = 1/49,中间不会出现重复数据
所以，我们用rand_7产生了rand_49，有了rand_49,按照最初上面过滤的方法，我们当然可以获得任何小于49的随机函数
