第8讲递归

组合数学第08讲_必胜策略游戏策略中往往有一类比较复杂的，需要逐步来递归的问题，这就需要对必胜与必败转态进行标记．一．网格移动类1．含义：给定一个东西和固定的表格，给出移动该物体的规则，最终谁移动到不能再移谁就算胜（或者输），求必胜（或必败）策略．2．方法：从最后必胜（或必败）的转态进行倒推，找出一般的规律，将必胜（或必败）的格子都标记出来即可找出必胜策略．二．其他类型1．特点：操作次数比较有限，没有周期规律．2．方法：由于操作次数较少，所以通常用枚举法，将必胜的操作标记出来，就可以得到必胜策略．重难点：从最后的必胜条件出来，进行倒推，将必胜的操作标记出来．题模一：网格移动类例1.1.1如下图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45 角走1步，最终将棋子走到方格B的人获胜．请问：（1）谁一定能获胜？必胜策略是什么？BA【答案】（1）甲必胜；（2）甲必胜【解析】（1）我们给必胜格子（如方格B）标记“√”，给必败格子标记“×”．从方格B逆推，能一步走到B的格子都要标记“×”．特别地，最上边一行和最右边一列为“√”和“×”相间的标记，如左图．对于左图中的格子1和格子3，对方有办法把它移到必胜格子中，所以格子1和格子3都是必败格子．如果把棋子移到格子2中，对手无论怎么移，都只能移到必败格子中，因此格子2是必胜格子．用类似的方法分析，得到右图．因此甲有必胜策略，每次把棋子移到标有“√”的格子中即可．（2）与第（1）问方法类似，得到下图．甲有必胜策略，每次把棋子移到标有“√”的格子中 即可．例1.1.2如图，方格A 中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B 的人获胜．请问：（）一定能获胜？A ．甲B ．乙C ．甲和乙都有可能【答案】B【解析】如下图标a 都是必胜格，A 本身就在必胜格里，所以先走的到达不了下一个必胜格，所以乙胜． 例1.1.3如图，方格A 中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B 的人赢．请问：（）一定能获胜？√ × √ × √ × B 1 × × 2 3 √ × √ A × √× √ × √ × B × × × × × × × √ × √ × √ × √ × × × × × × × √ × √ × √ × √ A × × × × × ××× × × × × B × × × × √ × × × × × × × √ × × √ × × × × × × × × × × × × A × × √ × × ×B AB a a ABAA．甲B．乙C．甲和乙都有可能【答案】A【解析】如图表有a的都是必胜格，只要甲第一步走到标有a个格必胜，选A．BaaaA a例1.1.4把一枚棋子放在图中左下角的方格内，甲、乙两人玩这样一个游戏：双方轮流移动棋子，只能向上、向右或者向右上方沿45°角移动，一次可以移动任意多格．谁把棋子移到了右上角的方格中即为输，试问：如果甲先走，是否有必胜的策略，为什么？【答案】乙必胜．从右上角开始分析哪些位置是必胜的，哪些位置是必败的，结果如图所示．因此甲第一步必然走到“√”上，而乙必然可以每一步都给甲留下“×”．【解析】首先看图最右面的那列，在这列中，如果棋子在右上角的下面，那么先走的只能把棋子向上走，所以他必败；如果棋子不在这个位置，那么他只要把棋子走到这个位置便可确保胜利．而为了方便分析，下面在图中先走必胜的位置标“√”，先走必败的位置标“×”，此时图如下所示：对1和2这两个位置，第一步只要走到右上的“×”处，便可取胜，所以标“√”；对3来说，怎么先走的如何走，都是走到一个“√”处，因为“√”处先走必胜，所以对3先走必败，应当标“×”．从上面的分析中，可以发现，对一个位置来说，如果它的上，右或右上有一个“×”，那先走的只需要把棋子移动到这些“×”处便可确保胜利；相反，如果它的三个方向上全是“√”，那无论如何走，都是后走的获胜．根据这个规律，便不难知道对任意一个位置来说，是否先走必胜，从而可以完成这个图，完成后的图如下所示：因为棋子最开始在左下角，甲只能向右走，而它右侧全部是“√”，所以乙必胜，每步时× √ √ √ × √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ √ √ √× 1 √ 2 3 √ √ √ √ √ √ √ ● √× √ √ √ × √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ ● √ √ √ √ √ √ √ √ √ √乙只需要把棋子移动到“×”即可． 题模二：其它例1.2.1桌上有一块巧克力，它被直线划分成3行7列的21个小方块，如图所示．现在让你和对手进行一种两人轮流切巧克力的游戏，规则如下：①每人每次只许沿一条直线把巧克力切成两块；②拿走其中一块，把另一块留给对手再切；③不断重复前两步，最后谁能恰好留给对手一个小方块，谁获胜．如果你首先切巧克力，那么你第一次应该切走多少个小方块，才能保证自己最后获胜？【答案】切走12个小方块【解析】当只剩1行（或1列）时，但不是一个小方块，先切的人只要切剩下一个小方块就赢了．当剩2行（或2列）时，如果剩22⨯的方块，那么先切的人切完后成为12⨯的方块，所以后切的人必胜；如果剩23⨯、24⨯、…等情况，先切的人只要切剩下一个22⨯的方块就可以取胜．当剩3行（或3列）时，如果剩33⨯的方块，先切的人切一刀后只能剩下13⨯或23⨯的方块，此时后切的人获胜．当有37⨯块时，先切的人切走3412⨯=块，给对手留下一个33⨯的正方形，接着每次都给对手留下一个11⨯或22⨯的正方形即可获胜． 例1.2.2如图为“狡兔三窟”的游戏，游戏中只有两个棋子：一为“猎人”，一为“狡兔”，它们的位置如图所示，棋盘的北端X 是一方飞第，这意味着任何一方棋子，都可以“飞”过X ，即：由C 直接到达D ，或由D 直接到达C ，游戏开始，由“猎人”先走，接下去双方轮流运子，每次一步，每次只能沿着黑线走到其相邻的点上，当猎人和兔子都到同一点时，猎人可以抓住兔子．那么，“猎人”至少要走（ ）步才能抓住兔子．A ．5B ．6C ．7D ．8【答案】B【解析】如果猎人第一步就开始往下抓兔子，那么兔子也会往下跑，这样猎人紧追兔子中间只差一步的话是永远抓不到兔子．那么猎人的对策就是第一步向上走，前三步向上绕一圈，这是猎人在空心点上，兔子在实心点上，如果兔子在1号位置，第4步抓到，若兔子在2，至多再3步抓到，最终在第6步被抓到例1.2.3在黑板上写有999个数，2、3、4、……、1000．甲、乙两人轮流擦去黑板上的一个数（甲先擦，乙后擦），如果最后剩下的两个数互质，则甲胜，否则乙胜．请判断：__________有必胜策略．【答案】乙【解析】共有500个偶数，甲共擦499个数．若甲想获胜，他必须擦499个偶数，否则乙只要先擦奇数，最终必能剩两个偶数，乙胜．但当甲全擦偶数时，乙只要保留两个个位为5的奇数至最后即可，故乙有必胜策略．随练1.1如右图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走1步，最终将棋子走到方格B的人获胜．请问：谁有必胜策略？必BA【答案】甲必胜【解析】策略是每次把棋子走到下图中标有“√”的格子内．√×√× B×××××√×√×√A ××××随练1.2如图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B的人赢．请问：（）一定能获胜？BAA．甲B．乙C．甲和乙都有可能【答案】B【解析】如下图标a都是必胜格，A本身就在必胜格里，所以先走的到达不了下一个必胜格，所以乙胜，选B．BaaaA随练1.3如图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B的人获胜．请问：（）一定能获胜？BAA．甲B．乙C．甲和乙都有可能【答案】A【解析】甲第一步走到如图所示的a处，无论乙怎么走，甲都有方法取胜，所以选A．BaA随练1.4桌上有一块巧克力，它被直线划分为排成3行7列的21个小方块，如图所示．现在让你和对手进行一种两人轮流切巧克力的游戏，规则如下： ① 每次只许沿一条直线把巧克力切成两块； ② 拿走其中一块，把另一块留给对手再切； ③ 谁能留给对手恰好是一个小方块，谁就取胜．如果请你首先切巧克力，那么你第一次应该切走多少个小方块，才能使你最后获胜？【答案】切走12块，给对手留下一个33⨯的正方形，接着每次都给对手留下一个正方形 【解析】如果只剩1行或1列，但不是一个小方块，那么先切的人只要剩一个小方块就赢了；如果剩2行，如果是22⨯的方块，那么先切的人切完后成为12⨯的方块，所以后切的人必胜；如果比22⨯多的话（23⨯，24⨯……），因为22⨯的时候是后切的人获胜，所以这时先切的人只要剩下一个22⨯的方块就可以取胜；在33⨯的时候，先切的切完后，剩下的巧克力是13⨯或者23⨯，根据上面的分析可以知道后切的一定获胜．所以第一刀切完后剩下33⨯的就可以保证获胜了，即是切下3412⨯=块巧克力．随练1.5如图所示，五角星上共有10个交点和15条小线段．甲首先将一枚棋子放在A 点上，并由此出发沿某条小线段将棋子移到相邻的一个交点上，之后乙再将棋子沿某条小线段移到下一个相邻的交点上，之后甲再走，……，如此下去．如果要求每条小线段都不能重复经过，并且轮到某人无路可走时便判其失败，那么甲是否有必胜策略？【答案】甲没有必胜策略，且乙必胜．一旦甲由角上的点走到中间，乙就再走回相邻的角上去．【解析】一枚棋子如果处在五角星的某个角上的话，先走的人只能把它从角上移到中心．而如果在中心的话则可以选择移到角上或者其他中心位置．据此可以给乙想出如下的方案：一旦甲由角上的点走到中间，乙就再走回相邻的角上去，角上的点是5个，中心点也只有5个，最后必然是连成一个封闭图形，甲无路可走．作业1如下图，方格A 中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走1步，最终将棋子走到方格B 的人获胜．请问：谁一定能获胜？必胜策略是什么？A【答案】甲必胜【解析】我们给必胜格子（如方格B ）标记“√”，给必败格子标记“×”．从方格B 逆推，能一步走到B 的格子都要标记“×”．特别地，最上边一行和最右边一列为“√”和“×”相间的标记，如左图．对于左图中的格子1和格子3，对方有办法把它移到必胜格子中，所以格子1和格子3都是必败格子．如果把棋子移到格子2中，对手无论怎么移，都只能移到必败格子中，因此格子2是必胜格子．用类似的方法分析，得到右图．因此甲有必胜策略，每次把棋子移到标有“√”的格子中即可．作业2（1）在一个3×3的方格棋盘的左上角方格中放有一枚棋子。

递归的概念 递归过程与递归工作栈 递归与回溯 广义表
递归的概念
递归的定义 若一个对象部分地包含它 自己, 或用它自己给自己定义, 则称这 个对象是递归的；若一个过程直接地或 间接地调用自己, 则称这个过程是递归 的过程。
以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的
do {
while ( n > 1 ) { w->n = n; w->tag = 1; S.push ( w ); n--;
} //向左递归到底, 边走边进栈 sum = sum + n; //执行求和
while ( !S.IsEmpty( ) ) { w = S.getTop( ); S.Pop( ); if ( w->tag == 1 ) { //改为向右递归 w->tag = 2; S.push ( w ); n = w->n – 2; //F(n)右侧为F(n-2) break; }
Fib(1) Fib(0)
2 1 2 2
3 1 3 1 3 1 3 2
4 1 4 1 4 1 4 1 4 1 4 2
n=1
n=0
n=1
sum=0+1 n=2-2 sum=1+0 n=3-2 sum=1+1 n=4-2

Fib(4)

Fib(3)


Fib(2) Fib(1)
递归调用
n! (n-1)! (n-2)!
1! 0!=1
返回次序
主程序第一次调用递归过程为外部调用；
递归过程每次递归调用自己为内部调用。
它们返回调用它的过程的地址不同。

递归算法详解完整版递归算法是一种重要的算法思想，在问题解决中起到了很大的作用。

它通过将一个大问题划分为相同或类似的小问题，并将小问题的解合并起来从而得到大问题的解。

下面我们将详细介绍递归算法的定义、基本原理以及其应用。

首先，我们来定义递归算法。

递归算法是一种通过调用自身解决问题的算法。

它通常包括两个部分：基础案例和递归步骤。

基础案例是指问题可以被直接解决的边界情况，而递归步骤是指将大问题划分为较小问题并通过递归调用自身解决。

递归算法的基本原理是"自顶向下"的思维方式。

即从大问题出发，不断将问题划分为较小的子问题，并解决子问题，直到达到基础案例。

然后将子问题的解合并起来，得到原始问题的解。

递归算法的最大特点是简洁而优雅。

通过将复杂问题分解为简单问题的解决方式，可以大大减少代码的复杂程度，提高程序的效率和可读性。

但是递归算法也有一些缺点，包括递归深度的限制和复杂度的不确定性。

过深的递归调用可能导致栈溢出，而不合理的递归步骤可能导致复杂度过高。

递归算法有许多应用场景，我们来介绍其中一些典型的应用。

1.阶乘问题：计算一个数的阶乘。

递归算法可以通过将问题划分为更小的子问题来解决。

例如，n的阶乘可以定义为n乘以(n-1)的阶乘。

当n 等于1时，我们可以直接返回1作为基础案例。

代码如下：```int factorial(int n)if (n == 1)return 1;}return n * factorial(n - 1);```2.斐波那契数列问题：求斐波那契数列中第n个数的值。

斐波那契数列的定义是前两个数为1，然后从第三个数开始，每个数都是前两个数的和。

递归算法可以通过将问题划分为两个子问题来解决。

当n等于1或2时，直接返回1作为基础案例。

代码如下：```int fibonacci(int n)if (n == 1 ， n == 2)return 1;}return fibonacci(n - 1) + fibonacci(n - 2);```3.二叉树问题：对于给定的二叉树，递归算法可以通过递归调用左子树和右子树的解来解决。

数据结构之递归Ⅲ递归的三⼤要素// 算 n 的阶乘(假设n不为0)int f(int n){if(n <= 2){return n;}}第三要素：找出函数的等价关系式第三要素就是，我们要不断缩⼩参数的范围，缩⼩之后，我们可以通过⼀些辅助的变量或者操作，使原函数的结果不变。

例如，f(n) 这个范围⽐较⼤，我们可以让 f(n) = n * f(n-1)。

这样，范围就由 n 变成了 n-1 了，范围变⼩了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。

说⽩了，就是要找到原函数的⼀个等价关系式，f(n) 的等价关系式为 n * f(n-1)，即f(n) = n * f(n-1)。

这个等价关系式的寻找，可以说是最难的⼀步了，如果你不⼤懂也没关系，因为你不是天才，你还需要多接触⼏道题，我会在接下来的⽂章中，找 10 道递归题，让你慢慢熟悉起来。

找出了这个等价，继续完善我们的代码，我们把这个等价式写进函数⾥。

如下：// 算 n 的阶乘(假设n不为0)int f(int n){if(n <= 2){return n;}// 把 f(n) 的等价操作写进去return f(n-1) * n;}⾄此，递归三要素已经都写进代码⾥了，所以这个 f(n) 功能的内部代码我们已经写好了。

这就是递归最重要的三要素，每次做递归的时候，你就强迫⾃⼰试着去寻找这三个要素。

还是不懂？没关系，我再按照这个模式讲⼀些题。

有些有点⼩基础的可能觉得我写的太简单了，没耐⼼看？少侠，请继续看，我下⾯还会讲如何优化递归。

当然，⼤佬请随意，可以直接拉动最下⾯留⾔给我⼀些建议，万分感谢！Ⅲ案例1：斐波那契数列斐波那契数列的是这样⼀个数列：1、1、2、3、5、8、13、21、34....，即第⼀项 f(1) = 1,第⼆项 f(2) = 1.....,第 n 项⽬为 f(n) = f(n-1) + f(n-2)。

求第 n 项的值是多少。