LightOj_1104 Birthday Paradox

题目链接

题意:

  若一年有n天, 问至少需要多少个人才能满足其中两个人生日相同的概率大于等于0.5?

思路:

  经典问题:生日悖论

  换成其互斥事件:m个人, 每个人生日都不相同的概率 ≤ 0.5 时最小人数。

  这就是邮票收集问题的变形:每个邮票至少出现一次的概率 小于等于 0.5

  等价于:

      找到最小的n, 使得:H[n] = (n / n + (n - 1) / n + (n - 2) / n + ... + 1 / n) <= 0.5

代码:

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 100010
22 #define MAXM 380
23 double f[MAXN];
24 int n;
25 void init()
26 {
27     double x, y;
28     double m;
29     f[0] = 0;
30     f[1] = 1;
31     for(int i = 2; i < MAXN; i ++)
32     {
33         m = i;
34         y = i - 1.0;
35         x = 1.0;
36         for(int j = 1; j < MAXM; j ++)
37         {
38             x = x * y;
39             x /= m;
40             y --;
41             if(x <= 0.5)
42             {
43                 f[i] = j;
44                 break;
45             }
46         }
47     }
48 }
49 
50 int main()
51 {
52     int T;
53     int kcase = 0;
54     init();
55     scanf("%d", &T);
56     while(T --)
57     {
58         scanf("%d", &n);
59         printf("Case %d: %.0lf\n", ++kcase, f[n]);
60     }
61     return 0;
62 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:Java团长

美团面试,我竟然输给了冒泡排序。。。

前一阵子有个读者在微信里跟我聊了一件很有趣的事情,他去美团实习,面试让他哭笑不得,因为败在了冒泡排序上。

12520
来自专栏互扯程序

jdk静态代理,jdk动态代理,cglib动态代理

代理是什么呢?举个例子,一个公司是卖摄像头的,但公司不直接跟用户打交道,而是通过代理商跟用户打交道。如果:公司接口中有一个卖产品的方法,那么公司需要实现这个方法...

17950
来自专栏九彩拼盘的叨叨叨

Dart 概览

元数据注解是以 @ 字符开头,后面是一个编译时 常量(例如 deprecated)或者 调用一个常量构造函数。

11520
来自专栏数据库新发现

史上最详细MySQL全局锁和表锁

原文:http://www.enmotech.com/web/detail/1/728/1.html (复制链接,打开浏览器即可查看)

14240
来自专栏微信公众号:Java团长

如何给女朋友解释什么是分布式和集群?

某天,下班较早,我正在玩吃鸡,已经到决赛圈了,这时候,女朋友满脸求知欲的朝我走过来。

13030
来自专栏木二天空

003.Ceph扩展集群

需求:添加Ceph元数据服务器node1。然后添加Ceph Monitor和Ceph Manager node2,node3以提高可靠性和可用性。

7920
来自专栏中科院渣渣博肆僧一枚

张量拼接_调整维度_切片

tf.concat的作用主要是将向量按指定维连起来,其余维度不变;而1.0版本以后,函数的用法变成:

12720
来自专栏音视频技术

Netflix:通过自适应音频码率提升音频体验

文 / Guillaume du Pontavice、Phill Williams和KyleePeña(代表我们的流媒体算法,音频算法和创新技术团队)

19130
来自专栏音视频技术

Dav1d移动端解码高清视频达30FPS

LiveVideoStack正在招募编辑/记者/运营,与全球顶尖多媒及技术专家和LiveVideoStack年轻的伙伴一起,推动多媒体技术生态发展。了解岗位信息...

7220
来自专栏凯哥Java

spring boot框架学习学前掌握之重要注解(2)-通过java的配置方式进行配置spring

本文是《凯哥陪你学系列-框架学习之spring boot框架学习》中spring boot框架学习学前掌握之重要注解(2)-通过java的配置方式进行配置spr...

11120

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励