计算机专业——概率论面试题.doc

题目1假设你参加了一个游戏节目，现在要从三个密封的箱子中选择一个。其中两个箱子是空的，另一个箱子里面有大奖(你偶像的签名)。你并不知道奖在哪一个箱子里，但主持人知道。游戏节目的主持人先要你选择一个箱子，接着他把你没有选的空箱子打开，以证明它是空的。最后主持人给你换箱子的机会，你可以把你所选择的箱子换成另一个没有打开的箱子。此时你该不该换箱子？分析：要相信直觉。你当然应该换箱子！我们把三个箱子编号A,B,C，并假设你选的是A箱。显然奖品在A里的概率是1/3，在B或C里的概率是2/3。B和C可能有一个是空的，也可能两个都是空的。因此，当你选择了A箱后，主持人很可能会打开B箱或C箱，以显示里面是空的。在这种情况下，主持人的举动并不会影响奖品在A箱里面的机会。我们假设主持人打开了B箱，以告诉你它是空的。现在A箱有奖品的概率还是1/3，B箱里面有奖品的概率是0，因此C箱里面有奖品的概率是2/3。在这种情况下，你应该换到C箱，因为它使你赢的机会提高了1倍！题目2有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛者吃到苹果的概率是多少？分析：我首先想到的就是把 第一次抛到正面的概率 + 第二次抛到的概率 + .+无穷多次，当然后面的概率几乎为0了。 结果就是 P = 1/2 + 1/8 + 1/32+ 最后的结果就是 P = 2/3 . 这个计算也不难，其实就是等比数列，比为1/4. 简单的无穷级数 (1/2) / (1-1/4) = 2/3. 1/(1-x)2=1+2x+3x2+4x3+5x4+ (-1xx，则把长度为1的线段截得的三段长度为x， y-x ，1-y，根据三角形两边和大于第三边以及两边之差小于第三边的定理，可以列出方程组y1-y; xy-x;即x1/2; yx+1/2;画图可以算得概率为1/8；（线性规划的思想）题目4世界上每十万人中就有一人是艾滋病患者。艾滋病的检测目前已经很准确，但并非万无一失。它的检测准确率是99%，假设你刚去做完艾滋病检验，得到的了检测报告，结果.是阳性！你会绝望或昏倒吗？或者说，你会担心到什么程度？分析：你大可不必那么担心，因为你几乎可以确定没有得艾滋病。什么？检测是阳性还几乎可以确定没有艾滋病？！是的，为了说明这一点，假设有100万人和你做了同样的检验。在这100万人中，得病的会有10个，没有得病的有999990个。当这些人接受检验时，910个人患有艾滋病的人会呈现阳性反应，另外999990个没有得病的人则会有1%出现错误的阳性反应，换算成人数大概是1万人。也就是说，大约10000个阳性诊断中，实际只有10个左右是真正患者。因此，绝大多数所呈阳性的反应都是误诊。当你得到阳性的检测结果时，真正得艾滋病的机会大概只有千分之一。（当然，如果你在检测之前做了很可能感染艾滋病的事，那就另当别论了）题目5有一对夫妇，先后生了两个孩子，其中一个孩子是女孩，问另一个孩子是男孩的概率是多大？答案是2/3.两个孩子的性别有以下四种可能：（男男）（男女）（女男）（女女），其中一个是女孩，就排除了（男男），还剩三种情况。其中另一个是男孩的占了两种，2/3.之所以答案不是1/2是因为女孩到底是第一个生的还是第二个生的是不确定的。题目6一个国家人们只想要男孩，每个家庭都会一直要孩子，只到他们得到一个男孩。如果生的是女孩，他们就会再生一个。如果生了男孩，就不再生了。那么，这个国家里男女比例如何？分析：一开始想当然的以为男多女少，毕竟都想要男孩。但是注意这句话“如果生了男孩，就不再生了”，一个家庭可能有多个女孩，只有一个男孩。再仔细分析，我们来计算期望值，只用计算一个家庭就行了。设一个家庭男孩个数的期望值为S1，女孩为S2.根据题目条件，男孩的个数期望值S1=1这个是不用计算了。主要计算S2一个家庭的孩子数量可以为:1,2,3,4,5. 对应的的男女分布为: “男”,”女男”,”女女男”,”女女女男”,”女女女女男” 对应的概率分布为 1/2, 1/4, 1/8, 1/16, 1/32 。其中女孩的个数分别为 0,1,2,3,4因此 S2=0*1/2 + 1*1/4 + 2*1/8 + 3*1/16 + 4*1/32 + 可以按照题目2用级数求，也可以用错位相减法：S2=1/4+2/8+3/16+4/32+ 两边乘以2,得: 2*S2=1/2+2/4+3/8+4/16+5/32+.两个式子相减得S2=1/2+1/4+1/8+1/16+1/32+=1. 所以期望值都为1，男女比例是一样的。一个面试题：快速生成10亿个不重复的18位随机数的算法(从n个数中生成m个不重复的随机数)/假设从-n这n个数中生成m个不重复的数，且n小于int的表示范围/总体思想是一开始每个数被选中的概率是m/n，于是随机一个数模n如果余数小于m则输出该数，同时m减/否则继续扫描,以后的每个数被选中的概率都是m/(n-i)cppview plaincopy1. voidrandom_generate(intn,intm)2. 3. inti=1,t，remain;4. while(n-im)5. 6. t=rand()%(n-i);7. if(tm)8. printf(%d,i);9. m-;10. 11. i+;12. 13. while(+i=n)printf(%d,i);14. (wiki关于随机数的介绍/wiki/Mersenne_twister)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、编程之美：金刚坐飞机问题大家都在排队上飞机，然后金刚来了，他也有票，但是插队第一个上了飞机，随便找了个座位坐下了，其余人的策略是：如果自己票上写的座位没被占就按照座位坐，被占了就变身成金刚，随便找地儿坐。问第i个人坐在自己座位的概率是多少？1.n一共n个座位，为了方便计算起见，我们做一个变换变换1：金刚的票上的座位是最后一个，也就是第n个，其余人的票和座位再按照原先的顺序排列成1.n-1。这样并不影响最终的概率，因为如果1）金刚坐在自己的位置上，那么大家同样都是肯定坐在自己的位置上。2）如果金刚坐在第i个位置(非他票上的座位)上，那么前i-1个人会坐在自己的位置上，与变换前相同，而第i个人肯定不会坐在自己的位置上，他会在变换前的金刚的座位再加上i+1.n的集合中随机挑一个座位，这也有变换前相同，他挑的座位对于后面人的影响也是与变换前相同的。设F(i,n)为新的n个座位的排列中第i个人坐到自己位置上的概率，那么旧排列中第i个人坐到自己位置的概率就是F(i,n) ij;j为金刚票上的座位那么我们现在来计算F(i,n)，后面的讨论全部基于变换后的排列。对于乘客i，金刚的选择会造成3种情况，假设金刚选择的是j，分别为ij，概率分别为(n-i)/n，1/n，(i-1)/n。如果ij，那么前j-