资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
一行两个正整数n和m
输出格式
一个实数P表示答案，保留4位小数。
样例输入
2 3
样例输出
0.7500
数据规模和约定
1≤n，m≤20
提交代码
| 编译语言： | C++CJavaPython |
|---|---|
| 代码： |
共有 n 种图案的印章，每种图案的出现概率相同。故买到某种图案的印章的概率为 1/n 。
买了 i 次，集齐 j 种图案。
当 i < j 是不可能事件，故概率为 0 ；
当 j = 1 时，表达买了 i 次，买的都是同一种，故概率为（1/n）^ j * n ；
当 i > j ，j ！= i 时，分为两种情况：
前 i-1 次买到了 j 种，故第 i 次买到的只能是 j 种中的一种，即 dp [ i-1 ] [ j ] * （1/n）* j；
前 i-1 次买到了 j-1 种，故第 i 次买到的只能是 n-j 种中的一种，即 dp [ i-1 ] [ j-1 ] * （1/n）* （n-j+1）。
原文链接：https://blog.csdn.net/qq_45256352/article/details/123958444
【解析】
首先我们知道这道题目是DP类型的，就开门见山了。
1.在做DP题目的时候，我们首先要确定这道题是几维的DP数组？
我们分析题目可知，这道题有两个极其清晰的条件，就是购买的次数和需要集齐的印章个数，所以这是一道二维数组题。
2.如何确定DP数组的初始条件，对于一维的，一般是前两个元素，对于二维而言，一般是第一行和第一列，如果条件多的话还能多初始几行；对于三维而言，我……暂时做不出来。
前面说了有两个条件，那么在二维数组中，那个是行，哪个是列呢，我们来分析一下。
假设要集齐的印章个数为行，购买的次数为列。对于初始数组的时候貌似基本都是零，没有可利用的数据，可知不是。
所以购买的次数为行，勋章的集齐个数为列。
初始化数组：前提条件（我们可知当购买的次数小于勋章个数时，P==0）。
我们先把这些i<j的元素先初始化为0；
if(i<j)
dp[i][j]=0;
然后分析第一列元素，购买i次，只集齐一种印章，那么P=（1/n）^i *n。
解释：购买的结果共有1/n）^i 种，但是元素全部一样的却只有n种。
else if(j==1)
dp[i][j]=pow(p,i-1);
接着就是一般情况，对于其他元素而言，dp[i][j]这个数该如何计算呢？
这个元素就代表购买i次，集齐j个印章。
有两个情况：
第i次不要要集齐新的印章了，也就是说前i-1次集齐了j种。
计算公式：dp[i-1][j]*(j/n)
第i次需要集齐新印章，也就是说前i-1次集齐了j-1种。
计算公式：dp[i-1][j]*(n-（j-1）/n)文章来源：https://www.toymoban.com/news/detail-407309.html
#include<stdio.h>
#include<math.h>
int main(){
int n,m;
scanf("%d %d",&n,&m);
double p=1.0/n;
double dp[m+1][n+1];
int i,j;
for(i=1;i<m+1;i++){
for(j=1;j<n+1;j++){
if(i<j)
dp[i][j]=0;
else if(j==1)
dp[i][j]=pow(p,i-1);
else
dp[i][j]=dp[i-1][j]*p*j+dp[i-1][j-1]*p*(n-j+1);
}
}
printf("%.4lf",dp[m][n]);
return 0;
}
原文链接：https://blog.csdn.net/weixin_53535434/article/details/127031561文章来源地址https://www.toymoban.com/news/detail-407309.html
到了这里，关于蓝桥杯算法训练1：印章的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
