前一篇复习了先验概率和后验概率。
发现自己全概率，贝叶斯概率都忘了！！！所以这次复习一下?。
有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛这吃到苹果的概率是多少？给所有的抛硬币操作从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。
一共抛1次，p=1/2
一共抛3次，p=1/2*1/2*1/2
一个抛5次，p=1/2*1/2*1/2*1/2*1/2
所以总的概率值为：p=1/2+(1/2)^3+(1/2)^5+.........≈2/3
一条长度为l的线段，随机在其上选2个点，将线段分为3段，问这3个子段能组成一个三角形的概率是多少？设随机选取的两个数为x，y，并令y>x，则把长度为1的线段截得的三段长度为x， y-x ，1-y，根据三角形两边和大于第三边以及两边之差小于第三边的定理，可以列出方程组
假设我们选择的两个点的坐标是x和y（先假设x < y）：
那么由三角形两边和大于第三边的性质，有：
x+y-x>1-y
x+1-y>y-x
1-y+y-x>x
由上述不等式得到：x < 0.5, 0.5 < y < x+0.5
然后画个图就能得到联合概率为1/8，不要忘了这个结果是在假设x < y时得来的，所以再乘以2，得到1/4。
基本思想是每次随机取一个数，然后把它交换到最后的位置。然后对前（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); } 一个面试题：快速生成10亿个不重复的18位随机数的算法(从n个数中生成m个不重复的随机数)//假设从-n这n个数中生成m个不重复的数，且n小于int的表示范围
//总体思想是一开始每个数被选中的概率是m/n，于是随机一个数模n如果余数小于m则输出该数，同时m减
//否则继续扫描,以后的每个数被选中的概率都是m/(n-i)
个人不同意上述解法：编程珠玑上有很好的解法
Knuth著作《Seminumerical Algorithms》中提出的方法，顺序遍历n个数，通过随机测试条件的元素被选择。
以一个例子来解释所说的随机测试条件，比如m=2，n=5。第一个元素0被选择的概率是2/5；第二个元素1被选择的概率取决于第一个元素有没有被选择，如果0被选择，则1被选择的概率为1/4，否则为2/4，所有1被选择的概率为（2/5）*（1/4）+（3/5）*（2/4）=2/5；同理第三个元素2被选择的概率取决于前两个的选择情况，如果都没被选择，则2被选择的概率为2/3，如果前两个有一个被选择，则2被选择的概率为1/3，如果前两个都被选择，则2被选择的概率为0，故2被选择的概率为（3/5）*（3/5）*（2/3）+2*（2/5）*（3/5）*（1/3）=2/5。依次类推，每个元素被选择的概率都为2/5。
总的来说，从剩下的r个元素中选择s个元素，那么下一个元素被选中的概率为s/r，从整个数据集合角度来讲，每个元素被选择的概率都是相同的。
void getRandNumber(int m,int n)//在0 -- n-1 中挑选m个 随机数 { srand(time(NULL));//这个很关键 int i,j; for(i=0;i { if( rand()%(n-i) < m) { printf("%d ",i); m--; } } } 一副扑克牌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。
由随机函数rand7构造rand10已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10()随机1~10。
【试题分析】
1）要保证rand10()在整数1-10的均匀分布，可以构造一个1-10*n的均匀分布的随机整数区间（n为任何正整数）。假设x是这个1-10*n区间上的一个随机整数，那么x%10+1就是均匀分布在1-10区间上的整数。
2）接下来利用(rand7()-1)*7+rand7()构造出均匀分布在1-49的随机数：
首先rand7()-1得到一个离散整数集合{0，1，2，3，4，5，6}，其中每个整数的出现概率都是1/7。那么(rand7()-1)*7得到一个离散整数集合A={0，7，14，21，28，35，42}，其中每个整数的出现概率也都是1/7。而rand7()得到的集合B={1，2，3，4，5，6，7}中每个整数出现的概率也是1/7。显然集合A和B中任何两个元素组合可以与1-49之间的一个整数一一对应，也就是说1-49之间的任何一个数，可以唯一确定A和B中两个元素的一种组合方式，反过来也成立。由于A和B中元素可以看成是独立事件，根据独立事件的概率公式P(AB)=P(A)P(B)，得到每个组合的概率是1/7*1/7=1/49。因此(rand7()-1)*7+rand7()生成的整数均匀分布在1-49之间，每个数的概率都是1/49。
3） 由于出现的每个数的出现都是相对独立的，所以剔除41-49后剩下1-40也应该是均匀分布。
int rand10() { int x = 0; do { x = (rand7()-1)*7+rand7(); }while(x > 40); return x % 10 + 1;} 你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子然后从里面随机选出一个弹球，怎么给出红色弹球最大的选中机会?在你的计划里，得到红球的几率是多少?题目意思是两个罐子里面放了50红色和50蓝色弹球，然后我任选一个罐子，从中选中一个红球的最大概率，是设计一个两个罐子里怎么放这100球的计划。一个罐子：1个红球另一个罐子：49个红球，50个篮球几率=1/2+(49/99)*(1/2)=74.7%
n把钥匙开锁，第k次（1=<K<=N）打开的概率？分析：钥匙开过一次就知道是否能打开，因此是有序排列；只有一把可以打开，前k-1次都没有挑中正确的钥匙
求解1:第一次没打开P(X=0)=(N-1)/N
第二次没打开P(X=0)=(N-2)/(N-1)
...
第k次打开P(X=1)=1/(N-(k-1))
概率P=P1*P2*...Pk=1/N
求解2:有序排列，n把锁一共有n!种可能，在第k个位置固定正确的钥匙，其他位置随意，共有(n-1)!种可能
第k次打开P(X=k)=(n-1)!/n!=1/n
1.1 同类扩展问题1：n个人参与抽签，一共n张彩票，只有一个人会中奖，那么先后抽取的获奖概率是等同的。 1.2 扩展问题2:n个人参与抽签，一共n张彩票，抽到后放回盒子，只有1个人会中奖，那么先后抽的概率还一样吗？求解1:第一次没打开P(X=0)=(N-1)/N
第二次没打开P(X=0)=(N-1)/N
...
第k次打开P(X=1)=1/N
概率P=P1*P2*...Pk=[(N-1)/N]^(K-1)*1/N
越靠后抽中概率越低。
【配对问题】 【古典概率的乱序问题】 【分房问题】 在半径为1的圆中随机选取一点。方法1：在x轴[-1,1]，y轴[-1,1]的正方形随机选取一点，如果此点在圆内，则即为所求的点。如果不在圆内，则重新随机直到选到了为止。
方法2：从[0, 2*pi)随机选取一个角度，再在这个方向的半径上随机选取一个点。但半径上的点不能均匀选取，选取的概率要和离圆心的距离成正比，这样才能保证随机点在圆内是均匀分布的。
因为每次抛到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次。
答案： e 次， 其中e是自然对数的底。
在一圆周上任意取三个点构成锐角三角形的概率是多少解法1：
取三角形三个顶点为A，B，C。
用E表示ABC为锐角三角形的事件，现在的问题是如何描述全空间和E，显然可以假设圆半径是1，圆心O，于是ABC为锐角三角形等价于角AOB，角BOC，角COA均小于90度，而这又等价于弧AB，弧BC，弧AC的长度小于PI（派），显然可以任意固定一个点，
由该点处剪开圆周，把圆周拉直为一条长度为2*PI的线段，然后向该线段随机投掷两个点，把线段分成长度为x,y,z的3条线段，于是只要这3条线段长度都小于PI，则ABC就是锐角三角形，这样便可将全空间G和E表示为
G={(x,y,z):x+y+z=2*PI,x>=0,y>=0,z>=0}
A={(x,y,z):x+y+z=2*PI,0<x<PI,0<y<PI,0<z<PI}
所以 P(E)=L(E)/L(G)=1/4
解法2：
任意一点A确定，B也确定之后，要形成锐角三角形，点C必须在DE之间，否则将成为直角或钝角三角形ABC。设AB对应夹角为θ，θ在（0，π）上才有可能形成锐角三角形。θ的概率密度是1/π，此时组成锐角三角形需要C点在AB对应的DE段间的概率是θ/2π
所以概率是【θ/2π*1/π】关于θ在（0，π）积分=(θ^2)/(4π^2)在π取值减去在0取值=1/4
两个人坐在一张桌子的两边，轮流往桌子上放硬币，硬币不能重叠，谁放不下谁就输了。问先手有办法获胜吗？本题目表面上看很难着手，因为我们既不知道桌子大小形状，也不知道硬币的大小形状。实际上，退一步想，如果硬币足够大，一个硬币就盖住桌子，那么先手必赢。现在进一步，硬币小了，一个硬币不能盖住桌子了，只要桌子是对称的，不管桌子大小，也不管桌子是什么形状的，先手只要先占住了对称中心，以后每次放硬币的地方都是对手所放的地方的对称点，那么对手有地方放时先手一定有地方放硬币，先手就能保证胜券在握。因此我们用对称性思想很快就找到解决问题的思路。
真硬币m个，假币n个。假币只有正面。真币投掷正面概率为p。其中某硬币投掷k次都是正面，求它为真币概率。爱奇艺笔试
参考：
IT 概率面试题整理