生日機率問題

問題描述：

算法導論 習題 5.4-1

一個房間必須有要有多少人，才能讓某人和你生日相同的機率至少為1/2？必須要有多少人，才能讓至少兩個人生日為7月4日的機率大于1/2？

分析和解決：

其實這個問題并不難，然而一開始我大意了，于是就出錯了，于是決定仔細分析，寫下來。首先假設不考慮閏年。

對于第一個問題：

假如從正面出發，就需要考慮有多少人和你同生日，很複雜，反過來考慮；用p(k)表示有k人與你生日相同，則p(0)表示沒有人和你相同，那麼問題就是1-p(0) >= 1/2，而p(0) = （364/365）^n ，因為你的生日是确定的

對于第二個問題：

分析類似于第一個，7月4日這一天定了，p(k)表示有k個人生日為7月4日

則問題轉化為

1 - p(0) - p(1) > 1/2，p(0) = (364/365)^n，p(1) = n *(1/365)* (364/365)^(n-1)