JDOJ 2195 青蛙为何在荷叶上跳来跳去

题目描述

Description

现有一只青蛙,初始时在N号荷叶上。
当它某一时刻在K号荷叶上时,下一刻将等概率地随机跳到1,2,....K号荷叶上之一,直至跳到1号荷叶为止。
当N=2时平均一共跳2次。

Input

一个整数N。(N<2000)

Output

输出平均一共跳多少次(保留3位小数)。

Sample Input

3

Sample Output

2.500

题目分析:

令f[i]是从1跳到i的期望次数

f[i]=(f[1]+1+f[2]+1+...+f[i-1]+1+f[i])/i

化简:f[i]=1+(f[1]+f[2]+f[3]+...+f[i-1])/i-1

初始:f[1]=1

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
double f[10000];
int n;
int main()
{
	scanf("%d",&n);
	f[1]=1;
	for(int i=2;i<=n;i++)
	{
		double tmp=0;
		for(int j=1;j<i;j++) tmp+=f[j];
		f[i]=tmp/(i-1)+1;
	}
	printf("%.3lf",f[n]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注