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
投稿
猜你喜欢
- 最近JETBRAINS发布了目前最受欢迎的python-web开发框架,可以看到最受欢迎的还是Django和Flask,那么本文就对上榜的1
- 研究网页编码很长时间了,因为最近要设计一个友情链接检测的VBS脚本,而与你链接的人的页面很可能是各种编码,以前采取的方法是:如果用GB231
- 我们以MNIST手写数字识别为例import numpy as npfrom keras.datasets import mnistfrom
- 如何做一个全面的探测器? 我们也可以做一个功能类似的探测器,见下:<Script lan
- 这里列出了javascript 中的document.execCommand() 的各种参数说明:2D-Position 允许通过
- 本文实例讲述了Python使用Selenium模块模拟浏览器抓取斗鱼直播间信息。分享给大家供大家参考,具体如下:import timefro
- 本文介绍了ORACLE客户端连服务器的注意事项:1. 通过SQL*NET协议,ORACLE客户端连服务器时一般需要配置sqlnet.ora和
- 本文实例讲述了Python实现PS滤镜特效之扇形变换效果。分享给大家供大家参考,具体如下:这里用 Python 实现 PS 滤镜中的一种几何
- 主题众所周知,django.forms极其强大,不少的框架也借鉴了这个模式,如Scrapy。在表单验证时,django.forms是一绝,也
- 简介程序中的数在计算机内存中都是以二进制的形式存在的,位运算就是直接对整数在内存中对应的二进制位进行操作,一般是将数字化为二进制数后进行操作
- 这篇文章主要介绍了windows环境中利用celery实现简单任务队列过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定
- 写在之前我们都知道 Python 中内置了许多标准的数据结构,比如列表,元组,字典等。与此同时标准库还提供了一些额外的数据结构,我们可以基于
- 梯度PyTorch的数据结构是tensor,它有个属性叫做requires_grad,设置为True以后,就开始track在其上的所有操作,
- 在使用DB2以来,碰到了几次出现提示SQL1032N错误,每次出错时出错信息大概如下:11/21/2004 22:15:33 0 0 SQL
- 本文实例讲述了python查找指定具有相同内容文件的方法。分享给大家供大家参考。具体如下:python代码用于查找指定具有相同内容的文件,可
- 一、背景(正)地理编码指的是:将地理位置名称转换成经纬度;逆地理编码指的是:将经纬度转换成地理位置信息,如地名、所在的省份或城市等百度地图提
- 我们在使用ASP 内置的ADO组件进行数据库编程时,通常是在脚本的开头打开一个连接,并在脚本的最后关闭它,但是就较大脚本而言,在多
- 目录项目地址功能概述效果图模块安装提交环境为python3.7 pyqt5==5.13.2 win10 一切正常!说一说大概的思路吧项目地址
- Data URIData URI是由RFC 2397定义的一种把小文件直接嵌入文档的方案。通过如下语法就可以把小文件变成指定编码直接嵌入到页
- 1、使用基础Python代码来读写和处理CSV文件import sys#使用基础Python代码来读写和处理CSV文件input_file