LightOJ_1248 Dice (III)-白红宇

LightOJ_1248 Dice (III)

阅读量：4693 次

发布时间：2019-06-09

本文共 1206 字，大约阅读时间需要 4 分钟。

题意：

　　给一个质地均匀的n的骰子，求投掷出所有点数至少一次的期望次数。

思路：

　　这就是一个经典的邮票收集问题（Coupon Collector Problem）。

　　投掷出第一个未出现的点数的概率为n/n = 1，因为第一次投掷必然是未出现的。

　　第二个未出现的点数第一次出现的概率为 (n - 1) / n，因为有一个已经投掷出现过。

　　第i个未出现的点数第一次出现的概率为 (n - i) / i，这满足几何分布。

　　其期望E = 1/p

　　所以期望为n *（1 + 1 / 2 + 1 / 3 + ... 1 / n）。

代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
             8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 using namespace std;17 #define LL long long18 #define INF 0x3f3f3f3f19 #define MOD 100000000720 #define eps 1e-621 #define MAXN 10001022 #define yy 0.577215664923 double f[MAXN];24 void init()25 {26 f[0] = 0.0;27 for(int i = 1; i < MAXN; i ++)28 f[i] = f[i-1] + 1.0 / (i * 1.0);29 }30 double GetExpectation(int n)31 {32 return n * 1.0 * f[n];33 }34 35 int main()36 {37 int T;38 int kcase = 0;39 init();40 scanf("%d", &T);41 while(T --)42 {43 int n;44 scanf("%d", &n);45 printf("Case %d: %.7lf\n", ++ kcase, GetExpectation(n));46 }47 return 0;48 }