快捷搜索:

第十三届蓝桥杯省赛真题2022年4月23日 第四题答案及解析 小马过河搬货物方案

第四题 又又如约而至,上题目:

编程实现:

小马需要将N件物品从河的一岸搬运到河的另一岸,每次搬运的物品为1到3件。请问小马将N件物品全部搬运过去有多少种方案。例如:N=3,将3件物品全部搬运过去有4种方案:方案一:第一次搬运1件,第二次搬运1件,第三次搬运1件;方案二:第一次搬运1件,第二次搬运2件;方案三:第一次搬运2件,第二次搬运1件;方案四:一次搬运3件。

输入描述:

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

输出描述:

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

样例输入:

3

样例输出:

4

思路来啦: N = 1,只有1种方案 N = 2,有11和2,2种方案 N = 3,有111,12,21,3,4种方案

以上都没有规律

但当N >= 4时,就有规律了。

当N=4时,一共是7种方案,可以发现,是(N=3的方案数)+(N=2的方案数)+(N=1的方案数) 当N=5时,一共是13种方案,又发现,是(N=4的方案数)+(N=3的方案数)+(N=2的方案数) 当N=6时,一共是24种方案,又又发现,是(N=5的方案数)+(N=4的方案数)+(N=3的方案数) 依次类推,当N=x时,一共是(x-1的方案数)+(x-2的方案数)+(x-3的方案数)

这样我们就可以写代码了!采用递归思想:

N = int(input())  # 输入一个数(代表物品数)
def f(N):  # 创建一个递归函数
    if N == 1:  # 当N等于1、2、3时,结果没有规律,所以直接返回结果
        return 1
    elif N == 2:
        return 2
    elif N == 3:
        return 4
    else:
        return f(N-1)+f(N-2)+f(N-3)  # 发现的规律直接用过来
print(f(N))  # 最终打印结果
经验分享 程序员 职场和发展