首页 > 代码库 > UVa10288概率

UVa10288概率

 

技术分享

技术分享

 

题意:

每张彩票上印有一张图案,要集齐n个不同的图案才能获奖。输入n,求要获奖购买彩票张数的期望(假设获得每个图案的概率相同)。

分析:

假设现在已经有k种图案,令s = k/n,得到一个新图案需要t次的概率为:st-1(1-s);

因此,得到一个新图案的期望为(1-s)(1 + 2s + 3s2 + 4s3 +...)

下面求上式中的级数:

技术分享

技术分享

所以得到一个新图案的期望为:技术分享

总的期望为:技术分享

 

#include "iostream"
#include "cstdio"
#include "sstream"
using namespace std;
#define LL long long
struct Fractions {
    LL numerator;
    LL denominator;
    Fractions(){
        numerator=1;
        denominator=1;
    }
};
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
void add(Fractions&a,Fractions&b)
{
    a.numerator=a.numerator*b.denominator+b.numerator*a.denominator;
    a.denominator*=b.denominator;
    LL t=gcd(a.numerator,a.denominator);
    a.numerator/=t;
    a.denominator/=t;
}
int length(LL x)
{
    stringstream ss;
    ss<<x;
    return ss.str().length();
}
void print_chars(char c,int len)
{
    while(len--)
        putchar(c);
}
int main()
{
    LL n;
    while(~scanf("%lld",&n))
    {
        Fractions ans_f,tf;
        for(LL i=2;i<=n;i++)
        {
            tf.numerator=1;
            tf.denominator=i;
            add(ans_f,tf);
        }
        ans_f.numerator*=n;
        LL t=gcd(ans_f.numerator,ans_f.denominator);
        ans_f.denominator/=t;
        ans_f.numerator/=t;

        if(ans_f.denominator==1){
            cout<<ans_f.numerator<<endl;
        }
        else if(ans_f.numerator>ans_f.denominator)
        {
            LL mix=ans_f.numerator/ans_f.denominator;
            int len=length(mix)+1;
            print_chars( ,len);
            cout<<ans_f.numerator%ans_f.denominator<<endl;
            cout<<mix;cout<<" ";
            int len1=length(ans_f.denominator);
            print_chars(-,len1);cout<<endl;
            print_chars( ,len);
            cout<<ans_f.denominator<<endl;
        }else
        {
            cout<<ans_f.numerator<<endl;
            int len=length(ans_f.denominator);
            print_chars(-,len);
            cout<<endl<<ans_f.denominator<<endl;
        }
    }
    return 0;
}

 

 http://www.cnblogs.com/AOQNRMGYXLMV/p/4180474.html

 

UVa10288概率