转载：关于概率的面试题

原文出处：https://blog.csdn.net/rudyalwayhere/article/details/7349957

当前面试中各大名企经常出现各种各样的概率类面试题。究其原因，我觉得是概率型面试题可以综合考查面试者的思维能力、应变能力、数学能力。在这里对各种类型的概率型题目进行了收集和总结，希望在自我总结的同时对大家有所帮助。

1、给你一个数组，设计一个既高效又公平的方法随机打乱这个数组（此题和洗牌算法的思想一致）

方法比较简单，基本思想是每次随机取一个数，然后把它交换到最后的位置。然后对前（n-1）个数使用递归的算法。

递归实现：

void suffle_dfs(int ar[], int n) {
    if(n<=1)return;
    swap(ar[n-1], ar[rand()%n]);
    shuffle_dfs(ar,n-1);
}

非递归实现：

void suffle(int ar[], int n) {
    while(n>1){
         swap(ar[n-1], ar[rand()%n]);
        n--;
    }
}

注：此处假设rand()的返回结果远远大于n。

2、有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛这吃到苹果的概率是多少？

这种题目一看似乎答案就是1/2，但其实认真细想并没有那么简单。

给所有的抛硬币操作从1开始编号，显然先手者只可能在奇数（1,3,5,7…）次抛硬币得到苹果，而后手只可能在偶数次（2,4,6,8…）抛硬币得到苹果。设先手者得到苹果的概率为p，第1次抛硬币得到苹果的概率为1/2，在第3次（3,5,7…）以后得到苹果的概率为p/4（这是因为这种只有在第1次和第2次抛硬币都没有抛到正面（概率为1/4=1/2*1/2）的时候才有可能发生，而且此时先手者在此面临和开始相同的局面）。所以可以列出等式p=1/2+p/4，p=2/3。

现在答案已经很明确了，所以大家平时要注意不要这样被人骗了，当然也不能去骗别人，哈哈~

3、一条长度为l的线段，随机在其上选2个点，将线段分为3段，问这3个子段能组成一个三角形的概率是多少？

另一篇文章：http://blog.sina.com.cn/s/blog_6aea6f2e0100yfk5.html

设随机选取的两个数为x，y，并令y>x，则把长度为1的线段截得的三段长度为x， y-x ，1-y，根据三角形两边和大于第三边以及两边之差小于第三边的定理，可以列出方程组

y>1-y; x<1-x; x+(1-y)>y-x;
即x<1/2; y>1/2; y>x+1/2;
画图可以算得概率为1/8；（线性规划的思想）

4、一个面试题：快速生成10亿个不重复的18位随机数的算法(从n个数中生成m个不重复的随机数)

//假设从-n这n个数中生成m个不重复的数，且n小于int的表示范围
//总体思想是一开始每个数被选中的概率是m/n，于是随机一个数模n如果余数小于m则输出该数，同时m减1
//否则继续扫描,以后的每个数被选中的概率都是m/(n-i)

void random_generate(int n, int m) {
    int i=1,t，remain;
    while(n-i>m) {
        t = rand()%(n-i);
         if(t<m) {
            printf("%d ",i);
            m--;
           }
           i++;
    }
    while(++i<=n)printf("%d ",i);
}

(wiki关于随机数的介绍http://en.wikipedia.org/wiki/Mersenne_twister))

knuth算法

knuth(int n,int m) {
    for(int i=0;i<n;i++) {
        if(rand()%(n-i)<m) {
            cout<<i<<endl;
            m--;
        }
    }
}

5、你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子然后从里面随机选出一个弹球，怎么给出红色弹球最大的选中机会?在你的计划里，得到红球的几率是多少?

题目意思是两个罐子里面放了50红色和50蓝色弹球，然后我任选一个罐子，从中选中一个红球的最大概率，是设计一个两个罐子里怎么放这100球的计划。一个罐子：1个红球另一个罐子：49个红球，50个篮球几率=1/2+(49/99)*(1/2)=74.7%

6、一副扑克牌54张，现分成3等份每份18张，问大小王出现在同一份中的概率是多少？（大意如此）

解答1：

54张牌分成3等份，共有M=(C54取18)(C36取18)(C18取18)种分法。

其中大小王在同一份的分法有N=(C3取1)(C52取16)(C36取18)*(C18取18)种。

因此所求概率为P=N /M=17/53。

解答2：

不妨记三份为A、B、C份。大小王之一肯定在某一份中，不妨假定在A份中，概率为1/3。然后A份只有17张牌中可能含有另一张王，而B份、C份则各有18张牌可能含有另一张王，因此A份中含有另一张王的概率是17/(17+18+18)=17/53。

也因此可知，A份中同时含有大小王的概率为1/3 * 17/53。

题目问的是出现在同一份中的概率，因此所求概率为3(1/3 17/53)=17/53。

7、A和B2人投硬币,正面A得1元,反面B得一元.起始时A有1元,B有100元.

游戏持续进行,直到其中1人破产才终止.

问:

1.如果硬币正反概率相同,游戏的期待长度(expected duration)是几次投掷?

2.如果硬币是不公正的,正面概率为P,反面概率为Q.(P+Q=1), 那么游戏的期待长度(expectedduration)是几次投掷?

答案还没整理

8、完美2011.10.16笔试题:2D平面上有一个三角形ABC，如何从这个三角形内部随机取一个点，且使得在三角形内部任何点被选取的概率相同。

在二维坐标系中可以用坐标（x，y）来表示图形中的一个点。如下图只要能够在各个带双向箭头的图之间的点能够建立一一映射即可。如把一个长方形（如正方形）的点映射到另一个长方形的点只要把坐标做相应的放大缩小即可。如把长方形的点映射到一个直角三角形，只要将长方形右上部份的三角形的点映射到对称的左下角的三角形的点即可。而直角三角形映射到一边平行于x轴的三角形的映射只要做x轴相应的偏移即可。而任意三角形可以分割成两个其中有一边平行于x轴的三角形。说的不是很清楚，具体的映射方法可以认真思考并写出公式。

9、平均要取多少个(0,1)中的随机数才能让和超过1。答案： e 次， 其中e是自然对数的底

10、编程之美：金刚坐飞机问题

另一篇文章：https://www.cnblogs.com/python27/archive/2012/04/08/2438009.html

问题描述

现在有一架飞机要起飞，乘客们正准备按机票号码（1,2,3…,N）一次排队登机。突然来了一只大猩猩（金刚）。他也有机票，但是他插队第一个登上了飞机，然后随意的选择了一个座位坐下了。根据社会的和谐程度，其他的乘客有两种反应：
1.乘客们都义愤填膺，“既然金刚同志都不守规矩，为什么我要遵守？”他们也随意的找位置坐下，并且坚决不让座位给其他乘客。
2.乘客们虽然感到愤怒，但是还是以“和谐”为重，如果自己的位置没有被占领，就赶紧坐下，如果自己的位置已经被别人（或者金刚同志）占了，就随机的选择另一个位置坐下，就开始闭目养神，不在挪动。
问题：在这两种情况下，第i个乘客（出去金刚同志外）做到自己原机票位置的概率分别是多少？

问题解答

第一问：该问题相当于排序问题，总的排序总数是n个人的全排列为N!，如果第i个人做到第i个位置上，那么其余n-1个人的全排列为(N-1)!,综上所求概率为(N-1)!/N!=1/N。

第二问：《编程之美》讲得比较复杂，没怎么看懂，在网上找了几个博文对该问题的解答，综合一下，这样理解比较容易：
假设：F(i,n)表示在有n个座位的前提下，第i个人恰好做到第i个座位的概率；
P(K=j)表示金刚刚好坐在位置j上的概率；
P(i|K=j)表示在金刚做到位置ｊ的前提下，第ｉ个人恰好做到第ｉ个位置上的概率。
由以上的假设根据全概率公式有：

　　由于金刚坐到每一个位置上的概率是相等的，容易知道Ｐ（Ｋ＝ｊ）＝１／ｎ；
　　接下来我们只需要考虑后一项条件概率的值即可。
　　（１）如果ｊ＝１，则表明金刚坐到第一个位置，则ｉ坐到ｉ位置的概率为１；如果ｊ＞ｉ，前面的人必然按位置坐，所以概率也为１.所以我们只需要考虑１＜ｊ＜ｉ的情况，见下。
　　（２）在１＜ｊ＜ｉ的情况下，即金刚坐在第ｊ（１＜ｊ＜ｉ）个位置上，则ｊ个乘客除非坐在金刚的位置上，否则同样要同样要抢占其他人的座位。这和金刚的行为是相似的（因为金刚除非坐在自己的位置上，否则抢占别人的座位），所以我们可以讲第ｊ个乘客当做新的金刚，此时还剩余ｎ－ｊ个座位，同时把剩余乘客的编号也都减去ｊ，则先前的第ｉ个乘客座位号变为ｉ－ｊ，此问题和原问题相似，只是规模更小，所以该种情况下，条件概率为Ｆ（ｉ－ｊ，ｎ－ｊ）.
　　所以有如下等式：

　　然后可以从上面的公式推出递推式：F(i,n)=F(i-1,n-1).（笔者验证了一下，公式是对的，但是不会推导，希望有会的网友指点）。
　　有上面的递推公式，我们可以到：nF(i,n)=(n-i+1)+(i-2)F(i,n)，则问题的最终答案为：