蓝桥杯 算法训练 印章
共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。
输入输出:
一行两个正整数n和m
一个实数P表示答案,保留4位小数。
样例:
2 3
0.7500
这是个dp问题,存在两个变量,印章种类和购买的个数可以使用二维数组来进行模拟dp[m][n]
来表示在购买m个印章的情况下,存在n种印章数的情况
对情况进行分析
对于dp[i][j]
第一种情况 : i < j
即购买的印章小于存在的印章种类 ,概率肯定为0
第二种情况:i = j && j = 1
即只购买一种的情况下,存在一种印章的可能性,为1
i > j && j = 1
即购买的所有印章种类都一样,概率为 P ^ i * n = (1/n)^(i-1)
第三种情况:i > j && j != 1
在中间状态的情况,分为两种,一种是第 i 买的印章种类已经存在, 第二种是第 i 次买的印章还没有存在
dp[i - 1][j] * (j * P)
dp[i - 1][j - 1] * (n - (j - 1)) * P
这两种情况相加,就是中间类型的情况
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 25;
double dp[N][N];
int n,m;
int main()
{
cin >> n >> m;
double P = 1.0 / n;
for(int i = 1;i < m;i ++)
{
for(int j = 1;j < n; j ++)
{
if(i < j) dp[i][j] = 0;
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] * ((n - j + 1) * P);
}
}
}
printf("%.4lf",dp[m][n]);
return 0;
}