[11]递推与递归
深入浅出程序设计竞赛第1 部分–语言入门V 2024-01
www.luogu.com.cn
版权声明本课件为《深入浅出程序设计竞赛–基础篇》的配套课件，版权归洛谷所有。所有个人或者机构均可免费使用本课件，亦可免费传播，但不可付费交易本系列课件。若引用本课件的内容，或者进行二次创作，请标明本课件的出处。?其它《深基》配套资源、购买本书等请参阅：https://www.luogu.com.cn/blog/kkksc03/IPC-resources?如果课件有任何错误，请在这里反馈https://www.luogu.com.cn/discuss/show/296741本章知识导图第11 章递推与递归递推思想递归思想课后实验与习题递推思想
知道递推式，也知道初始条件，从初始条件开始往上顺推直到求得目标解的思想就是递推。请翻至课本P154数楼梯例11.1 数楼梯(洛谷P1255)楼梯有??(??≤5000)阶，上楼可以一步上一阶，也可以一步上二阶，计算共有多少种不同的走法。例如，n=4时有以下5种走法：0 → 1 → 2 → 3 → 40 → 1 → 2 → 40 → 1 → 3 → 40 → 2 → 3 → 40 → 2 → 4
数楼梯分析：可使用回溯法枚举所有走法，但是数据范围稍大就会超时。想要走到第1000个台阶，必须先走到第999个台阶或者第998个台阶，然后一步跨到第1000个。1到第999级的走法数量1到第1000级的走法数量=+1到第998级的走法数量令从第1个到第i个台阶的走法数量是f[i]，可得：f[i]=f[i-2]+f[i-1]数楼梯后一项等于前面两项之和。这不就是斐波那契数列吗？即使归纳得到了这个式子（称为递推式），还不能说明这是一个斐波那契数列。计算这个数列中的某个元素需要得到它前面的两项元素就行。如果知道f[1] 和f[2] 的值，就可以推导出整个数列。f[1] 和f[2] 是这个数列的初始条件。对于这个问题而言初始条件是什么呢？?n=1 显然只有一种走法。?n=2 可以分两步走，或者两步并一步走，有两种走法。所以可以确定f[1]=1，f[2]=2。
数楼梯现在有了递推式，有了初始条件，就可以获得完整的数列了。经过计算，可以得到这个数列前面几项是：1、2、3、5、8、13、21 ...这就是斐波那契数列从第2 项开始的序列。而斐波那契的初始条件就是f[1]=f[2]=1。像这样知道递推式，也知道初始条件，从初始条件开始往上顺推直到求得目标解的思想就是递推。数楼梯由于斐波那契数字增长得很快，所以需要使用高精度计算。这里使用了“模拟与高精度”一章中提供的封装好的大整数结构体。intmain(){cin>>N;Bigintf[5010];f[1]=Bigint(1);f[2]=Bigint(2);for(inti=3;i<=N;i++)f[i]=f[i-2]+f[i-1];f.print();return0;}过河卒例11.2 过河卒（洛谷P1002，NOIP2002普及组）棋盘左上角(0,0)有一个过河卒，需要走到右下角(n,m)，卒每次可以向下或者向右一格。棋盘上有一个固定的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点，卒无法经过。求卒从起点到终点所有的路径条数。如图，当卒要从(0,0) 往右或下走到(6,6)，马在(3,3)。马能跳到的位置已经打上了叉，卒不能走到这些点，一共有6 种合法方案。
过河卒分析：暴力枚举还是枚举往右或往下然后回溯搜索，依然会超时。如果那个马不存在，从左上角到右下角一共有多少种走法？记从原点(0,0) 走到坐标(i, j)的方法数量是f[i, j]。当卒从起点开始，笔直往右或者笔直往下，只有唯一的一种走法。所以k≥0 时，f[k,0]=f[0,k]=1，这就是递推的初始条件。均只有一种走法过河卒记从原点(0,0) 走到坐标(i, j)的方法数量是f[i, j]。如何从点(0,0) 到点(1,1) 呢？要么是从点(0,1) 走下一格，要么是从点(1,0) 往右走一格，即f[1,1]=f[0,1]+f[1,0]。当i>0 且j>0时，f[i, j] = f[i-1,j] + f[i,j-1]，这就是递推式。f[i-1,j]f[i,j]=f[i-2,j]+f[i,j-1]f[i,j-1]过河卒有了递推式，有了初始条件，就可以求出完整的f 数组的值了。如果没有马，f 数组如左图。f[i-1,j]被马控制f[i,j]=f[i-1,j]如果有些点因为马的把守而不能走呢？无法从马的控制点转移到下一个点，那么就不进行转移，如右图。
此外初始条件和递推范围变为f[0,0]=1 ，递推范围i≥0,j≥0,ij≠0。
过河卒在实现时，需要预处理哪些点是马的控制点，然后对所有的点进行递推操作。只有转移来的格点存在，才会累加方案数。#include 栈分析：设i个元素一共有h[i]种出管方式，求n 个元素的出管方式。其中每个元素都可能最后一个出管。假设第k 个小球最后出管：?比k 早入且早出有k-1 个数，有h[k-1] 种出管方式；?比k 晚入且早出有n-k 个数，有h[n-k] 种出管方式，一共有h[k-1]×h[n-k] 种出管方式。递推式为h[n] = h[0]×h[n-1] + h[1]×h[n-2] + ... + h[n-1]×h[0]初始条件为h[0]=h[1]=1 栈像这种只有一个开口、元素先进后出的管子称为栈，在数据结构线性表一章我们会更详细地介绍栈的性质使用方式。h 数组里面的数字就是卡特兰数，前几项是1,1,2,5,14,42。卡特兰数有很多奇妙的性质，会在《进阶篇》中仔细讨论。#include 构造函数，这个函数在运行过程中调用自己，从而解决问题的思路被称为递归思想。请翻至课本P158数的计算例11.4数的计算（洛谷P1028，NOIP2001 普及组）给出自然数??(??≤1000)，最开始时数列中唯一的一项就是n，可以对这个数列进行操作，生成新的数列。请问最后能生成几种不同的数列？1.原数列直接作为一种合法的数列；2.在原数列的末端加入一个自然数，但是它不能超过该数列最后一个数字的一半；3.加入自然数后的数列继续按此规则从第一条进行处理，直到不能再加新元素为止。 数的计算输入数字6，可以生成以下数列：1：6 (原数字）2：6 1（在数列1后添加了1，无法再添加了）3：6 2（在数列1后添加了2）4：6 2 1（在数列3后添加了1，无法再添加了）5：6 3（在数列1后添加了3）6：6 3 1（在数列5后添加了1，无法再添加了）7：6 3 2 （在数列5后添加了2） 8：6 3 2 1（在数列7后添加了2，无法再添加了） 数的计算分析：例如数列最开始只有一个元素8，在末尾加入一个新元素，列表就变成[8 4]、[8 3]、[8 2]、[8 1]，算上[8] 一共有5 种情况。计算更长的数列的方案数怎么办呢？分别计算[4]、[3]、[2]、[1] 按照这样的操作能有几种情况，然后累加统计即可。以4 开头（3、2、1 同理）的所有合法数列，都可以接续到8 的后面。数的计算原来是要解决n=8 的问题，现在分解成了四个规模更小但是本质上是同样的子问题。直到n=1 时，没法继续分解，可以直接返回唯一一种数列，即[1]。然后返回上一层（n=2）接收到所有小规模问题的答案，合并统计处理获得这个规模下的答案，再返回上一层……直到求得问题的解。intsol(intx){if(x==1) return1;intans=1;for(inti=1;i<=x/2;i++)ans+=sol(i);returnans;}像这样构造函数，这个函数在运行过程中调用自己，从而解决问题的思路被称为递归思想。数的计算答案正确，但是并不能通过本题：运行效率很低导致程序超时。例如，sol(2) 可能由sol(4) 调用，也有可能被sol(8) 调用，但是sol(2) 的值固定不变，这里却被重复运行了很多次。开数组f，f[i] 就是当问题规模为i的时候的答案。初始化为-1，说明f[i] 还没有被计算过。使用同样的办法求解，如果发现已经计算过就直接返回f[i] ，否则仍递归计算，然后将结果存入数组中以便之后再次调用。intn,f[1010];intsol(intx){intans=1;if(f[x]!=-1)returnf[x];for(inti=1;i<=x/2;i++)ans+=sol(i);returnf[x]=ans;}intmain(){cin>>n;memset(f,-1,sizeof(f));f[1]=1;cout< Function分析：如果输入数据不在(0,20] 这个范围内，强制返回1 或者w(20,20,20)。根据题意写函数，建立数组记录w 的值进行记忆化。longlongf[25][25][25];longlongw(longlonga,longlongb,longlongc){if(a<=0||b<=0||c<=0)return1;elseif(a>20||b>20||c>20)returnw(20,20,20);elseif(f[a][b][c]!=0)returnf[a][b][c];elseif(a 本题也可以使用递推方法，只是边界问题和枚举顺序稍不好处理，感兴趣的读者可以自己尝试使用递推实现本题。 外星密码例11.6 外星密码(洛谷P1928）有一种压缩字符串的方式：对于连续的D(2≤??≤99) 个相同的子串X 会压缩为\的形式，而X 可能可以进行进一步的压缩。比如说字符串CBCBCBCB 可以压缩为[4CB]或者[2[2CB]]。现给出压缩后的字符串，求压缩前的字符串原文。[2[2CB]] = [2CB][2CB] = CBCBCBCB外星密码分析：假设只有一层方括号，那只需要找到方括号，就可以将该部分还原。如果方括号的“重复部分”里还有方括号呢？没关系，设法把里面的方括号继续展开即可。因此可以写成递归函数。字符串ABF[4RA[2A]B[3C]] 的展开如图：外星密码#include 学而时习之，不亦说乎。学而不思则罔，思而不学则殆。——孔子请翻至课本P162小结递推需要确定递推式、初始（边界）条件，从微观到宏观。递归将一个大的任务分解成若干个规模较小的任务，而且这些任务的形式与结构和原问题一致，然后将结果合并，直到达到边界。有些问题使用递推策略和递归策略都能解决，但有些问题只能将大问题分割成小问题，但是却很难建立递推式，或者不好确定递推顺序，这种情况下应当使用递归策略。 但递归需要记录每一层的状态，因此可能会比较占用空间。 课后习题思考题递推与递归的例题中，哪些可以使用另外一种思路（比如递归的例题是否可以使用递推完成）？如果可以的话，尝试使用另外一种方式完成这些例题。课后习题习题11.3 选数（洛谷P1036，NOIP2002 普及组）已知??个整数??1,??2,…,????(????≤5×106)，以及1 个整数??(?? 课后习题习题11.5 秘密奶牛码（洛谷P3612，USACO2017 January）给定一个长度不超过30 的字符串，不断对这个将这个字符串后面拼接自身的“旋转字符串”（旋转字符串是指把原字符串的最后一个字符移动到第一个之前）比如COW 拼接后变为COWWCO，再变成COWWCOOCOWWC，这样可以扩展成一个无限长度的字符串。给定??(??≤1018)，求这个字符串第??个字符是什么。第一个字符是??=1。课后习题习题11.6 黑白棋子的移动（洛谷P1259）有2??(4≤??≤100)个棋子排成一行，初始时先摆上??个白棋子，然后再摆上??个黑棋子，同时最右边还有2 个空位。移动棋子的规则：每次必须同时移动相邻的两个棋子，颜色不限，可以右空位上，但不能调换两个棋子的位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。要求。请编程打印出移动过程。例如，当??=5时，移动的过程如下：step 0:ooooo*****--step 1:oooo--****o*step 2:oooo****--o*step 3:ooo--***o*o*step 4:ooo*o**--*o*step 5:o--*o**oo*o*step 6:o*o*o*--o*o*step 7:--o*o*o*o*o*课后习题习题11.7 幂次方（洛谷P1010，NOIP1998 普及组）任何一个正整数都可以用2 的幂次方的和表示。例如137=27+23+20，同时约定方次用括号来表示，即????可表示为a(b)。由此可知，137 可表示为：2(7)+2(3)+2(0)。进一步，7=22+2+20(21用2 表示)，3=2+20，所以最后可表示为2(2(2)+2+2(0))+2(2+2(0))+2(0)。给出??(??≤20000)，按照题目要求输出将??变为2 和0 组成的幂次方式子。课后习题习题11.8 地毯填补问题（洛谷P1228）迷宫是一个边长为2??,(0 课后习题习题11.9 南蛮图腾（洛谷P1498）南蛮图腾是一种递归图形。当规模为1 时，南蛮图腾是一个简单的三角形，如下图左。规模每增加1，图形就变得复杂了：把原来规模的图形复制三次，分别放置于上方，左下角和右下角，组成了一个更大的三角形。当规模为2 的时候，图形如下图右：/\\/__\\/\\/__\\/\\/\\/__\\/__\\给出规模n(n≤10)，请画出对应规模的图形。
[洛谷深基]第11章 递推与递归v202401 - 图文
