首页 > ACM题库 > HDU-杭电 > HDU 4465-Candy-概率-[解题报告]HOJ
2015
07-16

HDU 4465-Candy-概率-[解题报告]HOJ

Candy

问题描述 :

LazyChild is a lazy child who likes candy very much. Despite being very young, he has two large candy boxes, each contains n candies initially. Everyday he chooses one box and open it. He chooses the first box with probability p and the second box with probability (1 – p). For the chosen box, if there are still candies in it, he eats one of them; otherwise, he will be sad and then open the other box.
He has been eating one candy a day for several days. But one day, when opening a box, he finds no candy left. Before opening the other box, he wants to know the expected number of candies left in the other box. Can you help him?

输入:

There are several test cases.
For each test case, there is a single line containing an integer n (1 ≤ n ≤ 2 × 105) and a real number p (0 ≤ p ≤ 1, with 6 digits after the decimal).
Input is terminated by EOF.

输出:

There are several test cases.
For each test case, there is a single line containing an integer n (1 ≤ n ≤ 2 × 105) and a real number p (0 ≤ p ≤ 1, with 6 digits after the decimal).
Input is terminated by EOF.

样例输入:

10 0.400000
100 0.500000
124 0.432650
325 0.325100
532 0.487520
2276 0.720000

样例输出:

Case 1: 3.528175
Case 2: 10.326044
Case 3: 28.861945
Case 4: 167.965476
Case 5: 32.601816
Case 6: 1390.500000

计算组合数最大的困难在于数据的溢出,对于大于150的整数n求阶乘很容易超出double类型的范围,那么当C(n,m)中的n=200时,直接用组合公式计算基本就无望了。另外一个难点就是效率。

    对于第一个数据溢出的问题,可以这样解决。因为组合数公式为:
    C(n,m) = n!/(m!(n-m)!)

    为了避免直接计算n的阶乘,对公式两边取对数,于是得到:
    ln(C(n,m)) = ln(n!)-ln(m!)-ln((n-m)!)

    进一步化简得到:

    Candy

    这样我们就把连乘转换为了连加,因为ln(n)总是很小的,所以上式很难出现数据溢出。

    为了解决第二个效率的问题,我们对上式再做一步化简。上式已经把连乘法变成了求和的线性运算,也就是说,上式已经极大地简化了计算的复杂度,但是还可以进一步优化。从上式中,我们很容易看出右边的3项必然存在重复的部分。现在我们把右边第一项拆成两部分:

    Candy

    这样,上式右边第一项就可以被抵消掉,于是得到:

    Candy

    上式直接减少了2m次对数计算及求和运算。但是这个公式还可以优化。对于上面公式里的求和,当m<n/2时,n-m是一个很大的数,但是当m>n/2时,n-m就会小很多。我们知道:
    C(n,m) = C(n,n-m)

    那么通过这个公式,我们可以把小于n/2的m变为大于n/2的n-m再进行计算,结果是一样的,但是却能减少计算量。

    当计算出ln(C(n,m))后,只需要取自然对数,就可以得到组合数:
    C(n,m) = exp(ln(C(n,m)))

    这样就完成了组合数的计算。

    用这种方法计算组合数,如果只计算ln(C(n,m))的话,n可以取到整型数据的极限值65535,

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
double f[400008];
double C_m_n(int m,int n)
{

    return f[m]-f[n]-f[m-n];
}
int main()
{
     f[0]=0;
    for(int i=1;i<=400006;i++)
    f[i]+=f[i-1]+log(i*1.0);
   double sum,p;
   int n,test=0;
   while(cin>>n>>p)
   {
       sum=0;
       printf("Case %d: ",++test);
       for(int k=0;k<=n-1;k++)
       {
           sum+=(n-k)*(exp((C_m_n(n+k,k))+(n+1)*log(p)+k*log(1-p))+exp((C_m_n(n+k,k))+(n+1)*log(1-p)+k*log(p)));
       }
       printf("%.6f\n",sum);
   }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sylg_li/article/details/8208514