蓝桥杯-算法-印章问题

这个题真的顶啊！

思路：

n种图案，m张印章，每一个图案的概率是1/n，这个概率以后用P表示

首先我们定义dp[i][j]是买了i张印章（对应于上面的m），凑齐j种图案的概率（对应于上面的n）

然后是推导：

1.如果i<j的话，说明无论买多少印章，都不能凑齐j种图案，所以概率我们就知道是0，所以二维数组dp[i][j]=0

2.如果j=1，说明买i张印章，凑齐一种的概率

这里分成两种情况讨论。

①如果j=1，说明，买一张凑齐一种的概率，这个概率肯定是1

②如果j>1，说明买j张，凑齐一种的概率是多少。

这里详细点，想一想哈，我们如果买两章，也就是j=2，我们凑齐一种的概率是不是应该这样想：p*p*n。这里的思路是：我们要凑齐一种的概率，但是我们抽了两张，每一张的概率是不是p，两张的概率是不是p*p。但是为什么乘n呢，这样想哈，我们一共有n种印章，每一种的概率是不是都是一样的，所以凑齐的这一个就有可能是n中印章的任意一种。所以得乘一个n

3.接下来是普遍情况了。

我们凑得印章都是随机的，我们买之前是不知道下一个是哪种类别的

所以，如果下一张是之前已经存在过得印章的话（也就是前面买的i-1张已经凑齐了j种，接下来的第i张就是重复前面的印章了），所以这个重复的印章再被抽取的时候，它的概率就是j*p(再详细点，前面已经有了j种了，我们此时假设的是，与之前的重复了，而与每一个重复的概率都是p，所以这里是j*p)

这里的式子是：

dp[i][j] = dp[i-1][j] * (j/n) = dp[i-1][j] *(j*p)

4.然后再就是抽取的印章不是重复的情况了

这个说明前i-1张我们凑齐了j-1种，而第i张，也就是接下来的这一张就是要凑齐的一种，但是我们不确定这一个出现的是没出现印章中的哪一种（有点儿绕，慢慢想一下）。因为前面已经出现了j-1种，所以还有n-(j-1)种没有出现。而接下来的这个只要是这没有出现的一种就行了，这个时候凑齐这一种的概率就是（n-j+1）*p

这里的式子就是：

dp[i][j] = dp[i-1][j-1]*(n-(j-1))/n = dp[i-1][j-1]*(n-j+1)*p

所以对于dp[i][j]这里的情况，就是3,4两种情况相加了。

代码是借鉴的其余博客，未亲自编写

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std; 
double dp[30][30];
int main(void)
{
int n,m;
cin>>n>>m;
double p=1.0/n;
memset(dp,0,sizeof(dp)); 
for(int i=1;i<=m;i++)//i张印章 
{
for(int j=1;j<=n;j++)//j种图案 
{
if(i<j)//不可能凑齐 
{
dp[i][j]=0;
}
if(j==1)//j只要所有图案中的一种就可以了，所以我们(1/n)^i还要再乘n，就是p^i-1 
{
dp[i][j]=pow(p,i-1);
}
else//买了i张凑齐j种，第i张 要么和之前凑齐的一样，要么不一样 
{
dp[i][j]=dp[i-1][j]*(j*p)+dp[i-1][j-1]*(n-j+1)*p;
}} } 
printf("%.4lf\n",dp[m][n]);
return 0;
}