蓝桥杯试题 算法训练 印章

印章"/>

蓝桥杯试题 算法训练 印章

试题 算法训练 印章 C/C++

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。

输入格式

一行两个正整数n和m

输出格式

一个实数P表示答案，保留4位小数。

样例输入

2 3

样例输出

0.7500

· 数据规模和约定
　　1≤n，m≤20

解题思路

1.题目已经提示用dp算法了（没有提示确实比较难想到使用dp算法QVQ）。则使用dp算法，dp[n][m]数组中，n表示抽到n种印章，m表示买的印章数。
2. 用到dp则首先要算出最初始的基本情况，即一般情况下先求出左边一列和最上面一行的数。
3. 求左边一列时，容易想到存在当需要抽到的种数大于买的印章数，其概率是0.
4. 下面就是求最上面一行，即集齐一种印章的概率。也就是求买的j个印章都是一种印章的概率。此时j个印章都是一种印章的概率为p^j，又因为有i种情况，每个情况都是p^j的概率，总共有n个情况，所以总共i为1的概率为p^j*n=p^j/p=p^j-1
5. 接下来就是正常的递推关系了，dp[i][j]怎么才能和dp[i-1][j-1]、dp[i][j-1]或dp[i-1][j-1]联系在一起呢？

• 我们可以想到j个印章及其i种印章的是由j-1个印章集齐i种印章和j-1个印章集齐i-1种印章概率之和。
• 难道没有其他情况了吗？似乎是没有了，即使有也可以归结成上面两种情况，比如对于上面提到的dp[i-1][j]，其指的是j个印章集齐i-1种，所以j个印章集齐i种已经是不可能的了。
• 所以我们只需要求dp[i][j]与dp[i][j-1]和dp[i-1][j-1]之间的关系就行。
  – 对于dp[i][j-1]，其说明在j-1个印章已经收集了i种印章，所以剩余的印章只要是已经收集的i种印章中的情况即可。所以其概率要乘上p*i，表示最后一个印章为已经集齐的i种的概率。
  – 对于dp[i-1][j-1]，其说明j-1个印章已经收集了i-1种印章，所以剩下的一个印章不是已经收集的i-1种的印章就能收集齐i种印章了。所以其要乘上(n-(i-1))*p，表示最后一个印章为不是已经收集齐的i-1种印章的概率。
• 最后将思路实现即可

#include<iostream>
#include<math.h>
using namespace std;
int n,m;
double dp[25][25];
int main(){cin>>n>>m;double p=1.0/n; //每个印章买一种印章的概率 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i>j){	//对于买的印章数小于要集齐的印章则概率为0 dp[i][j]=0;}else if(i==1){//对于只集齐一种印章的情况 dp[i][j]=pow(p,j-1);}else{//其他情况 dp[i][j]=dp[i][j-1]*p*i+dp[i-1][j-1]*(n-(i-1))*p;}}}printf("%.4lf",dp[n][m]);return 0;
} 

最后，有不对的地方欢迎大家指正OvO