印章"/>
蓝桥杯算法训练之印章
问题描述:
共有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问题,对于核心问题还是不太明白,希望后面通过其他的练习可以继续提升。
更多推荐
蓝桥杯算法训练之印章
发布评论