【NOIP2013初赛】青蛙

题目

Description

有n片荷叶在池塘上。因为如此这般，有一只年轻的青蛙要在荷叶上跳。它是这样跳的：假如它在第i 号荷叶上，那么它等概率地跳到1 到i 号的荷叶中的一个，跳到1 号荷叶结束。求这只青蛙期望跳多少次结束。

Input

一行，一个整数n，表示青蛙从n 号荷叶开始跳。

Output

一行，一个实数，保留2 位小数。

Sample Input

Sample Input 1

5
Sample Input2

3

Sample Output

Sample Output1

3.08

Sample Output2

2.50

Data Constraint

40% : 1<= n <= 10:

70% : 1 <= n <= 10000:

100% : 1 <= n <= 20000.

题解

题目大意

有一只青蛙一开始在$n$，每次等概率的跳到1~当前位置，问跳到位置1的最小步数的期望

题目分析

首先明白过程可逆，于是就变成了从1到n

设 f i f_i fi​表示跳到$i$时的期望，那么

f i = ∑ j = 1 i f j + 1 i f_i=\dfrac{\sum_{j=1}^if_j+1}{i} fi​=i∑j=1i​fj​+1​

f i = ( ∑ j = 1 i f j ) + i i f_i=\dfrac{(\sum^i_{j=1}f_j)+i}{i} fi​=i(∑j=1i​fj​)+i​

f i × i = ∑ j = 1 i f j + i f_i\times i=\sum^i_{j=1}f_j+i fi​×i=∑j=1i​fj​+i

f i × ( i − 1 ) = ∑ j = 1 i − 1 f j + i f_i\times (i-1)=\sum^{i-1}_{j=1}f_j+i fi​×(i−1)=∑j=1i−1​fj​+i

f i = ∑ j = 1 i − 1 f j + i i − 1 f_i=\dfrac{\sum_{j=1}^{i-1}f_j+i}{i-1} fi​=i−1∑j=1i−1​fj​+i​​

然后可以预处理 f i f_i fi​的前缀和

Code

#include
#define db double
using namespace std;
int n;
db s,f[20005];
int main()
{scanf("%d",&n);if (n==1) printf("0.00\n");else{for (int i=2;i<=n;++i){f[i]=(s+i)/(i-1);s+=f[i];	} printf("%0.2f",f[n]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！