Java中的生日问题

生日悖论，或称困境，是概率论中的一个概念。虽然这并不构成悖论，因为它导致了逻辑上的矛盾，但它被称为是悖论，因为数学现实与常识相悖：大多数人认为机会远远低于50%。指的是在一个群体中随机选择的两个人有一个生日的可能性。

在一个群体中的某一对个体，并且至少有23个随机选择的人，有大于50%的几率会有相同的出生日。对于57人或更多的群体，这个机会超过99%，对于366人或更多的群体，这个机会是100%（根据鸽子洞原则，忽略闰年）。生日攻击是一个著名的密码学攻击，它是基于这样一个问题背后的数学原理。

在一个房间里，至少有两个人的生日相同的可能性要达到100%，必须有多少人在场？

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

前面的查询并不复杂。自己试试下面这个查询。

一个房间里必须有多少人在场，才能使至少两个人同一天生日的可能性达到50%？

回复：。23

令人惊讶的是，这个数字相对较低。实际上，只要有70个参与者就可以达到这个概率。

我们来谈一谈更广泛的公式。

n人中有两个人的生日相同的可能性是多少

让P代表一个有n人的房间里面的两个人分享相同生日的可能性（相同）。P(不同)代表每个人的生日不同的可能性，这样就可以简单地用P(不同)来估计P(相同)。

P(相同)等于P-1(不同)

可以把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提供了一个更基本的近似值(相同)

我们可以通过把Log放在两边得到反向公式。

我们可以用上面的粗略公式估计有多少人有给定的机会。例如，Java中的find()函数返回概率超过指定p的最小n。

在实践中使用粗略公式

下面的代码中提供了一个特定概率的人口近似值。

文件名：Birthday.java

// Java program for the approximate number
// of people in the Birthday Paradox problem
class Birthday {

    // Returning the approximate number of people
    // for the given probability
    static double find(double p1) {

        return Math.ceil(Math.sqrt(2 *
            365 * Math.log(1 / (1 - p1))));
    }

    // Main code
    public static void main(String args[])
    {

        System.out.println(find(0.70));
    }
}

输出。

31.0

复杂度分析 。

时间复杂度： O(log n)

辅助空间： O(1)

文件名：Birthday1.java

class Birthday1{
  public static void main(String args[]){

    // Assuming the year to be the non-leap year
    float n = 365;

    float dn = 365;
    double pr1=0.7;
    int n1 = 0;


    float p1 = 1;
    while (p1 > pr1){
      p1 *= (n/dn);
      n--;
      n1++;
    }

    System.out.printf("\nAmong the  no. of people out of which there is ");
    System.out.printf( "%.1f probability that two of them "
                      + " have same birthdays is %d ", p1, n1);
  }
}

输出。

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)

任务

计算一个群体必须包含的最小独立成员数，以使其中至少有两个成员具有相同的出生日期的可能性大于非可能性。此外。计算模拟，以确定何时有更大的偶数机会，即至少有3、4、5个独立的组员会有相同的生日。为简单起见，我们假设每个人都还活着。

改进建议

计算估计值的误差范围，以确保该估计值正确到小数点后四位。
与其进行彻底的搜索，不如用寻根的方法收敛于th解。
祝贺(o)你选择使用编程语言来证明解决方案，而不是使用构造和模拟。

文件名：Birthday1.java

import static java.util.Arrays.stream;
import java.util.Random;

public class Birthday1 {

static double eB(int nS, int gS, int nR) {
Random r = new Random(1);

int eq1 = 0;

for (int i1 = 0; i1 < nR; i1++) {
int[] g = new int[365];
for (int j1 = 0; j1 < gS; j1++)
g[r.nextInt(g.length)]++;
eq1 += stream(g).anyMatch(c1 -> c1 >= nS) ? 1 : 0;
}

return (eq1 * 100.0) / nR;
}

public static void main(String args[]) {

int gE = 2;

for (int s = 2; s < 6; s++) {
int gS = gE + 1;
while (eB(s, gS, 100) < 50.0)
gS++;

int inf1 = (int) (gS - (gS - gE) / 4.0);
for (int gs1 = inf1; gs1 < gS + 999; gs1++) {
double eq1 = eB(s, gS, 250);
if (eq1 > 50.0) {
gS = gs1;
break;
}
}


for (int gs1 = gS - 1; gs1 < gS + 999; gs1++) {
double eq1 = eB(s, gs1, 50_000);
if (eq1 > 50.0) {
gE = gs1;
System.out.printf("In a group of %s people"
+ " %d independent people share a common birthday. (%5.1f)%n",
gs1,s, eq1);
break;
}
}
}
}
}

输出。

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)