最大乘法算式-第13届蓝桥杯选拔赛Python真题精选

[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第80讲。

最大乘法算式,本题是2022年3月13日举办的第13届蓝桥杯青少组Python编程选拔赛真题编程部分第5题。定一个正整数M和一个数字字符串,使用M个乘号插入到字符串中,请计算并输出最大乘积。

先来看看题目的要求吧。

一.题目说明

编程实现:

给定一个正整数 M(1 ≤ M ≤ 5)和一个只包含数字的字符串(5 < 字符串长度 ≤ 20)。使用M个乘号插入到字符串中,且两个乘号不能相邻,插入后生成一个乘法算式。找出一种使乘法算式数值最大的插入方式,并将结果输出。(乘号不能放在字符串的首尾位置)

如M = 2,字符串为123456,插入2个乘号。插入方式有:

1 * 2 * 3456 = 6912 , 1 * 23 * 456 = 10488 , 1 * 234 * 56 = 13104 , 1 * 2345 * 6 = 14070 ,12 * 3 * 456 = 16416 , 12 * 34 * 56 = 22848 , 12 * 345 * 6 = 24840 , 123 * 4 * 56 = 27552 ,123 * 45 * 6 = 33210,1234 * 5 * 6 = 37020,

其中乘法算式数值最大是第十种,为37020。

输入描述:

第一行输入一个正整数 M(1 ≤ M ≤ 5),表示乘号个数 

第二行输入一个只包含数字的字符串(5 < 字符串长度 ≤ 20),表示要插入M个乘号的字符串

输出描述:

输出一个整数,表示最大乘积数值

样例输入:sd2123456

样例输出:

37020

二.思路分析

这是一道经典的算法题,涉及的知识点包括循环、列表、字符串、枚举算法和动态规划等。

实际上,这是信息奥赛的一道原题,出自2000年NOIP提高组的第二题,原题是这样描述的:

今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。

活动中,主持人给所有参加活动的选手出了这样一道题目:设有一个长度为N的数字串,要求选手使用 K个乘号将它分成K + 1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。

虽然描述有所不同,但意思完全相同,题目还是非常有难度的。

通用的解决方案是使用动态规划,为了让大家更好的理解这个过程,超平老师准备使用3种算法来分析和解读,分别是:

  • 枚举算法

  • 递归算法

  • 动态规划算法

1. 枚举算法

对于编程中出现的大部分算法问题,都可以使用枚举算法来解决,只是效率相对不高。

以题目中的样例数据为例,在字符串"12345"中插入2个乘号,最基础的方法就是将所有的情况列举出来。

这是典型的组合问题,就是在5个位置中任选两个,我们可以使用数学中的”打枪法“,固定一个位置,变换另一个位置。

当第一个✖️在1和2之间时,第二个✖️有4个位置可选,如图:

图片

当第一个✖️在2和3之间时,第二个✖️有3个位置可选,如图:

图片

当第一个✖️在3和4之间时,第二个✖️有2个位置可选,如图:

图片

当第一个✖️在4和5之间时,第二个✖️有1个位置可选,如图:

图片

一共有10种组合,将这10种组合的乘积计算出来,就可以找到最大值37020了。

对于组合问题,在Python编程中,我们可以直接使用combinations()函数,5种组合中任选两个位置,可以使用如下代码:

combinations(range(5), 2)

就可以得到如下10种组合:

(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

对于每一种组合,对字符串"123456"进行截取运算,再转成整数,相乘即可。

比如对于组合(0,1),将字符串"123456"拆分成3段,分别为"1"、"2"、"3456",转成整数相乘如下:

1 * 2 * 3456 = 6912

按照同样的方式计算出所有组合的乘积,就可以找到最大值了。

2. 递归算法

枚举算法理解起来比较简单,但是随着字符串长度的增加,时间复杂度会急剧增加,算法效率大大降低,会出现超时情况。

接下来,我们使用递归算法来分析和解决,仍然以字符串s = "123456",M = 2为例进行分析和说明。

首先,我们需要给递归函数下一个明确的定义,这里有两个变量,一个是字符串的长度,一个是乘号的个数。

因此,可以定义f(i, j),表示字符串前i个数字使用j个乘号能够得到的最大乘积。

递归算法的核心思想就是找到f(n)和f(n - 1)之间的关系,也就是最后一步是如何演变过来的。

对于这里定义的f(i, j)来说,需要分析f(i ,j - 1)到f(i ,j)这一步是如何计算的,也就是第前6个数字串中已经有一个✖️了,第二个✖️放在哪儿,可以得到最大值的问题。

由于第二个✖️的位置有多种选择,因此,我们需要分情况讨论。

当第二个✖️在5和6之间时,它表示的是前5个数字串中插入一个✖️的情况,即f(5, 1),如图:

图片

当第二个✖️在4和5之间时,它表示的是前4个数字串中插入一个✖️的情况,即f(4, 1),如图:如图:

图片

当第二个✖️在3和4之间时,它表示的是前3个数字串中插入一个✖️的情况,即f(3, 1),如图:如图:

图片

当第二个✖️在2和3之间时,它表示的是前2个数字串中插入一个✖️的情况,即f(2, 1),如图:如图:

图片

发现这其中的规律了吗?

对于f(6, 2)而言,我们需要分别考虑如下4种情况:​​​​​​​

f(5, 1) * s[5: 6]f(4, 1) * s[4: 6]f(3, 1) * s[3 :6]f(2, 1) * s[2: 6]

然后从这几种情况中,找到最大值即可。

因此,对应f(i, j)而言,其推导公式可以描述如下:​​​​​​​

for k in range(1, i):  f(i, j) = max(f(i, j),f(k, j - 1) * int(s[k:i]))

递归是需要结束条件的,这里的结束条件有两个:

1). j = 0,即没有✖️时,就等于数字串本身,即f(i, j) = int(s[: i]);

2). i <= j时,没办法插入所有✖️,直接返回0。

普通的递归会存在大量的重复计算过程,因此,可以增加一个备忘录,将每一次的计算结果保存起来,从而提升算法效率。

3. 动态规划算法

如果说递归是自顶向下的推导过程,那么动态规划就是自底向上的推导过程,它们都有着共同的推导公式。

使用动态规划算法的要点有如下4个:

  • 定义DP数组

  • 初始化DP数组

  • 状态转移方程

  • 遍历顺序

1). 定义DP数组

根据前面的分析,DP数组可以描述如下:dp[i][j]表示字符串前i个数字中插入j个✖️的最大乘积。

这是一个典型的二维DP数组,对于字符串s = "123456",M = 2来说,我们要计算的是dp[6][2],如图:

图片

所谓的动态规划,其实就是逐步填充表格的过程。

2). 初始化DP数组

根据前面的分析,初始化有两种情况:

  • i <= j时,dp[i][j] = 0;

  • j = 0时,dp[i][j] = int(s[:i]);

对应的二维表格如图所示:

图片

实际上,可以将所有空白单元格中的值初始化为0,后续更新即可。

3). 状态转移方程

和递归算法中的推导公式是一样的,如下:​​​​​​​

for k in range(1, i):  dp(i, j) = max(dp(i, j),dp(k, j - 1) * int(s[k:i]))

这里就不再赘述了。

4). 遍历顺序

遍历顺序很重要,我们逐一来分析。

先从dp[2][1]开始,它表示前2个数字中插入一个✖️的最大乘积,根据上面的状态转移方程,k只能取1,因此:​​​​​​​

dp[2][1] = max(dp[2][1], dp[1][1] * int(s[1:2]))= max(0, 1 * 2)= 2

对应的dp表格如下:

图片

接着是dp[3][1],它表示前3个数字中插入一个✖️的最大乘积,k有两个取值,分别是1和2,需要根据dp[1][0]和dp[2][0]来计算,如下:​​​​​​​

dp[1][0] * int(s[1:3]) = 1 * 23 = 23dp[2][0] * int(s[2:3]) = 12 * 3 = 36

因此,dp[3][1] = 36,如图:

图片

再来计算dp[4][1],它表示前4个数字中插入一个✖️的最大乘积,k有3个取值,分别是1、2和3,需要根据dp[1][0]、dp[2][0]和dp[3][0]来计算,如下:​​​​​​​

dp[1][0] * int(s[1:4]) = 1 * 234 = 234dp[2][0] * int(s[2:4]) = 12 * 34 = 408dp[3][0] * int(s[3:4]) = 12 * 34 = 492

因此,dp[4][1] = 492,如图:

图片

依此类推,可以分别计算dp[5][1]和dp[6][1],结果如下:

图片

同理,计算第3列中的所有单元格,得到最终的二维表格数据,如下:

图片

通过上面的分析过程,相信你已经明白了,这一次,我们要采取先遍历列再变量行的策略,即从左到右,从上到下。

思路有了,接下来,我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析,我们使用三种方法来编写程序:

  • 枚举算法

  • 递归算法

  • 动态规划

1. 枚举算法

根据前面的思路分析,我们使用combinations()函数获取所有组合,逐个计算乘积,从而获取最大值,代码如下:

图片

代码比较长,说明4点:

1). 首先使用组合函数,获取所有组合,然后对字符串截取,将截取的数字串保存到临时列表temp中,如['1', '2', '3456'];

2). 为方便计算数字串的乘积,定义了一个f()函数,它将temp列表中的数字串依次取出,转成整型,累乘得到成绩,保存到res列表中;

3). res列表保存的是所有乘法算式的乘积,最后使用max()函数获取最大值并输出;

4). 在拆分字符串的时候,需要注意不断地更新和计算起点start和end,同时不要忘了最后一个乘号✖️后面的数字串。

2. 递归算法

使用带备忘录的递归算法,编写代码如下:

图片

代码不算少,说明两点:

1). 为了方便,这里将备忘录列表作为递归的参数进行传递,真正的关键还是i和j这两个参数;

2). 在循环取值的时候,k是从1开始的,确保函数能满足结束条件;

2. 动态规划

根据前面的思路分析,使用动态规划算法,编写代码如下:

图片

代码相对较少,强调两点:

1). 在遍历二维列表的时候,我们始终要遵循i表示行,j表示列的原则,如果要先遍历列,那就先写j,再嵌套i;

2). 对于每一列,起点是从 i + 1开始的,请参考填充DP表格的过程。

至此,整个程序就全部完成了,你可以输入不同的数据来测试效果啦。

四.总结与思考

本题代码在12 ~ 20行左右,涉及到的知识点包括:

  • 循环语句;

  • 列表操作;

  • 枚举算法;

  • 组合函数;

  • 递归算法;

  • 动态规划算法;

作为本次测评的最后一题,难度较大。关键点有两个,一是使用组合函数快速解决问题,二是使用递归思维深入分析计算最大乘积的过程,找到其中的规律,然后选择相应的算法编程实现。

对于本题而言,最基础的方法就是枚举算法,最高效的方法当属动态规划,而递归则是一种讨巧的实现方法。

枚举算法简单粗暴,如果一时半会找不到其他的解决方案,建议可以从枚举算法着手,先确保能解决问题或部分解决问题。

在使用枚举算法解决问题的过程中,说不定灵感就来了,想到更好的方法。实际上,大部分算法都是在枚举的基础上进行优化的。

很多同学都喜欢动态规划,从而忽略了递归算法,我倒是提倡大家多尝试使用递归思维来分析解决问题。

从本质上讲,动态规划和递归算法的核心是一样,但是递归算法的编写难度要小于动态规划,往往会给你带来意想不到的效果。

最后说说动态规划,动态规划的分析过程就是填充表格的过程,所以在解决动态规划问题时,一定要踏踏实实的逐步分析并填充表格,最终的代码往往是比较简单的。

你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香😄

需要源码的,可以移步至“超平的编程课”gzh。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/689667.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

动态规划求多段图的最短路径

一、基本思想 动态规划法将待求解问题分解成若干个相互重叠的子问题&#xff0c;每个子问题相互关联&#xff1b;动态规划法与分治法的区别就在于分治法的子问题相互不关联&#xff0c;而动态规划法的子问题是相互关联的&#xff0c;且有重叠的部分。 二、算法分析 动态规划…

细说NLP中的Embedding层

文章目录 前言一、为什么要引入Embedding层二、Embedding层是怎么发挥作用的&#xff1f;三、感受Embedding的强大四、为什么理解Embedding的底层原理&#xff1f;总结 前言 在构建高效的自然语言处理模型时&#xff0c;Embedding层是不可或缺的组成部分。它不仅可以帮助我们捕…

【免费Web系列】大家好 ,今天是Web课程的第十七天点赞收藏关注,持续更新作品 !

这是Web第一天的课程大家可以传送过去学习 http://t.csdnimg.cn/K547r SpingBoot原理 在前面十多天的课程当中&#xff0c;我们学习的都是web开发的技术使用&#xff0c;都是面向应用层面的&#xff0c;我们学会了怎么样去用。而我们今天所要学习的是web后端开发的最后一个篇…

通过影刀RPA,创建定时任务,自动获取图片验证码登录平台;

1.下载下载影刀客户端-影刀RPA - 影刀官网 2.安装&#xff0c;登录 3.应用创建->PC自动化应用 4.按照流程-创建【可双击或拖动】 5.保存 6.右击【创建的应用】->发版 7.选择触发器->【定时触发器】 根据提示配置 8.完成&#xff0c;每天平台会自动打开&#xff1b;…

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《基于日间-日内不确定集的中长期电源扩展规划》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…

TCP攻击是怎么实现的,如何防御?

TCP&#xff08;Transmission Control Protocol&#xff09;是互联网协议族中的重要组成部分&#xff0c;用于在不可靠的网络上提供可靠的数据传输服务。然而&#xff0c;TCP协议的一些特性也使其成为攻击者的目标&#xff0c;尤其是DDoS&#xff08;Distributed Denial of Ser…

正确挑选百兆超薄款工业级网络/脉冲变压器(网络隔离滤波器)

Hqst华强盛&#xff08;石门盈盛电子&#xff09;导读&#xff1a;工业级百兆超薄款网络变压器的生产要特殊的超薄磁芯配正确线径的铜线&#xff0c;使用符合相应防潮标准的凝固胶水。 一 ̖ 首先来看下商业级的超薄款的百兆网络变压器&#xff1a; 商业级&#xff08;消费级&…

基于Zero-shot实现LLM信息抽取

基于Zero-shot方式实现LLM信息抽取 在当今这个信息爆炸的时代&#xff0c;从海量的文本数据中高效地抽取关键信息显得尤为重要。随着自然语言处理&#xff08;NLP&#xff09;技术的不断进步&#xff0c;信息抽取任务也迎来了新的突破。近年来&#xff0c;基于Zero-shot&#x…

Linux CGroup资源限制(概念限制进程CPU使用)

Linux CGroup资源限制&#xff08;详解&#xff09; 最近客户认为我们程序占用cpu过高&#xff0c;希望我们限制&#xff0c;排查之后发现是因为程序频繁gc导致&#xff0c;为了精细化、灵活的的限制&#xff0c;想到了使用Linux CGroup。 0 前置知识 ①概念及作用 官网&#…

给Mac添加右键菜单「使用 VSCode 打开」的方法

用 macOS 系统的苹果电脑用户都知道&#xff0c;macOS 某些地方确实没 Windows 方便&#xff0c;比如右键菜单&#xff0c;没有复制粘贴之类的菜单&#xff0c;刚开始还有点使用不方便&#xff0c;今天我介绍两种方法来实现一个用右键通过 VSCode 打开文件和文件夹的方法&#…

Redis实战——创建账户及连接数据库

一、创建一个新账户 要创建一个带有免费数据库的新账户&#xff0c;请按照以下步骤操作&#xff1a; 前往 Redis Cloud 的注册页面。有两种开始使用 Redis Cloud 的选项&#xff1a; 在表单中输入您的信息&#xff0c;然后选择“Get Started”&#xff08;开始使用&#xff…

Golang使用讯飞星火AI接口

一、API申请 https://www.bilibili.com/video/BV1Yw411m7Rs/?spm_id_from333.337.search-card.all.click&vd_source707ec8983cc32e6e065d5496a7f79ee6 注册申请&#xff0c;需要在此页面获取appid、apisecret、apikey https://www.xfyun.cn/ https://console.xfyun.cn/ser…

隐式链接DLL

本文仅供学习交流&#xff0c;严禁用于商业用途&#xff0c;如本文涉及侵权请及时联系本人将于及时删除 【例9.5】创建的基于MFC对话框的应用程序MFCImLink2&#xff0c;隐式链接例9.2创建的MFCLibrary2.dll&#xff0c;使用其中的导出函数求正方形的面积。 (1) 使用MFC应用程…

PS的stable diffusion插件安装指南

PS的stable diffusion插件安装指南 1.首先要安装stable diffusion&#xff0c;具体安装方法&#xff0c;参考https://blog.csdn.net/sheji888/article/details/139196688 stable diffusion要求要启用API功能 2.安装ps2023以上版本&#xff0c;低于这个版本不能使用stable diff…

尝试使用blazor(一)吐槽blazor,未开始之前,先吐为敬

为什么要写一点关于blazor的文章呢?其实是没什么人看的&#xff0c;我知道blazor目前在国内使用的人数&#xff0c;恐怕一辆大巴车都坐不满。非常冷门&#xff0c;我刚用blazor遇到问题&#xff0c;花钱找人解决&#xff0c;找了国内几个著名的平台&#xff0c;几乎没人会blaz…

关于怎么用Cubemx生成的USBHID设备实现读取一体的鼠标键盘设备(改进版)

主要最近做了一个要用STM32实现读取鼠标键盘一体的那种USB设备&#xff0c;STM32的界面上要和电脑一样的能通过这个USB接口实现鼠标移动&#xff0c;键盘的按键。然后我就很自然的去参考了正点原子的例程&#xff0c;可是找了一圈&#xff0c;发现正点原子好像用的库函数&#…

短剧看剧系统投流版系统搭建,前端uni-app

目录 前言&#xff1a; 一、短剧看剧系统常规款短剧系统和投流版的区别&#xff1f; 二、后端体系 1.管理端&#xff1a; 2.代理投流端 三、功能区别 总结&#xff1a; 前言&#xff1a; 23年上半年共上新微短剧481部&#xff0c;相较于2022年全年上新的454部&#xff0…

使用el-tree封装一个权限管理的小功能

使用el-tree封装一个权限管理的小功能 使用el-tree封装权限管理, 选中人员并且在右侧回显, 此组件用到了递归, 我只是将需要显示的数据进行了动态传递, 其他数据小伙伴可以自己封装 父组件 <template><div><authorityManage ref"authorityManage" :…

Vuepress 2从0-1保姆级进阶教程——标准化流程

Vuepress 2 专栏目录 1. 入门阶段 Vuepress 2从0-1保姆级入门教程——环境配置篇Vuepress 2从0-1保姆级入门教程——安装流程篇Vuepress 2从0-1保姆级入门教程——文档配置篇Vuepress 2从0-1保姆级入门教程——范例与部署 2.进阶阶段 Vuepress 2从0-1保姆级进阶教程——全文搜索…

学习笔记——路由网络基础——路由概述

一、路由概述 1、路由定义与作用 路由(routing)是指导报文转发路径信息&#xff0c;通过路由可以确认转发IP报文的路径。 路由&#xff1a;是指路由器从一个接口上收到数据包&#xff0c;根据数据包的目的地址进行定向并转发到另一个接口的过程。 路由(routing)的定义是指分…