LightOJ1104Birthday Paradox（思维+数学）

78 阅读 0 评论 52 点赞

我是靠谱客的博主自觉小天鹅，最近开发中收集的这篇文章主要介绍LightOJ1104Birthday Paradox（思维+数学），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description
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 ≤ 105) 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

题意：告诉你一年有多少天，你至少要邀请！！多少个人才能使至少两个人生日相同概率至少为0.5.

思路：开始直接想的是c（2，x）/n （x代表总人数，n代表天数）。但是这样算发现测试数据都不是0.5.直接算等于测试数据这样做所得到的数0.6多，测试几组数据对了但交了肯定wa，（侥幸心理！！）后来想了想发现会有重复的比如说有好多组两个人生日分别在同一天。然后我就想啊怎么排除，就这么列了好多组数据找规律，弄了快两三个多小时还是一点想法都没有！后来我就想是不是有什么简便方法，然后再一想反着做直接就出来了！！就是判断所有人生日都不在同一天，概率这样就直接是c（x，n）*A（x，x）/pow（n，x）； c（x，n）代表从n天里抽出x天作为每个人的生日，A（x，x）每个人生日天数随机组合。pow（n，x）所有人生日的概率。化简就是（n*（n-1）*……（n-x+1））/（n*n*n*…………n）（n-x个n）。直接算出两个数在除估计会超时，因为上下两个个数都相同，直接

for(i=0;;i++)
{
sum*=((a-i)*1.0/a);
if(sum<=0.5)
break;
}

因为i初始为0，所以判断出来的i直接就是邀请的多少人了。因为这里的概率是所有人都不在同一天的情况，所以第一个小于等于0.5的人数即为邀请人数。

代码：

#include<cstdio>
#include<cstring>
#include<math.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
int k=1;
while(t--)
{
long long
a;
scanf("%lld",&a);
long long i=0;
double sum=1;
for(i=0;;i++)
{
sum*=((a-i)*1.0/a);
if(sum<=0.5)
break;
}
printf("Case %d: %lldn",k++,i);
}
return 0;
}