转载http://noalgo.info/414.html
概率论是计算机科学非常重要的基础学科之一，概率题也是在程序员求职过程中经常遇到的问题。
以下总结若干经典的概率题，作为练习。
1. 在半径为1的圆中随机选取一点。
方法1：在x轴[-1,1]，y轴[-1,1]的正方形随机选取一点，如果此点在圆内，则即为所求的点。如果不在圆内，则重新随机直到选到了为止。
方法2：从[0, 2*pi)随机选取一个角度，再在这个方向的半径上随机选取一个点。但半径上的点不能均匀选取，选取的概率要和离圆心的距离成正比，这样才能保证随机点在圆内是均匀分布的。
2. 一根木棒，截成三截，组成三角形的概率是多少？
设第一段截x，第二段截y，第三段1-x-y。
考虑所有可能的截法。可能的截法中必须保证三条边都是正数且小于原来边长，则有0<x<1，0<y<1，0<1-x-y<1，画图可知，(x,y)必须在单位正方形的左下角的半个直角三角形里，面积为1/2。
然后考虑能形成三角形的截法。首先要满足刚才的三个条件0<x<1，0<y<1，0<1-x-y<1，然后必须符合三角形的边的要求，即两边之和大于第三边，x+y>1-x-y，x+1-x-y>y，y+1-x-y>x，化简即得
0<x<1/2，0<y<1/2，1/2<x+y<1
画图可知，此时(x,y)必须在边长为1/2的三角形的右上角的半个直角三角形里，面积为1/8。
于是最终概率为 (1/8)/(1/2) = 1/4。
3. 抛一个六面的色子，连续抛直到抛到6为止，问期望的抛的次数是多少。
因为每次抛到6的概率相等，都是1/6，于是期望的次数就是1/(1/6)=6次。
下面用一种不一样的方法解答，假设期望的次数为E。考虑第一次抛，如果已经抛到6了（概率为1/6），那么就不用再抛了。如果没抛到6（概率为5/6），那么还需要继续抛，可是还要抛多少次呢？显然，现在开始知道抛到6的次数仍然是E，但是刚刚已经抛了一次了于是可以得到这个等式
E = 1 * 1/6 + (1 + E) * 5/6，
解得 E = 6。即期望的次数为6次。
4. 一个木桶里面有M个白球，每分钟从桶中随机取出一个球涂成红色（无论白或红都涂红）再放回，问将桶中球全部涂红的期望时间是多少？
令桶中有i个红球后再把全部球涂红的期望时间为a[i]，此时再取出一个球，如果是红色的（概率为i/M），则直接放回，且剩余的期望时间仍是a[i]。如果是白色的（概率为1-i/M），则涂红后放回，剩余的期望时间为a[i+1]，则
a[i] = (1 + a[i]) * i/M + (1 + a[i+1]) * (1 – i/M)
即 a[i] = a[i+1] + M/(M-i)
显然，有a[M] = 0
可以解得 a[0] = M/M + M/(M-1) + … + M/1 + 0
5. 你有一把宝剑。每使用一个宝石，有50%的概率会成功让宝剑升一级，50%的概率会失败。如果宝剑的级数大于等于5的话，那么失败会使得宝剑降1级。如果宝剑的级数小于5的话，失败没有效果。问题是：期望用多少个宝石可以让一把1级的宝剑升到9级？
问题比较简单，用a[i]表示从第i-1级升到第i级期望使用的宝石数量。
当i<=5时，因为不会降级，则期望的数量均为2，即a[2] = a[3] = a[4] = a[5] = 2
当i>5时，因为会降级，成功时一个宝石就够了，不成功时需要倒退一级，需要先使用a[i-1]个宝石先回到i-1级，再使用a[i]个宝石升到第i级，即
a[i] = 1 * 1/2 + (1 + a[i-1] + a[i]) * 1/2
即 a[i] = a[i-1] + 2
可知，a[6]= 4, a[7] = 6, a[8] = 8, a[9] = 10
则1级到9级需要的宝石数为 a[2]+…+a[9] = 36。
6. 已知有个rand7()的函数，返回1到7随机自然数，怎样利用这个rand7()构造rand10()，随机1~10。
产生随机数的主要原则是每个数出现的概率是相等的，如果可以得到一组等概率出现的数字，那么就可以从中找到映射为1~10的方法。
rand7()返回1~7的自然数，构造新的函数 (rand7()-1)*7 + rand7()，这个函数会随机产生1~49的自然数。原因是1~49中的每个数只有唯一的第一个rand7()的值和第二个rand7()的值表示，于是它们出现的概率是相等。
但是这里的数字太多，可以丢弃41~49的数字，把1~40的数字分成10组，每组映射成1~10中的一个，于是可以得到随机的结果。
具体方法是，利用(rand7()-1)*7 + rand7()产生随机数x，如果大于40则继续随机直到小于等于40为止，如果小于等于40，则产生的随机数为(x-1)/4+1。
7. 已知有个randM()的函数，返回1到M随机自然数，怎样利用这个randM()构造randN()，随机1~N。
上题的扩展。
当N<=M时可以直接得到。
当N>M时，类似构造(randM()-1)*M + randM()，可以产生1~M^2（即randM^2），可以在M^2中选出N个构造1~N的映射。
如果M^2还是没有N大，则可以对于randM^2继续构造，直到成功为止。
8. 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它产生0和1的概率均为1/2。
考虑连续产生两个随机数，结果只有四种可能：00、01、10、11，其中产生01和产生10的概率是相等的，均为p*(1-p)，于是可以利用这个概率相等的特性等概率地产生01随机数。
比如把01映射为0,10映射为1。于是整个方案就是：
产生两个随机数，如果结果是00或11就丢弃重来，如果结果是01则产生0，结果是10则产生1。
9. 已知一随机发生器，产生的数字的分布不清楚，现在要你构造一个发生器，使得它产生0和1的概率均为1/2。
思路类似，考虑连续产生两个随机数a、b，结果有三种情况a==b，a>b，a<b，其中由于a和b的对称性，a>b和a<b出现的概率是相等的，于是可以利用这个概率相等的特性等概率地产生01随机数。方法类似。
或者可以找到另一种概率相等的事件，比如选择一个阈值th，把随机数的结果分为小于阈值和大于等于阈值两种情况，于是连续产生两个随机数，他们一个小于阈值，另一个大于等于阈值的概率是相等。然后类似产生随机数。
10. 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，构造一个发生器，使得它构造1、2、3的概率均为1/3；…。更一般地，构造一个发生器，使得它构造1、2、3、…n的概率均为1/n。
此时我们已经知道，要从n个数中等概率地产生一个随机数，关键是要找到n个或更多个出现概率相等的事件，然后我们重复随机地产生事件，如果是跟这n个事件不同的事件直接忽略，直到产生这n个事件中的一个，然后就产生跟这个事件匹配的随机数。由于n个事件发生的概率相等，于是产生的随机数的概率也是相等的。
考虑连续产生x个随机数，结果应该是x个0跟1的组合，为了使某些结果出现的概率相等，我们应该要让这个结果中0和1出现的次数相等，即各占一半。于是x的长度必须是偶数的，为了方便，考虑连续产生2x个随机数。每个0跟1各出现一半的结果可以赋予1到n的某个数，为了能够表示这n个数，需要0跟1各出现一半的总结果数大于等于n，即
C(2*x, x) >= n
解出最小的x即为效率最高的x。
然后把前n个0和1个出现一半的结果分别赋予1到n的值。随机时连续产生2*x个数，如果不是这n个结果中的一个则重新随机，如果是的话则产生对应的值作为随机结果。
11. 给出从n个数中随机选择m个数的方法。n很大，可以认为是亿级别。m可以很小，如接近1；也可以很大，如接近n。
一个直接的思路是一直重复地随机，直到随机到m个数为止。这个方法有两个弊端：
- 难以直到后面随机到的一个数是否在前面已经随机过了，因为数据量很大，无法保存在内存中，如果保存到外存中则时间花费太大。
- 如果m很大，甚至接近于n，则后面随机到的数字基本上都是前面随机过的，因而需要尝试的随机次数太多。
一个思路是每个数被选中的概率是m/n，则可以遍历一遍原数据，在遍历每个数字的同时以m/n的概率决定是否要选择当前数字，则当遍历完毕的时候，选择到的数字在平均意义就是m个。这个会随着n的增大而更好地趋近于m，但不能很精确地保证随机到的数字一定是m个。
以上思路虽然不能满足要求，但我们可以进行改进。刚才我们在遍历每个数字的时候都是以同样的概率m/n决定是否要选择该数字，实际上，在当前遍历数字的前面的数字的结果我们是已经知道了，我们可以根据前面的随机结果动态地调整当前的随机策略，使得最终能够保证随机到的数字一定是m个。
具体的做法是，遍历第1个数字时有m/n的概率进行选择，如果选择了第1个数字，则第2个数字被选择的概率调整为(m-1)/(n-1)，如果没选择第1个数字，则第2个数字被选择的概率为m/(n-1)。即遍历到第i个数字的时候，如果此时已经选择了k个，则以(m-k)/(n-i+1)的概率决定是否要选择当前的第i个数字。
这样可以保证每次都能够保证在剩下的数字中能选择适当的数使得总体选择的数字是m个。比如，如果前面已经随机了m个，则后面随机的概率就变为0。如果前面一直都没随机到数字，则后面随机到的概率就会接近1。最终得到的结果始终精确地是m个数字。
12. 给出从n个数中随机选择1个的方法。注意，n非常大，并且一开始不知道其具体值。数字是一个一个给你的，当给完之后，你必须立刻给出随机的结果。
这里n的值非常大，而且要求立即给出答案，所以不能把所有的数字先保存起来，然后再慢慢考虑要随机哪个。
这题跟上面一题比较类似，因为我们不知道数字到底有多少个，所以必须在得到每一个数字的时候就有一个当前的结果，这样在数字给完的时候可以给出答案。
于是第1个数字是必须要拿的。问题是当第2个数字来的时候，究竟要保留手上的数字，还是拿当前的第2个数字呢？更一般地，当第i（i>1）个数字来的时候，究竟是保留手上的数字，还是选择当前的第i个数字呢？
答案是要保证每个数字被选取的概率是相等，当第i个数来的时候，如果我们已经保证了前i-1个数每个数被选取的概率都是相等的，那么只要第i个数字被选取的概率是1/i，我们就可以知道所有i个数被选取的概率都是1/i了。所以只需要以1/i的概率决定是否要选取当前的第i个数字即可。
于是可以保证对于任意的n，当给完n个数字时，选择每个数字的概率都是相等的，为1/n。
13. 给出从n个数中随机选择m个的方法。注意，n非常大，并且一开始不知道其具体值。数字是一个一个给你的，当给完之后，你必须立刻给出随机的结果。
这题是上一题的推广，于是可以仿照着进行。
首先前m个数字是必须拿的。问题是当第i（i>m）个数字来的时候，究竟是要丢弃这个数，还是保留这个数？如果要保留这个数的话，则必须得丢弃手中已有的m个数，那是怎么确定丢弃哪个呢？
下面是就具体的做法。第i个数到来的时候，以m/i的概率决定是否要选择这个数字。如果选择了这个数字，则随机地替换掉手上m个数字中的一个。
如果前i-1个数字的时候保证了每个数字被选取的概率相等，则这样做之后可以保证每个数字被选取的概率也相等，为m/i。
- 第i个数选择的概率是m/i，因为算法就是这样决定的。
- 考虑前i-1个数字中的任意一个，它在第i个数之前被选择的概率是m/(i-1)。在第i个数字的时候，这个数字要被选择的话又两种可能，一是第i个数没有被选中（概率是1-m/i），二是第i个数倍选中了（概率是m/i）但是替换掉的数字不是它（概率是1-1/m），于是这个数在第i个数时仍然被选择的概率是m/(i-1) * ((1-m/i) + (m/i * (1-1/m))) = m / (i-1) * ((i-1) / i) = m/i。
由数学归纳法原理知，对于任意的n，当给完n个数的时候，选择的结果可以保证这n个数中每个被选中的概率都是相等的，为m/n。