挺有技巧：与概率相关的题目

1、一个随机数产生器以概率p生成0，以概率(1-p)生成1，怎样生成等概率的0和1？

如果用这个随机数产生器产生两个位，出现00的概率为，出现01的概率为，出现10的概率为，出现11的概率为。看到没有，出现01和10的概率相等。那么我们就可以用这个随机数生成器每次产生2位，直到产生的是01或者10，当为01时，输出0，当为10时输出1。

问题扩展：还是给这么一个随机数产生器，要求等概率地产生。

解法1：每次产生n位，当为仅第一位是1，其他是0时输出1，当仅有第二位是1，其他位是0是输出2，……当仅有第n位是1，其他是0时输出n。（这个解法有点0疼，好多信息都浪费了，复杂度太高了）

解法2：从原问题的解答中，我们可以成功地得到等概率产生0和1的，求一下n-1二进制表示的位数，比如为k。那么我们每次等概率生成k位二进制数，将这k位二进制组装成一个数，如果这个数在0~n-1的范围内，输入这个数+1，否则重复产生。

2、不重复随机数的产生

我们可以把这题稍微细化一点，随机产生0~n-1中的k个不重复的随机数。

解法1：最容易想到的方法就是，用一个集合来装这些随机产生的数，当这个集合的大小不为k的时候，就没完没了的随机产生并add到集合中。真正这么干过的童鞋会发现这个办法是不行的，当k稍微大一点，这个程序就跑步出来了。

解法2：开辟一个长度为n的数组a，向其中装入0~n-1，然后随机产生一个0~n-1的数x，将a[x]与a[n-1]交换，并将a[n-1]输出，接下来随机产生一个0~n-2的数y，将a[y]与a[n-2]交换，并将a[n-2]输出，知道输出了k个数为止……代码实现参考。

3、给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数

解法1：

产生K个数(k>1) 假定产生的数分别为n1,n2,n3,n4…那么定义产生的数为n1-1+（n2-2）*5+（n3-1）*5^2+（n4-1）*5^3……..于是产生的数位于区间（0，5^k-1)。然后把5^k分成k等分，产生的数位于哪个等分就是那个产生的随机数（0~6），然后+1即可。如果位于k等分的余数范围，则重新执行一次上述过程。不用担心余数问题，当k取3时落到余数范围的概率就已经降低为6/125，而且余数不会导致概率的问题，只是会影响效率。（相当于5进制）

解法2：

通过rand5()*5+rand5()产生6 7 8 9 10 11……26 27 28 29 30这25个数，每个数出现的概率相等，去前面3*7个数，舍弃后面的4个数，将6 7 8转化成1， 9 10 11转化成2，……，公式：(a-3) / 3，其实跟解法1是一样的，包装一下而已。

4、如何随机选取1000个关键字

给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

定义长度为1000的数组。对于数据流中的前1000个关键字，显然都要放到数组中。对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。

PS：关于1000/n的概率问题，可以这样来，随机生成1~n的数，如果是在1~1000内那么就替换相应位置

5、在半径为1的圆中随机选取一点

解法1：

假设圆心在(0,0)。在x轴[-1, 1]，y轴[-1, 1]的正方形内随机选取一点。然后判断此点是否在圆内（通过计算此点到圆心的距离）。如果在圆内，则此点即为所求；如果不在，则重新选取直到找到为止。正方形的面积为4，圆的面积为pi，所以正方形内的随机点在圆内的概率是 pi / 4。

解法2：

从[0, 2*pi)中随机选一个角度，对应于圆中的一条半径，然后在此半径上选一个点。但半径上的点不能均匀选取，选取的概率应该和距圆心的长度成正比，这样才能保证随机点在圆内是均匀分布的。

关于不均匀选取问题：在一个直角三角形（斜边长pi，直角边长为1）斜边上随机选一点，然后投影到长为1的直角边应该满足条件。

、、

小桥流水 | | 2010 年 07 月 29 日 | 125次阅读

给定一个数组，要求你把数组的顺序随机打乱，然后输出，主要是要保证效率。

这个算法其实简单，首先从所有元素中选取一个数与第一个进行交换，然后在2至n中选择一个元素与第二个交换，直到最后一个元素。

这样能确保每个元素在每个位置的概率都是1/n。代码如下：

void random(int a[], int n)   {     int index, tmp, i;   srand(time(NULL));     for (i = 0; i <n; i++)     {     index = rand() % (n - i) + i;       if (index != i)       {      tmp = a[i];      a[i] = a[index];     a[index] = tmp;       }      }   }   int main()   {      int a[] = {1, 2, 3, 4, 5};      int i;     random(a, 5);      for (i = 0; i < 5; i++)    printf("%d ", a[i]);   printf("");    system("pause");   return 0;   }

概率分析（证明）：每个元素在第一个的位置是1/n，这是毫无疑问的。第一次交换时，一个元素不在第一个位置的概率是(n-1)/n。所以当第二次交换时，一个元素在第二个位置的概率是(n-1)/n*1/n-1=1/n。同时，一个元素不在第一个第二位置的概率是多少呢？很显然是1-1/n-1/n=(n-2)/n。那么在第三次交换时，一个元素在第三个位置的概率就是(n-2)/n*1/(n-2)=1/n。依此类推……

ps：当然你也可以反着来，首先从1…n中随机选取一个元素与第n个交换，然后从1…n-1中随机选取一个元素与第n-1个交换，依此类推……