前言
期望的计算公式：
\[E(X) = \sum_i{i\times P(x=i)} \]期望的线性性：
\[E(X+Y) = E(X)+E(Y), E(kX) = kE(X) \]百事世界杯之旅
题目描述
假设有 \(n\) 个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？
解：
令\(f(i)\)表示现在收集了\(i\)个球星名字的情况下，还需要购买饮料的期望次数。
\[f(i)=1+\frac{i}{n}f(i)+\frac{n-i}{n}f(i+1) \]显然\(f(n)=0\)，于是倒推出\(f(0)\)就得到答案了。
然后进行一个自己推自己，就得到了：
\[f(i)=f(i+1)+\frac{n-i}{n} \]这题的输出格式有点谔谔
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int get(int x){
int ret = 0;
while(x){
ret++;
x /= 10;
} return ret;
}
int gcd(int x, int y){
if(!x) return y;
return gcd(y%x, x);
}
// f(x) = f(x+1)(n-x)/n + f(x)x/n + 1
signed main(){
int n; scanf("%lld", &n);
int ans1 = 0, ans2 = 1;
for(int i = 0; i < n; i++){
ans1 = ans2*n+ans1*(n-i);
ans2 *= n-i;
int qwq = gcd(ans1, ans2);
ans1 /= qwq, ans2 /= qwq;
}
if(ans1 % ans2 == 0){
printf("%lld\n", ans1/ans2);
return 0;
}
int ans3 = ans1/ans2;
ans1 = ans1%ans2;
for(int i = 1; i <= get(ans3); i++)
putchar(' ');
printf("%lld\n", ans1);
if(ans3) printf("%lld", ans3);
for(int i = 1; i <= get(ans2); i++)
putchar('-'); putchar('\n');
for(int i = 1; i <= get(ans3); i++)
putchar(' ');
printf("%lld\n", ans2);
return 0;
}
收集邮票
题目描述
有\(n\)种邮票，每次买一张，买到每种邮票的概率是相同的（\(\frac{1}{n}\)），但是每次购买邮票的费用不同，第\(k\)次购买需要支付\(k\)元钱。
问收集所有种类的邮票的期望花费。（输出保留二位小数）
解：
如果买了\(m\)次邮票，则花费为\(c=\frac{(m+1)m}{2}\)。
根据期望的线性性，\(E(c) = \frac{1}{2}[E(m^2)+E(m)]\)
根据上一题的结论，对于购买次数的期望有\(f(i)=f(i+1)+\frac{n}{n-i}\)
设\(g(i)\)表示现在收集了\(i\)种邮票的情况下，还需要购买邮票的期望花费。
\[g(i)=\frac{i}{n}{[g(i)+f(i)+1]} + \frac{n-i}{i}{[g(i+1)+f(i+1)+1]} \]再进行一个自己推自己，简化为：
\[g(i) = \frac{i}{n-i}\times f(i) + g(i+1) + f(i+1) + \frac{n}{n-i} \]点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
double f[N],g[N];
int n;
int main() {
scanf("%d", &n);
for(int i = n-1; i >= 0; --i){
f[i] = f[i+1]+(1.0*n)/(1.0*(n-i));
g[i] = (1.0*i)/(1.0*(n-i))*(f[i]+1);
g[i] += g[i+1]+f[i+1]+1;
}
printf("%.2lf\n", g[0]);
return 0;
}