选自： http://blog.csdn.net/myhelperisme/article/details/39724515

用dp(n)表示有n个位置时的期望值，那么，对于一个刚进来的人来说，他有 n 个选择，当他选择第 i 个位置时，此时的期望值是 [dp(i-k-1) + dp(n-i-k)  + 1] / n, 推导一下，就得 (2 * sum(n-k-1) ) / i + 1, （sum(i)是指 有1～n个位置时的dp总和。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 1001000double f[N];int main(){    int n,k;    int T;    int tt=1;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&k);        for(int i=1;i<=k+1;i++)            f[i]=1;        double sum=f[1];        for(int i=k+2;i<=n;i++)        {            f[i]=1+sum*2.0/(double)i;            sum+=f[i-k];        }        printf("Case #%d: ",tt++);        printf("%lf\n",f[n]);    }    return 0;}