Python实现印章代码的算法解析
作者：奋斗中的小宸宸 发布时间：2023-10-14 15:18:24
标签：Python,印章,算法
1.题目
2.代码
#共有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。进行以下初始化
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数目中的概率）
dp[i][j]=(dp[i-1][j])*(j*1.0/n)+(dp[i-1][j-1])*((n-j+1)*1.0/n)
来源：https://blog.csdn.net/qq_51096893/article/details/123432356
0
投稿猜你喜欢
- 可能接触网站与编程设计的人都知道，一个属性值需要引号包括起来，但是有的时候就是因为没有正确设定引号类型，导致程序出错，就连我自己也是这样，我
一：绑定方法：其特点是调用方本身自动作为第一个参数传入1.绑定到对象的方法：调用方是一个对象，该对象自动传入2.方法绑定到类：调用方是类，类- 近期，需要实现检测摄像头中指定坐标区域内的主体颜色，通过查阅大量相关的内容，最终实现代码及效果如下，具体的实现步骤在代码中都详细注释，代码还
- 这几天在落伍上转转，发现有朋友不太明白一些网站在会员注册时，当输入用户名后没按“确定”提交数据，系统也能马上检测该用户名是否已经存在。在此我
- 也许你刚刚来到一家公司，他们希望进行一些“可用性”工作。你可能是一名UI设计师，业务分析师，或前端开发人员，一名产品经理，或者负责用户体验部
- 前段时间由于收集视频数据的需要，自己捣鼓了一个YouKu视频批量下载的程序。东西虽然简单，但还挺实用的，拿出来分享给大家。版本：Python
- Django在执行python manage.py makemigrations的时候一切正常但是执行python manage.py mi
- css的流行导致了标签的流行，很直观，看起来很清爽。流行的一部分，还有很多种功能强大且美观的导航。。。1. Change.org2. N.D
- 每个矿工将从先前创建的交易池中获取交易.要跟踪已挖掘的消息数量，我们必须创建一个全局变量 :last_transaction_index =
- 1 概述C/C++和Java（以及大多数的主流编程语言）都有自己成熟的单元测试框架，前者如Check，后者如JUnit，但这些编程框架本质上
- 从基础的层面来讲，理解JavaScript的定时器是如何工作的是非常重要的。计时器的执行常常和我们的直观想象不同，那是因为JavaScrip
- 公用表表达式简介：公用表表达式 (CTE) 可以认为是在单个 SELECT、INSERT、UPDATE、DELETE 或 CREATE VI
- 本文介绍了如何在Linux下安装MySQL8.0，供大家参考，具体内容如下准备工作：mysql8.0 rpm文件测试工具（比如 idea的d
- 概念关键字：array，数据的组合（多个）存储到一个指定的容器中，用变量指向该容器，然后可以通过变量一次性得到该容器中的所有数据.数组定义语
- 1. 可选链从 v3.7 可用这是当你尝试访问嵌套数据时的一个痛点，嵌套数据越多，代码就会变得越繁琐。在下面的例子中，要访问address，
- 今天的第二个作品，哈哈哈哈，搞起来感觉还挺有意思的，不过代码里纸牌J，Q，K，A几个数字被我替换成了11，12，13，14......主要是
- 提问：如果想要通过爬虫程序去爬取”糗百“全站数据新闻数据的话，有几种实现方法？方法一：基于Scrapy框架中的Spider的递归爬去进行实现
- 今天在这里，不以设计师的身份，而从一个普通用户的角度和各位聊聊设计中蕴含的那份情感，关于情感再产品设计中的意义，聊聊设计中的那份源于“心”的
- 微信的小程序是一个很不错的体验，简单，上手快，这几天也在学习使用小程序，自己总结了三种用 Python 作为小程序后端的方式，供你参考。方法
- 本文实例为大家分享了vue简单的图书管理具体代码，供大家参考，具体内容如下<table class="table table
