首页 > 代码库 > 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概率
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。