LightOJ_1248 Dice (III)
题意：
给一个质地均匀的n的骰子， 求投掷出所有点数至少一次的期望次数。
思路：
这就是一个经典的邮票收集问题（Coupon Collector Problem）。
投掷出第一个未出现的点数的概率为n/n = 1， 因为第一次投掷必然是未出现的。
第二个未出现的点数第一次出现的概率为 (n - 1) / n，因为有一个已经投掷出现过。
第i个未出现的点数第一次出现的概率为 (n - i) / i， 这满足几何分布。
其期望E = 1/p
所以期望为n *（1 + 1 / 2 + 1 / 3 + ... 1 / n）。
代码：
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 yy 0.5772156649
23 double f[MAXN];
24 void init()
25 {
26 f[0] = 0.0;
27 for(int i = 1; i < MAXN; i ++)
28 f[i] = f[i-1] + 1.0 / (i * 1.0);
29 }
30 double GetExpectation(int n)
31 {
32 return n * 1.0 * f[n];
33 }
34
35 int main()
36 {
37 int T;
38 int kcase = 0;
39 init();
40 scanf("%d", &T);
41 while(T --)
42 {
43 int n;
44 scanf("%d", &n);
45 printf("Case %d: %.7lf\n", ++ kcase, GetExpectation(n));
46 }
47 return 0;
48 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-08-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读