本文主要是介绍生日悖论问题——《算法导论学习笔记》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 生日悖论问题
1.1 原始问题
一个房间里的人数必须达到多少，才能使两个人生日相同的机会达到50%？不考虑闰年情况，也就是一年按照365天来计算。
解答：
假设房间里的人数是k，我们对其进行编号：1, 2, … , k。
为简单起见，用n表示一年的天数（也就是365天），那么一个人的生日在一年中的哪一天应该是机会均等的，我们用bi表示第i个人的生日，1<=bi<=n，因此，Pr{bi=r}=1/n，对于i=1,…,k；r=1,...,n成立。
这个问题可以通过求补法来求解：
也就是先计算任意两个人的生日都不相同的概率，然后用1去减，就可以算得相应概率。
K个人各有互不相同生日的事件为
Bk = ∩Ai(i=1,..,k)
其中Ai是指对所有的j<i，i与j生日不同的事件。
Bk=Ak ∩Bk-1
ð Pr{Bk}=Pr{Bk-1}Pr{Ak | Bk-1}
初始条件Pr{B1}=Pr{A1}=1.
如果b1,b2,…,bk-1互异，条件概率bk与b1,b2,..bk-1互异的概率为(n-k+1)/n
Pr{Bk}=1*((n-1)/n)* ((n-2)/n)*…((n-k+1)/n)
根据1+x<=e[x]
Pr{Bk}<=e[-1/n-2/n…-(k-1)/n]<=0.5
K(k-1)>=2nln2
当n=365时，解得k>=23。
因此，如果至少有23个人在一个房间里，那么至少有两个人生日相同的概率至少是0.5。
1.2 引申问题
一个房间里必须要有多少人，才能让某人和你生日相同的概率至少为1/2？必须要有多少人，才能让至少有两个人生日为7月4日的概率大于1/2。
第一个问题：
使用与前面类似的分析方法，可以得
1-((n-1)/n)[k-1] >= 0.5
从而解得k>=254人
第二个问题：
同样采用求补法：
分成两种情况考虑问题：
第一种情况：没有一个人生日为7月4日
第二种情况：有一个人生日为7月4日
可得表达式1-((n-1)/n)[k] – (k/n)((n-1)/n)[k-1]>=0.5
这篇关于生日悖论问题——《算法导论学习笔记》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
