买印章集齐图案蓝桥杯

Question

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

我的代码哪里有问题啊，为什么只对了37%？呜

#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
    int m,n,i,j; //dp[i][j]表示到第i个印章，集齐了j个图案的概率
    float dp[21][21];
    scanf("%d%d",&m,&n);
    memset(dp,0,sizeof(dp));
    //dp[1][1]=1; //第一个印章肯定是一种图案
    for(i=1;i<=m;i++)
        for(j=1;j<=i;j++)
        {
            if(j==1) dp[i][j]=pow(1.0/n,i-1);  //前i个印章都是一种
            else dp[i][j]=dp[i-1][j]*j*1.0/n+dp[i-1][j-1]*(n-j+1)*1.0/n;    
            //dp[i-1][j]表明di个印章前面一定出现了，dp[i-1][j-1]表明di个印章前面一定没有出现过
        }
    printf("%.4f",dp[m][n]);
    return 0;
}

Answer 1

上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

问题：买印章集齐图案蓝桥杯共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率，但是给出的代码只对了37%。

解决方案：

1. 首先需要明确题意，小A买了m张印章，要集齐n种图案，而每种图案的出现概率相同，因此这是一个概率问题，需要使用动态规划求解。

2. 为了方便，使用dp[i][j]表示到第i个印章，集齐了j种图案的概率，因此需要定义一个二维数组表示状态。注意，题目中的n表示印章的种类数，而不是图案的种类数，因此应该使用n表示图案的种类数。

3. 对于dp数组的初始化，需要特殊处理第一列，即dp[i][1]。当小A买了i个印章，但只集齐了一种图案时，由于每种图案的出现概率相同，因此有n种情况，故dp[i][1]应为pow(1.0/n,i-1)。

4. 接下来是状态转移方程的推导过程。当i>j时，显然无法集齐j种图案，因此dp[i][j]=0。当i=j时，最多只能集齐i种图案，因此dp[i][j]的值应该等于1。当i<j时，如果前i-1个印章已经集齐了j种图案，那么第i个印章就不能再出现已有的图案，所以此时的概率为dp[i-1][j]*(n-j+1)/n。如果前i-1个印章集齐了j-1种图案，而第i个印章又恰好出现了一种之前没有出现过的图案，那么此时的概率为dp[i-1][j-1]j/n。因此，状态转移方程如下：dp[i][j]=dp[i-1][j](n-j+1)/n+dp[i-1][j-1]*j/n。

5. 最后，在输出答案时，直接输出dp[m][n]即可。

修改后的代码：