UVa10288概率

UVa10288概率

UVa10288概率

题意:

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

分析:

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

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

下面求上式中的级数:

UVa10288概率

UVa10288概率

所以得到一个新图案的期望为:UVa10288概率

总的期望为:UVa10288概率

#include "iostream"
#include "cstdio"
#include "sstream"
using namespace std;
#define LL long long
struct Fractions {
LL numerator;
LL denominator;
Fractions(){
numerator=;
denominator=;
}
};
LL gcd(LL a,LL b)
{
return b==?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=;i<=n;i++)
{
tf.numerator=;
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==){
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)+;
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 ;
}

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

上一篇:asp.net core mvc 统一过滤参数,防止注入漏洞攻击


下一篇:iOS开发——代码生成TabBar与视图切换具体解释