腾讯WXG面试题 生成随机数

问题描述

工行有30万员工，现在要均匀抽出1万员工发奖品，提供一个16位的随机数生成器函数 rand16() 可供随意调用，请写一个函数 selectLuckyStaffs() 实现这个功能。

如何用rand5()生成rand7()

先看一个数据量不这么大的的类似题目，题目描述如下
给你一个能生成1到5随机数的函数，用它写一个函数生成1到7的随机数。 (即，使用函数rand5()来实现函数rand7())。

rand5可以随机生成1,2,3,4,5；rand7可以随机生成1,2,3,4,5,6,7。
rand5生成rand7不太好实现，如果反过来呢？给你rand7，让你实现rand5，这个好实现吗？
一个非常直观的想法就是不断地调用rand7，直到它产生1到5之间的数，然后返回。 这个也是等概率的，每次rand都是独立同分布的。

int rand5()
{
    int x = 0;
    do
    {
        x=rand7();
    }while(x>5);
    return x;
}

可以得到一个一般的结论，如果a > b，那么一定可以用Randa去实现Randb。其中， Randa表示等概率生成1到a的函数，Randb表示等概率生成1到b的函数。

错误的方式（不等概率）

回到原先的问题，现在题目要求我们要用Rand5来实现Rand7，只要我们将Rand5 映射到一个能产生更大随机数的Randa，其中a > 7，就可以套用上面的模板了。 这里要注意一点的是，你映射后的Randa一定是要满足等概率生成1到a的。比如，

Rand5() + Rand5() - 1

上述代码可以生成1到9的数，但它们并不是等概率生成的。

正确的方式（等概率）

我们先给出一个组合，再来进行分析。组合如下：

5 * (Rand5() - 1) + Rand5()

Rand5产生1到5的数，减1就产生0到4的数，乘以5后可以产生的数是：0,5,10,15,20。 再加上第二个Rand5()产生的1,2,3,4,5。我们可以得到1到25， 而且每个数都只由一种组合得到，即上述代码可以等概率地生成1到25。OK， 到这基本上也就解决了。

//生成随机数7；
int rand7()
{
    int x = 0;
    do
    {
        x=5*(rand5()-1) + rand5();//生成1——25之间的数
    }while(x>7);
    return x;
}

上面的代码有什么问题呢？可能while循环要进行很多次才能返回。 因为Rand25会产生1到25的数，而只有1到7时才跳出while循环， 生成大部分的数都舍弃掉了。这样的实现明显不好。我们应该让舍弃的数尽量少， 于是我们可以修改while中的判断条件，让x与最接近25且小于25的7的倍数相比。 于是判断条件可改为x > 21，于是x的取值就是1到21。 我们再通过取模运算把它映射到1-7即可。代码如下：

//生成随机数7；
int rand7()
{
    int x = 0;
    do
    {
        x=5*(rand5()-1) + rand5();//生成1——25之间的数
    }while(x>21);
    return x%7+1;
}

回到原问题

工行有30万员工，现在要均匀抽出1万员工发奖品，提供一个16位的随机数生成器函数 rand16() 可供随意调用，请写一个函数 selectLuckyStaffs() 实现这个功能。

unsigned int rand16(); //供随意调用，返回值 [1 2^16]。

void rand300000(){
	int x = 0;
    do
    {
        x=65536*(rand16()-1) + rand16();
    }while(x>14316*300000);
    return x%300000+1;
}

结论

1、如果a > b，进入步骤2；否则构造Randa2 = a * (Randa – 1) + Randa， 表示生成1到a2 随机数的函数。如果a2 仍小于b，继教构造 Randa3 = a * (Randa2 – 1) + Randa…直到ak > b，这时我们得到Randak , 我们记为RandA。
2、步骤1中我们得到了RandA(可能是Randa或Randak )，其中A > b