蓝桥杯算法训练之印章

印章"/>

蓝桥杯算法训练之印章

问题描述：
　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
输入格式
　　一行两个正整数n和m
输出格式
　　一个实数P表示答案，保留4位小数。
代码如下：

#include<stdio.h>
#include<math.h>
int main()
{int n = 0;int m = 0;int a = 0;int b = 0;scanf("%d %d", &n, &m);double dp[25][25] = { 0 };double p = 1.0 / n;for (a = 1; a <=m; a++){for (b = 1; b <=n; b++){if (a < b)dp[a][b] = 0;if (b == 1){dp[a][b] = pow(p, a - 1);}else{dp[a][b] = dp[a - 1][b] * (b * 1.0 / n) + dp[a - 1][b - 1] * ((n - b + 1) * 1.0 / n);}}}printf("%.4lf", dp[m][n]);return 0;
}

运行结果如下：

代码我是借鉴另一位大佬的，刚刚开始接触这种dp问题，对于核心问题还是不太明白，希望后面通过其他的练习可以继续提升。