Java 中的生日问题

生日悖论（或称生日问题）是概率论中的一个概念。虽然它并不构成逻辑矛盾意义上的悖论，但之所以被称为悖论，是因为数学上的现实与常识相悖：大多数人认为概率远低于 50%。它指的是在一个群体中，随机选择两个人，他们有相同生日的可能性。

在一个至少有 23 名随机选择的人组成的群体中，某对个体拥有相同生日的概率大于 50%。对于 57 人或更多的群体，概率超过 99%，而对于 366 人或更多的群体，概率为 100%（根据鸽巢原理，忽略闰年）。生日攻击是一种基于此问题的数学原理的著名密码学攻击。

要使至少两人有相同生日的概率达到 100%，房间里需要有多少人？

回答：367 人（因为有 366 个可能的生日，包括 2 月 29 日）。

上一个问题很简单。请尝试以下问题。

要使至少两人有相同生日的概率达到 50%，房间里需要有多少人？

回答：23 人

令人惊讶的是，这个数字相对较低。实际上，只需 70 位参与者即可达到此概率。

让我们来讨论更广泛的公式。

n 个人中至少有两人有相同生日的概率是多少？

设 P 代表 n 个人中至少两人有相同生日的概率（相同）。通过 P(不同)，即每个人都有不同生日的概率，可以轻松地估算 P(相同) 与 P(不同) 的关系。

P(相同) = 1 - P(不同)

P(不同) 可以写成 1 x (364/365) x (363/365) x (362/365) x.... x (1 - (n-1)/365)。

我们是如何得出上述表达式的？

为了确保每个生日都是唯一的，人们可以按以下顺序获得他们的生日，从第一个到最后一个：

第一个人的生日可以是任何一个（365 种可能性）。

第二个人不应该和第一个人有相同的生日。

第三个人不应该和前面两个人有相同的生日。

…………….

…………….

第 n 个人应该的生日与之前考虑过的 (n-1) 个人中的任何一个都不同。

上述表达式的特写

使用泰勒级数，上述陈述可以进行近似计算。

对于 x << 1，给出 ex 的一阶近似值

将 x 设置为 -a / 365，以将该近似值应用于为 p(不同) 生成的初始表达式。因此，

上述 p(不同) 的表达式可以写成 1 x (1 - 1/365)，1 x (1 - 2/365)，1 x (1 - 3/365)，1 x.... x (1 - (n-1)/365)。

将 1 - a/365 写成 e-a/365 会得到以下结果。

因此，p(相同) = 1 - p(不同)

p 提供了更简单的近似值（相同）

通过在两边取对数，我们可以得到反向公式。

我们可以使用上述近似公式来估计给定概率下需要多少人。例如，Java 中的 find() 函数返回使概率超过指定 p 的最小 n。

在实践中使用近似公式

下面的代码提供了特定概率的人数近似值。

文件名：Birthday.java

输出

31.0

复杂度分析

时间复杂度：O(log n)

辅助空间：O(1)

文件名：Birthday1.java

输出

Among the  no. of people out of which there is a 0.7 probability that two of them  have the same birthdays is 1

时间复杂度：O(log n)

辅助空间：O(1)

任务

计算一个群体至少需要多少独立成员，才能使至少两名成员拥有相同生日的概率大于 50%。此外：计算模拟，以确定当群体中有至少 3、4 和 5 名独立成员拥有相同生日的概率大于 50% 时的情况。为了简单起见，我们假设所有人都还活着。

改进建议

• 计算估计值的误差范围，以确保估计值精确到小数点后四位。
• 与其进行穷举搜索，不如使用根查找方法收敛到第 n 个解。
• 祝贺您（o）选择使用编程语言来证明解决方案，而不是使用构造和模拟。

文件名：Birthday1.java

输出

In a group of 23 people 2 independent people share a common birthday. ( 50.6)
In a group of 87 people 3 independent people share a common birthday. ( 50.4)
In a group of 187 people 4 independent people share a common birthday. ( 50.1)
In a group of 314 people 5 independent people share a common birthday. ( 50.2)

应用

1. 生日悖论经常与哈希一起提及，以强调碰撞处理的重要性，即使对于少量键也是如此。
2. 生日攻击