#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t,n;
double dp[100010];
int main()
{
scanf("%d",&t);
int cas=1;
while(t--)
{
scanf("%d",&n);
dp[n]=0;
for(int i=n-1;i>=0;i--)
dp[i]=dp[i+1]+(double)(n)/(n-i);
printf("Case %d: %.8lf\n",cas++,dp[0]);
}
}
这一题期初我怎么也没理解这递推方程。后来想通一个说法。
dp[i]表示您还差i面没扔出来时你扔的次数。
dp[i]=i/n*dp[i]+(n-i)/n*dp[i+1]+1;
dp[i]=dp[i+1]+(double)(n)/(n-i);
现在让我来分析一下：
为什么i/n*dp[i]+(n-i)/n*dp[i+1]呢，我觉得是(n-i)/n*(dp[i]+1)+(i+1)/n*(dp[i+1]+1)
其实这个要反着考虑一下。就是n个你选i个里面的那么造成了dp[i],不然还是dp[i+1].。这个从后往前。
原文：http://www.cnblogs.com/newadi/p/4729985.html