一场亲子趣味运动引起的算法优化及Python实现

问题描述：

某学校举办亲子趣味运动会，规定每个孩子必须有一个家长陪同，所有的家长一组，孩子一组，为确保孩子们的安全，上场后每位家长最多只能照看一个孩子（不必须是自己的），要求家长组先派人上场之后孩子组才能派人上场，每个孩子上场时必须保证场上至少有一个家长能照看Ta。假设每队3个人，那么可能的出场方案有5种：

大大大小小小

大大小小大小

大大小大小小

大小大大小小

大小大小大小

函数main()接收一个<=15的自然数n作为参数，表示孩子的数量，要求计算并返回有多少种出场方案。例如，main(9)返回4862，main(15)返回9694845。

注：这个问题最初是中国传媒大学胡凤国老师发给我讨论的全国青少年编程挑战赛题目。对这个问题胡老师也在自己的公众号里分享了其他算法的实现，详见：算法恒久远，数学永流传：2021-2022年全国青少年Python编程挑战赛题目解析（6）

====================

参考代码1：

运行结果：

在上面的程序的内层函数中，使用形参already表示当前上场方案，如果需要获取这些方案的具体情况可以增加代码输出合法的方案。如果只获取方案数量可以删除这个形参并对内层函数略加修改，可以缩短一半左右的执行时间，也就是下面的参考代码2。

参考代码2：

运行结果：

在上面的两个程序中，都是模拟逐个选手上场的过程，遍历所有可能的情况，并在生成二叉树的过程中进行简单地剪枝来减少计算量。在代码中，使用1表示家长，-1表示小孩，运动会规则要求上场的每个小孩必须至少有一个家长照顾，所以仅当场上的所有1与-1之和大于0才能安排小孩上场，否则只能安排家长上场。

但在上面的代码中，没有对上场的家长数量进行检查和约束，剪枝不及时不彻底，有些计算是没必要的，还有优化的空间。上面两个程序的执行过程如下所示，在生成二叉树的过程中只对红框中的部分进行了剪枝。

剪枝原理（以n=3为例，红色箭头表示有效方案，红框表示提前剪掉的分支）：

容易看出，上面的剪枝还不够充分，没有对上场的大人的数量进行检查和约束，如果把这一部分分支提前剪掉，可以进一步减少计算量。

优化原理（以n=3为例，红色箭头表示有效方案，红框表示提前剪掉的分支）：

根据优化后的剪枝算法，改写程序如下，参考代码3：

运行结果：