题目地址:https://vjudge.net/problem/SPOJ-FAVDICE

单词积累:   die骰子         button按钮

题意


给出骰子的面数,求要使每个面都朝上一次,抛的次数的数学期望

 

解题思路


dp[i]表示还剩i个面没有朝上过

i/n 表示抛一次剩下的i面中出现朝上的概率

n-i/n表示抛一次已经出现的n-i面中出现朝上的概率

状态转移方程:

(我个人认为最后的1表示从dp[i+1]转移到dp[i]要抛一次)

化简(移项)后:

 

ac代码


#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 1005
typedef long long ll;
using namespace std;
int main() 
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int t, n;
    cin >> t;
    while (t--) 
    {
        double dp[maxn] = {0};
        cin >> n;
        for (int i = n - 1; i >= 0; i--)
            dp[i] = dp[i + 1] + n * 1.0 / (n - i);
//或者用n/1+n/2+...+n/n
        printf("%.2lf\n", dp[0]);
    }
    return 0;
}