LOJ1248 Dice(III)

LOJ1248 Dice(III)

描述

给定一个 n 面的骰子,每个面出现的概率相同,现在要所有的面都至少出现一次,求投掷次数的期望。

题解

\(f[i]\) 表示投出 \(i\) 个面需要投掷的期望次数,投掷出现 \(i\) 个面后,当前的一次投掷,可能是投出的面原先投出过,这种情况有 \(\frac{i}{n}\) 的概率,也可能是当前投出的面未出现过,这种情况有 \(\frac{n - i}{n}\) 的概率。

对于已经投掷出 \(i\) 个面后的状态,此时的投掷,实际上是一个伯努利实验,事件即为是否投出新的一面。因此,根据几何分布的公式 \(E[X]=\frac 1 p\) ,易得投出新的一面的期望是 \(\frac n {n-i}\) ,因而可以得出 \[ f[i] = f[i - 1] + \frac n {n-i} \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T, t = 0;
scanf("%d", &T);
while (T--)
{
t++;
double n;
scanf("%lf", &n);
double ans = 0.0;
for (int i = 0; i < n; i++)
ans += n / (n - i);
printf("Case %d: %lf\n", t, ans);
}
}
----- 本文结束 感谢阅读 -----
0%