蓝桥杯 印章

印章"/>

蓝桥杯 印章

资源限制

时间限制：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;
}