印章"/>
蓝桥杯 印章
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案,保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n,m≤20
通过输入确定了印章的图案个数n和所购买的印章数m
定义中间变量i j ;中间目前所集齐图案数量i;中间目前所购买印章数量j;
而每一种图案出现的概率为p;p=1/n
分情况讨论
当印章的图案个数n大于所购买的印章数m时:概率为0;永远也集不齐
当印章的图案个数n小于等于所购买的印章数m时:
当目前只凑齐第一个图案时即i=1时:
购买第一个印章时概率1.0;
购买第二个印章时即第二个印章和第一个印章相同;概率就为1/n=p
购买第三个印章时即第三个印章和前几个印章相同;概率就为1/n*1/n=p*p
。。。。
购买第j个印章时即第j个印章和前几个印章相同;概率就为(1/n)^(j-1)=p^(j-1)
当目前只凑齐的图案不是第一个图案时 即i!=1时:
刚刚买的印章有两种可以:
1.与之前买的相同
那么之前是有了i种而总共有n种;
所以第j种的概率为i/n即i*p;
那么有i个品种,买了j个的概率是有i个品种,买了j-1个的概率乘上i*p
2.与之前买的不同
同理
那么之前是有了i-1种而总共有n种;
所以第j种的概率为n-(i-1)/n即(n-(i-1))*p;
那么有i个品种,买了j个的概率是有i-1个品种,买了j-1个的概率乘上(n-(i-1))*p;
而总概率就是他们两种情况相加即a[i][j]=a[i-1][j-1]*((n-(i-1))*1.0)*p+a[i][j-1]*(i*p);
#include<stdio.h>
int main()
{
int n;
int m;
int i=1;
int j=1;
int k=1;
double p;
double a[21][21]={0.0};
scanf("%d %d",&n,&m);
p=1.0/n;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++){if(i==1){ a[i][j]=1.0;for(k=1;k<j;k++){a[i][j]*=p;}}else{a[i][j]=a[i-1][j-1]*((n-(i-1))*1.0)*p+a[i][j-1]*(i*p);}}
}
printf("%.4lf",a[n][m]);
return 0;
}
更多推荐
蓝桥杯 印章
发布评论