题目
题目描述
有 n 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 n 种邮票中的哪一种是等概率的，概率均为 1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第 k 次邮票需要支付 k 元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
输入格式
一行，一个数字 N（N le 10000）。
输出格式
输出要付出多少钱，保留二位小数。
输入输出样例
输入 #1
3输出 #1
21.25
思路
设(f_i)表示我们有(i)种邮票,获得剩下(n-i)种邮票所需要的期望购买次数.
显然,有(f_n=0).
[egin{equation}
egin{aligned}
f_i&=frac{i}{n}f_i+frac{n-i}nf_{i+1}+1\
f_i&=f_{i+1}+frac n{n-i}
end{aligned}
end{equation}
]
设(g_i)表示我们有(i)种邮票,获得剩下(n-i)种邮票所需要的期望花费.
同样的,(g_n=0).
[egin{equation}
egin{aligned}
g_i &= frac inBig(f_i+g_i+1Big)+frac {n-i}nBig(f_{i+1}+g_{i+1}+1Big)\
g_i &=frac 1{n-i}Big( icdot f_i+iBig)cdot Big(f_{i+1}+g_{i+1}+1 Big)
end{aligned}
end{equation}
]
答案即(g_0).
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10010;
double f[N] , g[N];
int main() {
double n;
cin >> n;
for(int i = n - 1 ; i >= 0 ; i--) {
f[i] = f[i + 1] + n / (n - i);
g[i] = (i * f[i] + i) / (n - i) + (f[i + 1] + g[i + 1] + 1);
}
printf("%.2lf" , g[0]);
return 0;
}