[数据结构与算法] 蓝桥杯试题算法训练印章_python

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 蓝桥杯试题算法训练印章_python_个人练习 -> 正文阅读

[数据结构与算法]蓝桥杯试题算法训练印章_python_个人练习

资源限制

时间限制：1.0s ? 内存限制：256.0MB

问题描述

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

输入格式

　　一行两个正整数n和m

输出格式

　　一个实数P表示答案，保留4位小数。

数据规模和约定

　　1≤n，m≤20

?此题采用动态规划（Dynamic Programming，DP）的方法求解，动态规划的三要素：最优子结构、边界和状态转移函数。

边界	问题最小子子集的解（初始范围）
最优子结构	每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
状态转移函数	从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)

对于本题，

·设置状态：当前状态下的数据包含小A手里的印章数目、印章的种类数目，因此可以构建二维数组 $dp[i][j]$ 来存储概率。令 $dp[i][j]$ ?=?小A手里的印章数目为 $i$ 、印章的总种类数目为n时小A收集齐 $j$ 种印章的概率。

·边界：初始状态即找 $i j$ =0,1....时 $dp[i][j]$ 的值，

当 $j$ ?= 1时：i = 1时， $dp[1][1]$ 表示小A手里有1枚印章并且集齐了一种类型的概率，易知为1；

i > 1时， $dp[i][1]$ 表示小A手里有i枚印章并且收集到了一种类型的概率，也就是说小A手里的这i枚印章全是一种类型的，但是一共有n种类型（键盘输入），因此 $dp[i][1]$ $= n * (\frac{1}{n})^{i}$ $= (\frac{1}{n})^{i-1}$ 。

还有一种明显的情况可以容易得出的是：当 i < j 时，即小A手里有 i 枚印章收集到 j 种的概率，显然为 0 。

·状态转移函数：找递推式，即找状态之间的关系，这样就能从初始状态一直往下推了。在中间状态 $dp[i][j]$ ：从手里有 $(i-1)$ 枚印章到有? $i$ ?枚印章时，有两种情况：第一种，拿到的这枚印章种类手里已经有了，此时 $dp[i][j]$ 表示手里已经有 j 种印章了，因为和手里的重复了，因此上个状态（即手里有(i-1)枚印章时）也是只有 j 种印章，即 $dp[i-1][j]$ ?。那此时拿的这一枚肯定是 j 中的其中一枚，因此 $dp[i][j] = dp[i-1][j] * \frac{j}{n}$ ；第二种，拿到的这枚印章种类手里还没有，此时上个状态表示为 $dp[i-1][j-1]$ ，一共有 n 种印章，前面已经取了（j-1）种了，而现在取的和前面没有重复，因此取的是 n-(j-1)中的其中一个，因此

? $pd[i][j] = dp[i-1][j-1] * \frac{n-(j-1))}{n} = dp[i-1][j-1] * \frac{n-j+1}{n}$ 。这两种情况加起来即得到状态转移函数。

python代码实现如下：

#2021.11.15 试题 算法训练 印章
import numpy as np
n,m = map(int,input().split())#n种图案，小A买了m张印章
#动态规划：用dp[i][j]表示小A集齐n种印章的概率，其中i、j分别表示当前状态的买的印章数目和收集到种类数目
dp = np.zeros((25,25),dtype=np.float64)#创建二维空数组
#边界/初始状态：
for i in range(1,m+1):
    for j in range(1,n+1):
        if i < j :
            dp[i][j] = 0
        elif j == 1 :
            dp[i][j] = (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)#状态转移函数

s = float(dp[m][n])
print("%.4f"%s)#按照题目要求输出四位小数