spoj1026 favorite dice

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,t;
 4 const int  N  = 1200;
 5 double dp[N];
 6 /*
 7 甩一个n面的骰子，问每一面都被甩到的需要甩的次数期望是多少。
 8 dp[i]：已经甩到i个面了，要达到n个面还需要次数的期望
 9 显然dp[n] = 0
10 那么逆序分析：dp[i] ：再甩一次,有(n-i)/n的概率甩到其他的
11 有i/n的概率甩到已经被甩过的。
12 那么 dp[i]=(n-i)/n*dp[i+1]+i/n*dp[i]+1(+1是因为再甩了一次）
13 化简可得到  dp[i]=dp[i+1]+n/(n-i)
14 */
15 int  main()
16 {
17     scanf("%d",&t);
18     while(t--){
19         scanf("%d",&n);
20         dp[n] =0;
21         for(int i =n-1;i>=0;i--){
22             dp[i] = dp[i+1]+(n/(n-(double)i));
23         }
24         printf("%.2f
",dp[0]);
25     }    
26     return 0;
27 }