父与子-2022年全国青少年信息素养大赛Python国赛第10题

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

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

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

一.赛事说明

2021-2022年（第8届）Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛，复赛是地方选拔赛，总决赛是全国各地选拔的精英汇聚在一起进行PK。

2021-2022年全国青少年Python编程挑战全国总决赛于2022年8月27日正式举行。一共是10道编程题，每道题100分，满分1000分，考试时间是120分钟。

10道编程题分别如下：

• 分苹果
• 韩信点兵
• 借书问题
• 四位数密码
• 邮票面值
• 组合取球
• 统计连续字符
• n的n次方
• 海盗搜身
• 父与子

超平老师将分10讲对每道题进行详细的解读和剖析，今天要解读的是第10题，父与子。

二.题目描述

题目背景：

学校举办亲子运动会，所有的父亲一组，孩子一组，出场规则是：父亲组先派一个人上场之后孩子组才能派一个人上场，假设每队3个人，可能的出场策略包括5种：

父父父子子子、父父子子父子、父父子父子子、父子父父子子、父子父子父子

任意输入父子的对数n(3 <= n <= 15)，计算并输出有多少种出场策略。

输入描述：

输入父子对数n

输出描述：

输出共有多少种出场策略

样例输入：

3

样例输出：

5

注意：

input()内不添加任何参数

只有完全正确才可提交，若无法点击提交说明答题存在错误，可及时进行检查并修改

三.思路分析

从本题的描述来看，这是一个排列组合问题，需要注意的是待排列的元素是重复的。

对于此题，有多种不同的实现方式，比如排列组合法、模拟算法、回溯算法和递归算法。其中，排列组合法和递归算法相对要简单一些，超平老师主要介绍这两种方法。

所谓的排列组合法就是使用itertools库中的permutations函数，将所有的排列都列出来，再进行筛选，将满足条件的排列筛选出来。

这种方法理解起来比较简单，代码也不复杂，但是当n大于5时，需要执行较长时间才能得到结果，有可能会超出时间限制。

递归算法的效率则要高很多，代码也十分精简，但是对于很多同学来说，理解起来难度较大，这也是递归算法的特点。

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

四.编程实现

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

• 排列组合法
• 递归算法

1.排列组合法

我们以n = 3为例，当n为3时，父和子都是3个，可以构造一个元组如下：

然后使用itertools模块中的permutations函数，将这6个元素进行全排列。在这些排列中，有的是不符合条件的，比如：

如何过滤掉这些不符合条件的排列呢？我们可以定义一个函数，对指定的元组进行判断，如果满足条件就返回True，否则就返回False。

具体的判断方法是，遍历给定的元组，对元组进行切片处理，然后统计当前父和子的个数，如果父的个数小于子，则返回False。

对应的代码如下：

此方法，理解起来比较简单，但是执行时间太长，考试时有可能出现超时的情况。

2.递归算法

递归是一种非常重要的基础算法，是指通过重复将问题分解为同类的子问题而解决问题的方法。具体表现上，在函数中直接或间接调用自己。

构成递归需要具备如下两个条件：

1). 子问题须与原始问题为同样的事，且更为简单；

2). 不能无限制地调用本身，必须要有出口；

首先定义递归函数fs(x，y)，其中x和y分别表示父亲和儿子的人数，注意这里的人数是指还没有出场的人数，返回结果就是满足条件的排列数量。有了递归函数，只需要调用fs(n, n)即可。

对于fs(x, y)而言，可以分成如下三种情况：

1). 父亲已经全部出场了，即x = 0，此时就只有一种排列了；

2). 没有出场的人数方面，父亲比儿子多，即 x > y，此时的排列就不能满足条件；

3). 其它情况下，既可以让父亲出场，也可以让儿子出场；

对应的代码如下所示：

递归算法的效率取决于递归的层数，本题中的n最大值为15，是完全没有问题的，执行速度还是非常快的。

从实际执行情况来看，很显然，方法2才是更好的方法。

五.总结与思考

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

• 输入输出函数；
• 列表操作；
• 递归算法；
• 时间复杂度的概念；

作为最后的压轴题目，本题还是非常有难度的，已经上升到常用算法层面了。如果你想从比赛中脱颖而出，算法学习是必不可少的。

在众多的算法中，相对来说，递归是一种简单的算法，但是递归也存在弊端，就是当递归的层数不断增加之后，程序的执行时间会急剧增加。所以，还需要进一步学习更加高效的算法，比如回溯和动态规划等。