小马搬运物品-第13届蓝桥杯省赛Python真题精选_将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种算法，尤其是带备忘录的递归和动态规划。如果说递归是自顶向下的推导过程，那么动态规划就是自底向上的推导过程。

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

• 《病毒繁殖-第12届蓝桥杯选拔赛Python真题精选》

• 《密室逃脱游戏-第12届蓝桥杯省赛Python真题精选》

• 《跳房子游戏-第13届蓝桥杯选拔赛Python真题精选》

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

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

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