也許更好的閱讀體驗(yàn)
$Description$Description
一個(gè) $n$n面的骰子，求期望擲幾次能使得每一面都被擲到
輸入有 $T$T組數(shù)據(jù)，每次輸入一個(gè) $n$n
輸出保留兩位小數(shù)

$Solution$Solution
設(shè) $f\left[i\right]$f[i]表示已經(jīng)擲到過 $i$i面，還 期望擲多少次骰子使每一面都被擲到
現(xiàn)在擲一次骰子，有兩種情況

1. 有 $\frac{i}{n}$ni?的概率擲到已經(jīng)擲到過的面，此時(shí)仍然還要擲 $f\left[i\right]$f[i]次骰子
2. 有 $\frac{n?i}{n}$nn?i?的概率擲到?jīng)]擲到過的面，此后就擲到過 $i+1$i+1個(gè)面了，還需擲 $f[i+1]$f[i+1]次骰子

需要注意的是，無論是擲到以上哪種情況，都需要擲一次骰子
所以有
$f\left[i\right]=\frac{i}{n}f\left[i\right]+\frac{n?i}{n}f[i+1]+1$f[i]=ni?f[i]+nn?i?f[i+1]+1
將其化簡
$f\left[i\right]=f[i+1]+\frac{n}{n?i}$f[i]=f[i+1]+n?in?

初值 $f\left[n\right]=0$f[n]=0，答案為 $f\left[0\right]$f[0]
應(yīng)逆向循環(huán)

$Code$Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年07月21日 星期日 14時(shí)51分18秒 *******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 1005;
//{{{cin
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';
		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	 res=~res+1;
		return *this;
	}
}cin;
//}}}
int T,n;
double f[maxn];//f[i] -> 有了i個(gè)面，變成擁有n個(gè)面的期望
int main()
{
	freopen("p1026.in","r",stdin);
	freopen("p1026.out","w",stdout);
	cin>>T;
	while (T--){
		cin>>n;
		f[n]=0;
		for (int i=n-1;i>=0;--i)	f[i]=f[i+1]+1.0*n/(n-i);
		printf("%.2lf\n",f[0]);
	}
	return 0;
}

本篇博客亦被收進(jìn)期望總結(jié)

如有哪里講得不是很明白或是有錯(cuò)誤，歡迎指正
如您喜歡的話不妨點(diǎn)個(gè)贊收藏一下吧