1.题目
2.代码
1
2
3
4
5
6
7
8
9
10
11
12
|
#共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。 n,m = map ( int , input ().split()) dp = [[ 0 for i in range (n + 1 )] for j in range (m + 1 )] for i in range ( 1 ,m + 1 ): for j in range ( 1 ,n + 1 ): if (j>i): dp[i][j] = 0 elif (j = = 1 ): dp[i][j] = pow ( 1 / n,i - 1 ) else : dp[i][j] = (dp[i - 1 ][j]) * (j * 1.0 / n) + (dp[i - 1 ][j - 1 ]) * ((n - j + 1 ) * 1.0 / n) print ( '{:.4f}' . format (dp[m][n])) |
3.代码解析
这个题我开始想的第一个方法是深搜,因为想着每一个都是选择的问题,没一次的选项都一样,但是发现如果每一次搜索的很多的话很费时间,而且去写代码的时候思路也不是很清晰。
后面按照蓝桥杯的提示说是dp(动规),因此换了方法。
首先按照输入n,m,这里是python蓝桥杯中常用的输入方法:
map(int,input().spilt)
这里的map就是映射,将input().spilt切割后的数都用int函数转换为int型。
*重点(别把上面的i和j和下面的i和j看反了):dp数组就是在初始已知的值中去考虑递进的状态
(1)j>i的情况,即当只买了i张,集赞到对应j张的概率,这是不可能的,因为为0。进行以下初始化
1
2
|
if (j>i): dp[i][j] = 0 |
(2)j=1:的情况,即集赞到j的概率,这种情况下,一张就是需要的那张那个就概率为1/n
(3)其他情况,对于买了i张集赞到对应j张的概率=买了i-1张积攒 j 张的概率*(新的一次再一次选中j张中的一张的概率)+买了i-1张积攒 j-1 张的概率*(选中n张目标图中除去不在目标图j数目中的概率)
1
|
dp[i][j] = (dp[i - 1 ][j]) * (j * 1.0 / n) + (dp[i - 1 ][j - 1 ]) * ((n - j + 1 ) * 1.0 / n) |
以上就是Python印章代码实现算法解析的详细内容,更多关于Python印章代码算法的资料请关注服务器之家其它相关文章!
原文链接:https://blog.csdn.net/qq_51096893/article/details/123432356