关键词:数学期望 调和级数
相关题目:$Luogu39825$

同学私人题库里的一道题,数学期望入门题

题目描述

现在有一只青蛙(Called ZBY!) 在第$n$个荷叶上,每一次等概率地跳到第1格~当前所在荷叶上
求ZBY跳到第1个格子上的步数期望,保留8位小数

Solution

我们用 f[i] 表示第i格跳到第1格的数学期望,则易得

变一下形

然后可得

上下两个式子相减,我们会惊喜的发现

这样我们就得到了一个递推式

似乎后面这部分是个调和级数?
调和级数 $\Sigma_{i=1}^{n}\frac{1}{i}$ 虽然是发散的,但是当n较大时,可以用 $ln(n)+欧拉常数$ 来求其近似前缀和

欧拉常数≈$0.5772156649015328606$
$f[2]=2$

Code

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <cmath>
using namespace std;
double ans;
long long n;
int main(int argc, char const *argv[]){
scanf("%lld",&n);
if(n<=1e6) for(int i=2;i<n;i++) ans+=1/(double)i;
else ans=log(n-1)-1+0.5772156649015328606;
printf("%.8lf\n",2+ans);
return 0;
}