Dice (III) LightOJ - 1248（機率期望+幾何分布（n面骰子，問看到所有的面一次的至少所需擲骰子次數的期望）

LOJ—1248

題意：

一個均勻的骰子有n個面 投色子, 要求最後要把骰子的每一面都看到了, 求扔骰子次數的期望。

分析：

1.幾何分布

上面我們定義隻要E(x)=1/P,P表示第k次成功的機率

扔出第一面成功的機率為P=1，E=1,因為第一面肯定沒見過。

扔出第二面成功的機率為P=(n-1)/n,E=n/(n-1)（因為實驗獨立，是以有n-1個可以當作第二面）

扔出第i面成功的機率為P=(n-i-1)/n ,E=n/(n-i+1)

扔出第n面成功的機率為P=1/n ,E=n

累加E即可

2.期望DP

設dp[i]為已經扔了i個不同面的期望值 ，dp[n] = 0 求dp[0]

那我們每次可能扔中已經扔過的面或者沒有扔到過的面2中情況：

1.該面在前面已經出現過機率：（i-1）/n，E= F(i - 1) * ((i - 1) / n)

2.該面已經未出現過機率：(n-（i+1）)/n，E= F(i) * ((n - (i - 1)) / n)

則狀态方程：F(i) = F(i - 1) * ((i - 1) / n) + 1 + F(i) * ((n - (i - 1)) / n)。

解得F(i) = F(i - 1) + (n / (i - 1))。

幾何分布：

#include<stdio.h>
#include<algorithm>
#include<iostream> 
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#define nmax 510
using namespace std;
int cas=0,T,n;
int main(){
 
        scanf("%d",&T); 
        while(T--)
		{
        	cas++;
        	cin>>n;
        	double sum=0;
        	
        	//System.out.println(t);
        	for(int i=1;i<=n;i++){ 
        	   sum+=n*1.0/i*1.0;
        	}
        	
        printf("Case %d: %lf\n",cas,sum);
        }
 }
           

期望DP：

#include<stdio.h>
#include<algorithm>
#include<iostream> 
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
const int maxn = 1e5+10;
double dp[maxn];
int main() {
    int t;
    scanf("%d", &t);
    int cas = 0;
    while(t--) {
        int n;
        scanf("%d", &n);
        dp[1] = 1.0;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + double(n) / (double(i) - 1.0);
        }
        printf("Case %d: %.10lf\n", ++cas, dp[n]);
    }
}