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

问题描述：

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

大大大小小小

大大小小大小

大大小大小小

大小大大小小

大小大小大小

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

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

参考代码1：

运行结果：

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

参考代码2：

运行结果：

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

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

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

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

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

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

运行结果：