算法导论 5.4-1 - newdye的专栏 - 博客频道 - CSDN.NET

算法导论 5.4-1 - newdye的专栏 - 博客频道 - CSDN.NET

1 问题

一个房间里必须要有多少人，才能让某人和你生日相同的概率至少为1/2？必须要有多少人，才能让至少两个人为7月4日的概率大于1/2？

2 分析与解答

P{n个人中有人与你生日相同} = 1-P{n个人中没有人与你生日相同} = 1-(364/365)ⁿ >=1/2
所以(364/365)ⁿ <= 1/2
n >= -1/log₂ (364/365)
n >= -lg2/lg(364/365)
n >= 253
所以房间里必须有254人。
X_ij = I_ij{i与j生日都为7月4日}
E(X_ij ) = P{i与j生日都是7月4日} = 1/365²
E(X) = ∑_i=1^n-1∑_j=i+1ⁿ(1/365² ) = n(n-1)/365² >= 1/2
所以，n约为258

http://yuanhsh.iteye.com/blog/2195667

一个房间里有50个人，那么至少有两个人生日相同的概率是多少？（忽略闰年的事实，也就是一年365天）

计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里，我们可以计算所有人生日都互不相同的概率，也就是：365/365 * 364/365 * 363/365 * … * (365-49)/365，这样至少两个人生日相同的概率就是1 – 这个值。

1. public double caculateProbability(int n){  
2.     double x = 1;   
3.    
4.     for(int i=0; i<n; i++){  
5.         x *=  (365.0-i)/365.0;  
6.     }  
7.    
8.     double prob = Math.round((1-x) * 100);  
9.     return prob/100;  
10. }

calculateProbability(50) = 0.97
Read full article from 算法导论 5.4-1 - newdye的专栏 - 博客频道 - CSDN.NET