什么网站专门做境外当地游,公司网站怎么选,秘密入口3秒自动进入,wordpress默认编辑器[导读]#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后#xff0c;受到了广大老师和家长的好评#xff0c;非常感谢各位的认可和厚爱。作为回馈#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》#xff0c;这是解读系列的第52讲。
病毒繁殖#xf…
[导读]超平老师的Scratch蓝桥杯真题解读系列在推出之后受到了广大老师和家长的好评非常感谢各位的认可和厚爱。作为回馈超平老师计划推出《Python蓝桥杯真题解析100讲》这是解读系列的第52讲。
病毒繁殖本题是2021年3月27日举办的第12届蓝桥杯青少组Python编程选拔赛真题题目要求编程求解在第N分钟时病毒粒子的总数量。
先来看看题目的要求吧。
一.题目说明
提示信息
某种病毒具有很强的繁殖能力从病毒粒子出生后的第5分钟开始每分钟可以复制出一个新的病毒粒子。新出生的病毒粒子从第5分钟开始也可以每分钟复制一个新的病毒粒子。
举例来说第1分钟时有一个病毒粒子此病毒粒子从第5分钟开始复制新的病毒粒子因此第5分钟时的病毒数量为2个第6分钟时又复制出新的病毒粒子因此第6分钟的病毒数量为3个以此类推第7分钟时病毒粒子数为4第8分钟时病毒粒子数为5第9分钟时第5分钟复制出的病毒粒子开始复制新的病毒粒子因此第9分钟时的病毒总数为7第10分钟时第6分钟复制出的病毒粒子开始复制新的病毒粒子因此第10分钟时的病毒粒子总数为10。
编程实现
计算病毒粒子总数已知第一分钟时出生了一个病毒粒子假设所有病毒粒子不会自动死亡请计算第N分钟时的病毒粒子总数。
例如前10分钟病毒粒子的总数分别为1,1,1,1,2,3,4,5,7,10。
输入描述
输入正整数 N(0 N ≤ 60)表示时间
输出描述
输出第N分钟时病毒粒子的总数
样例输入
6
样例输出
3
二.思路分析
这是一道算法题考查的算法有递归和递推涉及的知识点包括循环、条件、列表和函数等。
看到这个题目所描述的场景你会想到什么呢
对了就是斐波那契数列也叫兔子数列。13世纪意大利数学家斐波那契的《算盘书》中记载了典型的兔子产仔问题。 其大意如下
如果一对两个月大的兔子以后每一个月都可以生一对小兔子而一对新生的兔子出生两个月后才可以生小兔子。也就是说1月份出生3月份才可产仔。那么假定一年内没有产生兔子死亡事件那么1年后共有多少对兔子呢
斐波那契数列是一个非常经典的算法编程题目有多种实现方法比如递归和递推等。
不管是使用哪种算法其关键在于要确定递推公式比如斐波那契数列的递推公式是这样的 那本题描述的病毒繁殖递推公式又是怎样呢
对于这类问题我们用f(n)来表示问题的解通常有如下两种推导方式
1). 正向推导利用已知数列找规律
2). 逆向推导分析f(n)和f(n-1)之间的关系
我们先用正向推导方法题目给出了一个例子前10分钟病毒粒子的总数分别为
1,1,1,1,2,3,4,5,7,10
由于新出生的病毒粒子从第5分钟开始复制说明前面4分钟的病毒例子都只有1个即
f(1) f(2) f(3) f(4) 1
第5分钟开始复制一个例子于是就得到了两个病毒粒子
f(5) f(4) f(1) 1 1 2
第6分钟呢它是在第5分钟的基础上又增加了一个增加的一个是第1个病毒粒子复制出来的
f(6) f(5) f(2) 2 1 3
以此类推可以分别计算出第7、8、9分钟的病毒数量
f(7) f(6) f(3) 3 1 4f(8) f(7) f(4) 4 1 5
到第9分钟时第5分钟复制出来的第2个病毒粒子也开始复制了也就是说有两个病毒粒子在复制要增加2个其病毒数量计算如下
f(9) f(8) f(5) 5 2 7
第10分钟时病毒数量计算如下
f(10) f(9) f(6) 7 3 10
因此我们可以得到如下递推公式 接下来我们使用逆序推导的方式此时我们只需要考虑f(n)和f(n-1)之间的关系。
为了方便描述我们引入两个概念存量和增量。 所谓存量是指原来就有的比如要计算第n分钟的病毒数量f(n)存量就是第n-1分钟的病毒数量f(n - 1)。
所谓增量是指新增的部分对于本题而言就是新复制出来的病毒那么新复制出来多少呢
此时我们只需要明白一点新出生的病毒粒子从第5分钟才开始复制可以理解为病毒有4分钟的生长期。
也就是说在第n分钟时只有第n - 4分钟的那些病毒粒子才可以复制病毒粒子所以增量就是f(n - 4)。
两者相加就是第n分钟的病毒粒子数如下
f(n) f(n - 1) f(n - 4)
同时我们还要考虑边界情况要确保n - 1和 n - 4都大于0所以n 5时需要单独处理。可以理解为前4分钟病毒粒子还不具备繁殖能力不能使用这个推导公式来推导。
有了推导公式问题就变简单了接下来我们就进入具体的编程实现环节。
三.编程实现
根据上面的思路分析我们使用两种方法来编写程序 递归算法 递推算法
1. 递归算法
根据前面的思路分析先定义递归函数然后调用即可代码如下 代码比较简单说明两点
1). 为了完整性这里增加了 0的判断实际上本题中的N是大于0的所以不写也是可以的
2). return不仅可以返回结果还可以直接结束程序所以只需要使用if语句就行代码更简洁。
但是考虑到N的范围是0~60随着N的增加时间复杂度急剧增加所以会存在超时情况。
可以考虑使用带备忘录的递归算法代码改进如下 说明如下
1). 需要借助一个列表用来保存f(n)的值其长度为n1默认值都是0
2). 在定义函数的时候尽量不要依赖外部变量所以这里将memo列表作为参数进行传递。
2. 递推算法
递归问题通常都可以改用递推算法来实现。为了方便我们可以定义一个列表来保存每一分钟的病毒数量。
对应的代码如下 代码不多强调2点
1). 为了方便这里借用了列表arr下标i对应的就是第i分钟所以第一项表示第0分钟设置为0
2). 需要分情况讨论当n 5时只需将第1~n项都设置为1当n 5时先将第1~4项设置为1然后再利用递推公式计算第5~n项。
当输入n 10的时候arr数组如下 因此我们只需要输出arr[10]即可。
至此整个程序就全部完成了你也可以输入不同的数字来测试效果。
四.总结与思考
本题代码在12行左右涉及到的知识点包括 循环语句主要for...in循环 条件语句包括单分支和双分支 列表的使用 函数的定义及使用 递归算法 递归算法
本题作为stema测评的最后一题难度不小。这里的关键点在于如何找到推导公式并选择相应的算法来实现。
在探寻推导公式的时候我们使用了两种策略一是正向推导二是逆向推导。
实际上正向推导就是归纳法其核心思想是从特殊到一般的推理过程通过对众多的事物特例进行观察和综合以发现一般规律的推理方法。
而逆序推导就是演绎法它是一种从普遍性的前提出发通过逻辑推理得出个别或特殊结论的方法。它基于已知的一般原则或假设推导出具体的结论确保如果前提为真则结论也必然为真。
这是两种非常重要的思维方式也是我们认识、理解和探索这个世界的基本方法。
二者各有其特点和适用范围归纳法有助于我们发现新知识和规律而演绎法则确保从已知前提中得出必然结论。在实际应用中两种方法常常相互补充共同推动人类知识的积累和发展。
学习编程不仅仅是学习编程知识更重要的是培养孩子的思维包括逻辑思维、数学思维和计算思维。
归纳法和演绎法是逻辑思维的两种具体体现这两种思维的培养和提升对于提高我们的逻辑思考能力和问题解决能力至关重要。在平时的学习过程中要有意识地加强这些思维的训练和提升。
超平老师给你留一道思考题在上面的递推算法中我们借助了一个列表用于保存第n分钟的病毒数量如果不使用数组是否可以又该如何实现呢
你还有什么好的想法和创意吗也非常欢迎和超平老师分享探讨。
如果你觉得文章对你有帮助别忘了点赞和转发予人玫瑰手有余香
需要源码的可以移步至“超平的编程课”gzh。
