Birthday Paradox LightOJ - 1104 （概率期望）

46 阅读 0 评论 31 点赞

我是靠谱客的博主危机早晨，最近开发中收集的这篇文章主要介绍Birthday Paradox LightOJ - 1104 （概率期望），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Sometimes some mathematical results are hard to believe. One of the common problems is the birthday paradox. Suppose you are in a party where there are 23 people including you. What is the probability that at least two people in the party have same birthday? Surprisingly the result is more than 0.5. Now here you have to do the opposite. You have given the number of days in a year. Remember that you can be in a different planet, for example, in Mars, a year is 669 days long. You have to find the minimum number of people you have to invite in a party such that the probability of at least two people in the party have same birthday is at least 0.5.

Input
Input starts with an integer T (≤ 20000), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 10^5) in a single line, denoting the number of days in a year in the planet.

Output
For each case, print the case number and the desired result.

Sample Input
2
365
669
Sample Output
Case 1: 22
Case 2: 30

大致题意：告诉你现在一年的天数n，问除了主人，至少还需邀请多少人来家里聚会，才能使得此时所有人中至少有两个人的生日是同一天的概率大于0.5。

思路：所有人中至少有两个人的生日是同一天的概率就等于1减去所有人的生日都不是同一天的概率，那么问题就变的简单了，假设此时一年的天数为n，至少要邀请x人，那么所有人的生日都不是同一天的概率即为（n-1） / n * （n-2）/n * ……*（n-x）/n，暴力去求下最小的x使得该答案的值小于0.5即可

代码如下

#include<bits/stdc++.h>
const double eps=1e-7;//注意精度，这里至少1e-7取1e-6会wa
using namespace std;
int main()
{
int T;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
int n;
scanf("%d",&n);
double s=1;
int ans=0;
while(1)
{
if(s-0.5<eps) break;
ans++;
s*=1.0*(n-ans)/n;
}
printf("Case %d: %dn",cas,ans);
}
return 0;
}