首页 > 代码库 > UVA 10288 Coupons (概率)
UVA 10288 Coupons (概率)
题意:有n种纸片无限张,随机抽取,问平均情况下抽多少张可以保证抽中所有类型的纸片
题解:假设自己手上有k张,抽中已经抽过的概率为 s=k/n;那抽中下一张没被抽过的纸片概率为 (再抽一张中,两张中,三张中...)(1-s)*(1+2*s+3*s^3+...)=(1-s)*E
s*E = (s+2*s^2+3*s^3+...);则E-s*E = (1+s+s^2+s^3+...)(等比数列,且公比不可能为1)=1/(1-s) = n/(n-k)
所以总概率就是n*(1/n+1/(n-1)+...+1/2+1/1);注意需要约分,还有带分数的计算:(a b/c)*d = a*d+b*d/c
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const ll INF=1LL<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=200010; ll inte,mole,demn;//分子 分母 int Gcd(ll a,ll b) { return b==0LL?a:Gcd(b,a%b); } void Fraction(int n)//计算n*(1/1+1/2+...+1/n) { mole=demn=1LL; inte=0LL; for(int i=2;i<=n;++i) { mole=mole*(ll)i+demn; demn*=(ll)i; ll gcd=Gcd(demn,mole); demn/=gcd; mole/=gcd; inte+=mole/demn; mole%=demn; } inte*=(ll)n; mole*=(ll)n; inte+=mole/demn; mole%=demn; ll gcd=Gcd(mole,demn); mole/=gcd; demn/=gcd; // printf("%I64d %I64d %I64d\n",inte,mole,demn); return; } int Length(ll n)//n的长度 { int m=0; while(n) { n/=10; m++; } return m; } void Print(int n)//之一输出格式 { if(demn==1LL){ printf("%lld\n",inte); }else{ int m=Length(inte)+1; for(int i=0;i<m;++i) printf(" "); printf("%lld\n%lld ",mole,inte); for(int i=0;i<Length(demn);++i) printf("-"); printf("\n"); for(int i=0;i<m;++i) printf(" "); printf("%lld\n",demn); } return; } int main() { int n; while(~scanf("%d",&n)) { Fraction(n); Print(n); } return 0; }
UVA 10288 Coupons (概率)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。