使用动态规划解决分钱方案-2023年全国青少年信息素养大赛Python复赛真题精选

本文主要是介绍使用动态规划解决分钱方案-2023年全国青少年信息素养大赛Python复赛真题精选,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 [导读]:超平老师计划推出《全国青少年信息素养大赛Python编程真题解析》50讲,这是超平老师解读Python编程挑战赛真题系列的第14讲。

全国青少年信息素养大赛(原全国青少年电子信息智能创新大赛)是“世界机器人大会青少年机器人设计与信息素养大赛”赛事之一,由中国电子学会主办,包含很多赛项,大赛自2013年举办,已连续成功举办八届,已正式入围“2022-2025学年面向中小学生的全国性竞赛活动名单”。 

大赛旨在激发广大青少年的科学兴趣和想象力,培养钻研探究、创新创造的科学精神和实践能力,促进青少年科技创新活动的广泛开展,发现和培养一批具有科研潜质和创新精神的青少年科技创新后备人才。

大赛主要竞赛类别包括电子科技、智能机器人、软件编程三类,全国青少年Python编程挑战赛就属于其中的软件编程类。

一.赛事说明

2023年(第9届)Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛,复赛是地方选拔赛,总决赛是全国各地选拔的精英汇聚在一起进行PK。

本届Python挑战赛是在线上举行,参赛选手登录大赛官网在指定页面完成答题并提交答案。评定成绩的依据是同时考虑得分和用时两个方面,首先是得分高者名次靠前,如果得分一样,则用时少者名次靠前。

2023年全国青少年Python编程挑战赛华北赛区(北京)初中组复赛于2023年7月15日正式举行。一共有6道题,全是编程题,考试时间是90分钟。

今天超平老师分享的是第5题,分钱方案。

二.题目说明

题目背景:

有n个人,他们需要分配m元钱 (m >= n),每个人至少分到1元钱,且每个人分到的钱数必须是整数。

请问有多少种分配方案?

输入描述:

输入一行两个正整数n, m,用空格间隔。

输出描述:

输出分配方案数。

样例1:

输入:

5  10

输出:

126

三.思路分析

从本题的描述来看,这是一个排列组合问题,但并不是简单地从m个元素中直接选取n的简单组合问题。

我们可以换个说法,这相当于将m个球放入n个盒子中,每个盒子至少有一个球的问题。

图片

针对这类问题,我们首先能想到的就是枚举算法,但是这里的m和n不是固定的数字,无法确定循环嵌套的层数,所以枚举算法是行不通的。

对于不确定次数的枚举算法,可以尝试使用递归算法来解决。递归的关键是要找到推导公式和出口条件,重点是推导公式,也就是第n项和第n-1项之间的关系。

我们使用f(m, n)来表示m个球放到n个盒子里(每个盒子里至少一个小球)的方案数量,然后来分析第n个盒子和前n - 1和盒子之间的关系。

  • 如果第n个盒子放1个小球,那么前面n - 1个盒子要存放 m - 1个小球,即f(m - 1, n -1);

  • 如果第n个盒子放2个小球,那么前面n - 1个盒子要存放 m - 2个小球,即f(m - 2, n -1);

  • 如果第n个盒子放3个小球,那么前面n - 3个盒子要存放 m - 1个小球,即f(m - 3, n -1);

  • ......

  • 如果第n个盒子放i个小球,那么前面n - i个盒子要存放 m - i个小球,即f(m - i, n -1);

请你思考一下,第n个盒子最多可以放几个小球呢?

由于要确保每个盒子至少1个小球,所以第n个盒子最少放1个小球,最多放m - n + 1个小球。因为前面的每个盒子装1个小球,一共要装 n - 1个小球,然后用总数m减去 n - 1,就是 m - n + 1个小球了。

再将所有的方案加起来就可以得到总的方案数量了,即:

图片

那么递归的出口条件呢,这个比较简单,就是只有一个人的时候,即n = 1,此时只有一种方案。

递归算法理解起来相对要简单一些,代码也比较简洁,但是它有一个严重的问题,就是当m和n比较大的时候,程序运行时间比较长,有可能会超出题目的时间要求。

所以,我们还需要优化我们的程序,大多数情况下,能用递归解决的问题,可以使用动态规划(DP)算法来解决,这才是本题最优的解决方案,关于动态规划的思路分析,我们稍后再讲。

接下来,我们进入具体的编程实现环节。

四.编程实现

根据上面的思路分析,我们使用两种方式来编写代码:

  • 递归算法

  • 动态规划

1.递归算法

根据前面的思路分析和递归算法的实现方式,需要先定义好递归函数,代码如下:

图片

这里增加了一个m < n的判断,此时无法分钱,所以返回0。

有了该函数,主代码就比较简单了,如下:

图片

简单说明三点:

1). split函数的作用是通过指定分隔符对字符串进行切片,并返回分割后的字符串列表,默认的分隔符是空格;

2). 使用split函数切片后得到的字符串,需要转换成整数,所以这里使用了int函数;

3). 这里使用了列表推导式,这是一个非常有用的技巧,一定要熟练掌握。

递归的好处就是理解起来简单,缺点就是当递归层数较多时,执行时间太长,考试时有可能出现超时的情况。

2.动态规划

动态规划,英文Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

图片

在递归算法中,我们是从后往前,即从n到n - 1、从n - 1到n - 2...,直到1结束。而动态规划中每一个状态一定是由上一个状态推导出来的,它是从前到后的。

对于动态规划,通常可以分成如下5个步骤:

  • 确定dp数组以及下标的含义

  • 确定递推公式

  • dp数组如何初始化

  • 确定遍历顺序

  • 举例推导dp数组

首先dp数组,在本题中,dp是一个二维数组,dp[i][j]表示将j个小球放到i个盒子里的方案数量。

只看这个二维数组的定义,可能会有点懵,还是看图吧:

图片

时刻牢记,dp[i][j]表示将j个小球放到i个盒子里的方案数量,很显然,在如下3种情况下,方案数量都为0:

1). i = 0时,表示没有盒子,方案数为0;

2). j = 0时,表示小球数量为0,方案数为0;

3). i > j 时,不能满足每个盒子都装一个小球,方案数为0;

当 i = 1时,也就是只有一个盒子时,方案数量为1,如图:

图片

这里的难点是确定递推公式,根据前面递归算法中的思路分析,有如下公式:

图片

其中,i - 1表示是上一行,j的值从i - 1开始直到 j - 1结束,这就意味着dp[i][j]等于上一行从第i - 1列到第j-1列所有格子的总和。

按照这个思路,可以将上面的表格填写完整,如图:

图片

为了你更好地理解,我举例说明如下:

图片

聪明的你也许已经发现了,上面的递推公式可以简化为:

图片

此处有点烧脑,你要好好理解一下,既然dp[i][j]等于上一行左边所有列的和(由于最左边的都为0,可以直接累加进来),那么dp[i][j - 1]就等于它上一行左边所有列的和(不包括第j - 1列),所以二者相加就刚好等于dp[i][j]了。

根据上面的分析,初始化也就比较简单了,首先初始化一个n + 1行m + 1列的二维列表,每一项元素的值都设置为0,然后将第2行(下标为1)的值设置为1。

从第3行(下标为2)开始,使用递推公式计算出每一个列表项的值即可,遍历顺序按照先行后列即可。

完整的代码如图所示:

图片

输入数据进行测试,即使n和m的值都非常大,也可以很快地输出结果,非常完美,这才是解决本题的最佳方案。

五.总结与思考

本题难度较大,考查的知识点主要包括:

  • 处理输入数据;

  • 列表推导式

  • 二维列表;

  • 递归算法;

  • 动态规划;

作为初中组复赛倒数第二题,本题还是非常有难度的,已经上升到常用算法层面了,而且还是有点难度的动态规划算法。

如果你想从比赛中脱颖而出,算法学习是必不可少的。相对来说,递归是一种简单的算法,但是递归也存在弊端,就是当递归的层数不断增加之后,程序的执行时间会急剧增加。

大部分递归算法问题,都可以使用动态规划来解决,对于动态规划算法来说,其核心在于dp数组的理解及递推公式的确定,这个需要经过大量的练习才能熟练掌握。

给你留一个小小的思考题,根据动态规划算法中的递推公式,你能否将递归算法中的代码进行简化呢?

你还有什么巧妙的解决方案吗,欢迎和超平老师交流。

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

更多教程可以移步至“超平的编程课”gzh。

这篇关于使用动态规划解决分钱方案-2023年全国青少年信息素养大赛Python复赛真题精选的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/306597

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

高效+灵活,万博智云全球发布AWS无代理跨云容灾方案!

摘要 近日,万博智云推出了基于AWS的无代理跨云容灾解决方案,并与拉丁美洲,中东,亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础,将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合,为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日,万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频,介绍了

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表