当前位置:   article > 正文

小马搬运物品-第13届蓝桥杯省赛Python真题精选_将n件物品从河的一岸搬另一岸

将n件物品从河的一岸搬另一岸

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

小马搬运物品,本题是2022年4月23日举办的第13届蓝桥杯青少组Python编程省赛真题编程部分第4题,13届一共举办了两次省赛,这是第二次省赛。题目要求编程计算小马将N件物品从河的一岸搬运到河的另一岸一共有多少种方案。

先来看看题目的要求吧。

一.题目说明

时间限制:3000MS

内存限制:589824K8

编程实现:

小马需要将N件物品从河的一岸搬运到河的另一岸,每次搬运的物品为1到3件。请问小马将N件物品全部搬运过去有多少种方案。

例如:N = 3,将3件物品全部搬运过去有4种方案:

方案一:第一次搬运1件,第二次搬运1件,第三次搬运1件;

方案二:第一次搬运1件,第二次搬运2件;

方案三:第一次搬运2件,第二次搬运1件;

方案四:一次搬运3件。

输入描述:

输入一个正整数N,表示需要搬运的物品数

输出描述:

输出将N件物品全部搬运过去有多少种方案

样例输入:

3

样例输出:

4

评分标准:

  • 10分:能正确输出一组数据;

  • 10分:能正确输出两组数据;

  • 20分:能正确输出三组数据;

  • 20分:能正确输出四组数据。

二.思路分析

这是一道经典的算法题,涉及的知识点包括循环、条件、列表、递归、动态规划等。

看完题目描述,你脑海里首先想到的是什么呢?

如果你想到的是斐波那契数列,那么恭喜你,这道题基本上就可以拿下了。

图片

实际上,这是斐波那契数列的变种问题。

对于经典的斐波那契数列来说,每一项(第1项和第2项除外)都只和前面的两项有关系,即:

f(n) = f(n - 1+ f(n - 2)

本题中小马的搬运方案,每一项(前面3项除外)都和前面的三项有关系,如下:

f(n) = f(n - 1+ f(n - 2) + f(n - 3)

这是怎么推导出来的呢?

对于这种具有递推性质的问题,通常只需要考虑最后一步是如何计算的,就可以迅速的确定推导公式。

我们使用f(n)表示搬运n件物品的方案数量,最后一次到底搬运几件物品呢?

可以分3种情况讨论:

  • 搬运3件物品,那么搬运n - 3件物品的方案数为f(n - 3);

  • 搬运2件物品,那么搬运n - 2件物品的方案数为f(n - 2);

  • 搬运1件物品,那么搬运n - 1件物品的方案数为f(n - 1);

根据加法原理,当完成一件事情有n种不同的方式,且这些方式之间互不影响,那么完成这件事情的总方法数就是各类方式中的方法数之和。

因此,总的方案数量f(n)就等于f(n - 1) + f(n - 2) + f(n - 3)。

对于斐波那契数列及其变种这类问题,通常有如下三种解决方案:

  • 递归算法

  • 动态规划

  • 递推算法

不管使用哪一种思路,都需要单独考虑边界问题,对于本题而言,需要考虑前3项。

如果只有一件物品,毫无疑问只有一种方法,即f(1) = 1。

如果有两件物品,可以一次搬运两件,也可以分两次,每次搬运一件,所以一共有两种方案,即f(2) = 2。

如果有三件物品,可以每次搬运一件,分3次搬运,也可以一次搬运3件,还可以第一次搬运1件,第二次搬运2件,又或者是第一次搬运2件,第二次搬运1件,一共有4种方案,即f(3) = 4。 

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

三.编程实现

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

  • 递归算法

  • 动态规划

  • 递推算法

1. 递归算法

递归算法的重点是定义递归函数,代码如下:

图片

代码比较简单,但是随着n的增加,代码运行的时间会越来越长,效率会急剧下降。

其原因在于存在大量重复的计算,可以增加一个备忘录将每一次的计算结果保存起来,避免重复计算。

使用带备忘录的递归代码如下:

图片

代码不多,强调一点,这里的memo列表就是备忘录,前3项不需要保存,从第4项开始保存,对应于memo[4]。

有了备忘录,算法效率大大提高。

2. 动态规划

这里的推导公式(状态转移方程)和初始状态都已经确定好了,代码就比较简单了,如下:

图片

代码并不多,说明4点:

1). 这里定义函数f(n)用于计算搬运n件物品的方案数量,主要是为了方便处理边界条件,但它不是递归函数;

2). Python支持多变量赋值运算,因此可以直接写成dp[1], dp[2], dp[3] = 1, 2, 4,代码看起来更加紧凑;

3). 在循环计算的时候,从第4项开始,所以range()函数的起点是4;

4). dp列表的最后一项就是要计算的方案数量,可以使用dp[n]获取,也可以使用dp[-1]获取。

3. 递推算法

针对上面的动态规划算法,仔细想一想,每一项只和前3项有关,是不是只要保存这3项就可以了呢?

答案是肯定的,只需要4个变量就够了,1个表示当前项,另外3个用来保存前3项,从而节省了一个列表,这就是递推的写法,也叫迭代,代码如下:

图片

代码不难,强调一点,由于每一次都需要保存最后3项,需要不断更新f1,f2,f3的值,这就是f1, f2, f3 = f2, f3, f4的作用。

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

四.总结与思考

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

  • 循环语句;

  • 条件语句;

  • 列表;

  • 递归算法;

  • 动态规划函数;

  • 递推算法;

本题分值为60分,难度中等。关键点有两个,一是找到搬运物品方案的规律,确定好推导公式,二是使用多种算法来实现。

在找规律确定推到公式的问题时,一定要学会运用递归思维,将问题简化为两个步骤。最后一步保留,最后一步之前的所有步骤当作一步,然后看最后一步是如何计算出来的。切不可小瞧了这一点,在编程中,有很多问题都可以使用这一思维来解决。

本教程讲解了3种解决方案,这3种方案绝不是孤立的,它们之间都有一个共同的观点,这就是推导公式。

实际上,凡是有推导公式的问题,基本上可以采用这3种算法,尤其是带备忘录的递归和动态规划。如果说递归是自顶向下的推导过程,那么动态规划就是自底向上的推导过程。

和斐波那契数列相关的题目在历届真题中多次出现,如下:

你可以放在一起来分析对比,以加深理解。

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

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小桥流水78/article/detail/1013488
推荐阅读
相关标签