Python实现印章代码的算法解析

目录
  • 1.题目
  • 2.代码
  • 3.代码解析

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)

以上就是Python印章代码实现算法解析的详细内容，更多关于Python印章代码算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 用Python实现给Word文档盖章

    用Python实现给Word文档盖章

    目录 模块分解 设置加粗 功能块练习 知识归纳与总结 总结 目标文件夹内有多份 Word 文件 ——[xxx涨薪通告.docx],我们需要在这些文档的末尾处添加公司的电子章与公司名称. 这次的任务困难吗?手动操作起来其实很简单,无非就是先打开一个文档,接着在结尾处添加文字盖章:并且插入电子章图片,然后另起一行,添加公司名称闪光科技金融公司(Shining Fintech Company),将公司名称的字号设置为四号,字体加粗,右对齐:完成这些操作后,复制这些文字和图片,最后保存文档. 实现代码:

  • Python实现七个基本算法的实例代码

    1.顺序查找 当数据存储在诸如列表的集合中时,我们说这些数据具有线性或顺序关系. 每个数据元素都存储在相对于其他数据元素的位置. 由于这些索引值是有序的,我们可以按顺序访问它们. 这个过程产实现的搜索即为顺序查找. 顺序查找原理剖析:从列表中的第一个元素开始,我们按照基本的顺序排序,简单地从一个元素移动到另一个元素,直到找到我们正在寻找的元素或遍历完整个列表.如果我们遍历完整个列表,则说明正在搜索的元素不存在. 代码实现:该函数需要一个列表和我们正在寻找的元素作为参数,并返回一个是否存在的布尔值

  • Python Opencv实战之印章提取的实现

    Python Opencv实战之印章提取的实现

    目录 前言 源码展示 效果展示 前言 这期分享的是使用opencv提取印章,很多时候我们需要电子版的章,所以今天就带大家使用代码提取出来! Photoshop虽然强大,但是奈何小编不会使啊,昨天就有一个小伙伴问我能不能帮忙,这不? PS虽然我不会,但是我会写代码呀!这可难不倒我!安排安排~ (特别提醒:所有爱好设计和喜欢做图的小伙伴们,切记千万不要帮着老板或者朋友PS伪造公章,刑法第280条特别指出,伪造证件印章,是可以追究刑事责任的,违法的事情不要做哦.) 源码展示 import cv2 im

  • Python实现印章代码的算法解析

    Python实现印章代码的算法解析

    目录 1.题目 2.代码 3.代码解析 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-

  • TF-IDF算法解析与Python实现方法详解

    TF-IDF算法解析与Python实现方法详解

    TF-IDF(term frequency–inverse document frequency)是一种用于信息检索(information retrieval)与文本挖掘(text mining)的常用加权技术.比较容易理解的一个应用场景是当我们手头有一些文章时,我们希望计算机能够自动地进行关键词提取.而TF-IDF就是可以帮我们完成这项任务的一种统计方法.它能够用于评估一个词语对于一个文集或一个语料库中的其中一份文档的重要程度. 在一份给定的文件里,词频 (term frequency, T

  • Python利用正则表达式实现计算器算法思路解析

    (1)不使用eval()等系统自带的计算方法 (2)实现四则混合运算.括号优先级解析 思路: 1.字符串预处理,将所有空格去除 2.判断是否存在括号运算,若存在进行第3步,若不存在则直接进入第4步 3.利用正则表达式获取最底层括号内的四则运算表达式 4.将四则运算表达式进行预处理:表达式开头有负数时,在表达式前加上一个0 5.利用re.split().re.findall()方法,通过加减符号,对四则运算进行拆分为乘除运算式和数字,并保留对应的位置下标. 6.利用re.split().re.fi

  • Python+OpenCV实现分水岭分割算法的示例代码

    Python+OpenCV实现分水岭分割算法的示例代码

    目录 前言 1.使用分水岭算法进行分割 2.Watershed与random walker分割对比 前言 分水岭算法是用于分割的经典算法,在提取图像中粘连或重叠的对象时特别有用,例如下图中的硬币. 使用传统的图像处理方法,如阈值和轮廓检测,我们将无法从图像中提取每一个硬币,但通过利用分水岭算法,我们能够检测和提取每一个硬币. 在使用分水岭算法时,我们必须从用户定义的标记开始.这些标记可以通过点击手动定义,或者我们可以使用阈值和/或形态学操作等方法自动或启发式定义它们. 基于这些标记,分水岭算法将

  • Python内存管理方式和垃圾回收算法解析

    概要 在列表,元组,实例,类,字典和函数中存在循环引用问题.有 __del__ 方法的实例会以健全的方式被处理.给新类型添加GC支持是很容易的.支持GC的Python与常规的Python是二进制兼容的. 分代式回收能运行工作(目前是三个分代).由 pybench 实测的结果是大约有百分之四的开销.实际上所有的扩展模块都应该依然如故地正常工作(我不得不修改了标准发行版中的 new 和 cPickle 模块).一个叫做 gc 的新模块马上就可以用来调试回收器和设置调试选项. 回收器应该是跨平台可移植

  • python实现协同过滤推荐算法完整代码示例

    python实现协同过滤推荐算法完整代码示例

    测试数据 http://grouplens.org/datasets/movielens/ 协同过滤推荐算法主要分为: 1.基于用户.根据相邻用户,预测当前用户没有偏好的未涉及物品,计算得到一个排序的物品列表进行推荐 2.基于物品.如喜欢物品A的用户都喜欢物品C,那么可以知道物品A与物品C的相似度很高,而用户C喜欢物品A,那么可以推断出用户C也可能喜欢物品C. 不同的数据.不同的程序猿写出的协同过滤推荐算法不同,但其核心是一致的: 1.收集用户的偏好 1)不同行为分组 2)不同分组进行加权计算用

  • Python编程二分法实现冒泡算法+快速排序代码示例

    本文分享的实例主要是Python编程二分法实现冒泡算法+快速排序,具体如下. 冒泡算法: #-*- coding: UTF-8 -*- #冒泡排序 def func(lt): if type(lt).__name__ !='list' and type(lt).__name__ !='tuple': return if type(lt).__name__ == 'tuple': return list(lt) for i in range(1,len(lt)-1): for j in range

  • Java语言字典序排序算法解析及代码示例

    字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

  • Python 25行代码实现的RSA算法详解

    本文实例讲述了Python 25行代码实现的RSA算法.分享给大家供大家参考,具体如下: 网络上很多关于RSA算法的原理介绍,但是翻来翻去就是没有一个靠谱的算法实现,即使有代码介绍,也都是直接调用JDK或者Python代码包中的API实现,或者即使有代码也都写得特别烂.无形中让人感觉RSA加密算法竟然这么高深,然后就看不下去了.还有我发现对于"大整数的幂次乘方取模"竟然采用直接计算的幂次的值,再取模,类似于(2 ^ 1024) ^ (2 ^ 1024),这样的计算就直接去计算了,我不知

  • Python异常对代码运行性能的影响实例解析

    Python异常对代码运行性能的影响实例解析

    前言 Python的异常处理能力非常强大,但是用不好也会带来负面的影响.我平时写程序的过程中也喜欢使用异常,虽然采取防御性的方式编码会更好,但是交给异常处理会起到偷懒作用.偶尔会想想异常处理会对性能造成多大的影响,于是今天就试着测试了一下. Python异常(谷歌开源风格指南) tip: 允许使用异常, 但必须小心. 定义: 异常是一种跳出代码块的正常控制流来处理错误或者其它异常条件的方式. 优点: 正常操作代码的控制流不会和错误处理代码混在一起. 当某种条件发生时, 它也允许控制流跳过多个框架

随机推荐