概率练习 (16.04.30)

概率练习 (16.04.30)

继之前的概率dp，这次博文同样和概率相关，但不仅仅限于dp处理。

UVA - 10288 Coupons

​​ 大意：买彩票，图案有n种，如果收集到所有的n种彩票就能得到大奖。问平均情况下需要买多少张彩票？ 分析：推状态 ⟶ 假设现在已经有了i种彩票，那么购买j的概率就是： 设 p=in，购买j次的概率就是 pj−1(1−p) 那么期望

E=1p0(1−p)+2p1(1−p)+3p2(1−p)+⋯+kpk−1(1−p)pE=p1(1−p)+2p2(1−p)+⋯+kpk(1−p)(1−p)E=(1−p)+p(1−p)+p2(1−p)+⋯+pk−1(1−p)−kpk(1−p)=(1−p)(1+p+p2+⋯+pk−1−kpk)E=1−pk1−p−kpk=1−pk−kpk(1−p)1−p=11−p=nn−i

那么结果就是

∑i=0n−1nn−i

#include #include #include using namespace std;typedef long long LL;LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}int main(){ LL n; while(cin>>n){ LL p1=n,p2=n,d; for(int i=1;i

poj 3744 Scout YYF I

​​ 大意：在一段路途中，给出N个地雷地点，一个人一次走1步或者2步，求解顺利通过此路的概率。 分析：N很小，其数组元素ai很大，列出转移式子，dp[i]=p×dp[i−1]+(1−p)×dp[i−2] 当然，我们没有那么大的空间用于dp数组， 他只是假想存在的。 对于通过ai的概率就是

(dp[i]dp[i−1])=(p11−p0)ai−1(dp[1]dp[0])=(p11−p0)ai−1(10)

如果能够顺利通过，那么地雷点绝对是分界点！ 分段： 1——x1 x1+1——x2 x2+1——x3 …… 且到达x1+1，x2+1的概率是1！

#include #include #include using namespace std;int a[15];struct matrix{ double m[2][2];}A;matrix I={1,0,0,1};matrix multi(matrix m1,matrix m2){ matrix ans; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ ans.m[i][j]=0; for(int k=0;k<2;k++){ ans.m[i][j]+=m1.m[i][k]*m2.m[k][j]; } } } return ans;}matrix power(matrix m1,int p){ matrix ans=I; while(p){ if(p&1) ans=multi(ans,m1); m1=multi(m1,m1); p>>=1; } return ans;}int main(){ //freopen("cin.txt","r",stdin); int n; double p; while(~scanf("%d%lf",&n,&p)){ for(int i=0;i

hdu 5245 Joyful

​​(i-1)(j-1)(m-i+1)*(n-j+1);

A在2时，B可以在4,5,6,7,8,9 (i-1)1(m-i+1)*n;

3: (i-1)(n-j)(m-i+1)*j;

4: 1*(j-1)*(n-j+1)*m;

5: m*n

6: (n-j)*1*j*m;

7: (m-i)(j-1)*i(n-j+1);

8: (m-i)*1*i*n;

9: (m-i)*(n-j)*i*j;

最后一个格子被覆盖的概率就是：1−(1−si,jm2n2)k

关于pow函数： C++提供以下几种pow函数的重载形式： double pow(double X,int Y); float pow(float X,float Y); float pow(float X,int Y); long double pow(long double X,long double Y); long double pow(long double X,int Y);

靠！ 当pow()的指数参数是浮点数时，运行效率很低。很容易超时。 但Y是整数时，利用分治递归可以提高效率。

自己写函数替代pow(double, double)：

#include #include #define LL long longint main(){ //freopen("cin.txt","r",stdin); int t,ca=1; LL n,m,K; scanf("%d",&t); while(t--){ scanf("%I64d%I64d%I64d",&m,&n,&K); double ans=0; for(LL i=1;i<=m;i++){ for(LL j=1;j<=n;j++){ double s=0.0; s+=(i-1)*(j-1)*(m-i+1)*(n-j+1); s+=(i-1)*1*(m-i+1)*n; s+=(i-1)*(n-j)*(m-i+1)*j; //3 s+=1*(j-1)*(n-j+1)*m; s+=m*n; s+=(n-j)*1*j*m; s+=(m-i)*(j-1)*i*(n-j+1); s+=(m-i)*1*i*n; s+=(m-i)*(n-j)*i*j; s=s/m/m/n/n; //s=pow((1.0-s),1.0*K); double tt=1.0-s; s=1; for(int it=0;it

或者用C++的pow函数重载： pow(double, int) //不能用C写，否则无法顺利重载

#include #include #define LL long longint main(){ //freopen("cin.txt","r",stdin); int t,ca=1; LL n,m; int K; scanf("%d",&t); while(t--){ scanf("%I64d%I64d%d",&m,&n,&K); double ans=0; for(LL i=1;i<=m;i++){ for(LL j=1;j<=n;j++){ double s=0.0; s+=(i-1)*(j-1)*(m-i+1)*(n-j+1); s+=(i-1)*1*(m-i+1)*n; s+=(i-1)*(n-j)*(m-i+1)*j; //3 s+=1*(j-1)*(n-j+1)*m; s+=m*n; s+=(n-j)*1*j*m; s+=(m-i)*(j-1)*i*(n-j+1); s+=(m-i)*1*i*n; s+=(m-i)*(n-j)*i*j; s=s/m/m/n/n; s=pow((1.0-s),K); /*double tt=1.0-s; s=1; for(int it=0;it

效率对比：

acdream 1113 The Arrow

​​ 大意：一个人扔色子，每次将点数相加，如果大于N，保证点数和不变，否则加上得到的点数，问掷色子的次数的期望。

分析：如果是”>=N”的类型问题，应该是dp[i]=∑(16dp[i+j])+1 对于这种”==N”的类型问题，dp[i]=k×dp[i]16+∑(dp[i+j]16)+1 化简得到: dp[i]=66−k(∑dp[i+j]16+1)

#include #include #include using namespace std;const int N=1e5+10;double dp[N]; int main(){ int t,n; cin>>t; while(t--){ scanf("%d",&n); memset(dp,0,sizeof(dp)); for(int i=n-1;i>=0;i--){ int k=0; double temp=0; for(int j=1;j<=6;j++){ if(i+j>n) k++; else temp+=dp[i+j]*1.0/6; } temp++; dp[i]+=temp*6.0/(6-k); } printf("%.2lf\n",dp[0]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。