不备案 没版权 网站,免费空间刷赞,wordpress大不了,定制开发软件和产品这个题真的顶啊#xff01;思路#xff1a;n种图案#xff0c;m张印章#xff0c;每一个图案的概率是1/n#xff0c;这个概率以后用P表示首先我们定义dp[i][j]是买了i张印章#xff08;对应于上面的m#xff09;#xff0c;凑齐j种图案的概率#xff08;对应于上面的n…这个题真的顶啊思路 n种图案m张印章每一个图案的概率是1/n这个概率以后用P表示首先我们定义dp[i][j]是买了i张印章对应于上面的m凑齐j种图案的概率对应于上面的n然后是推导 1.如果ij的话说明无论买多少印章都不能凑齐j种图案所以概率我们就知道是0所以二维数组dp[i][j]02.如果j1说明买i张印章凑齐一种的概率这里分成两种情况讨论。①如果j1说明买一张凑齐一种的概率这个概率肯定是1②如果j1说明买j张凑齐一种的概率是多少。这里详细点想一想哈我们如果买两章也就是j2我们凑齐一种的概率是不是应该这样想p*p*n。这里的思路是我们要凑齐一种的概率但是我们抽了两张每一张的概率是不是p两张的概率是不是p*p。但是为什么乘n呢这样想哈我们一共有n种印章每一种的概率是不是都是一样的所以凑齐的这一个就有可能是n中印章的任意一种。所以得乘一个n3.接下来是普遍情况了。我们凑得印章都是随机的我们买之前是不知道下一个是哪种类别的所以如果下一张是之前已经存在过得印章的话也就是前面买的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-j1*p这里的式子就是dp[i][j] dp[i-1][j-1]*(n-(j-1))/n dp[i-1][j-1]*(n-j1)*p所以对于dp[i][j]这里的情况就是3,4两种情况相加了。代码是借鉴的其余博客未亲自编写
#includestdio.h
#includemath.h
#includealgorithm
#includestring.h
#includeiostream
using namespace std;
double dp[30][30];
int main(void)
{
int n,m;
cinnm;
double p1.0/n;
memset(dp,0,sizeof(dp));
for(int i1;im;i)//i张印章
{
for(int j1;jn;j)//j种图案
{
if(ij)//不可能凑齐
{
dp[i][j]0;
}
if(j1)//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-j1)*p;
}} }
printf(%.4lf\n,dp[m][n]);
return 0;
}
