算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
小游戏
Loading...
来自 Peking University 的课程
算法基础
284 个评分
从本节课中
递归
递归调用是设计和描述算法的一种有力工具，尤其是在解决复杂问题时经常采用。它的基本思想是要解决某一问题A，可以先解决一个形式相同，但规模小一点的问题B。问题B如果解决了，那么问题A也就迎刃而解。有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易地解决。本模块将通过具体的例题介绍如何构造递归函数，如何设置递归终止的条件以及分析递归算法的复杂度。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，那么我们这一小节中呢就来看一下递归中的例子，称为叫做小游戏。
这个题目呢是这样子描述的。
如果有一天早上起来，你突然想说，咦？我编程这么牛，为什么不能靠这个写点赚点小钱呢？
于是呢，你就决定编写了一个小程序，
啊，这个题干本身是有点狗血，那么你编的这个游戏是什么呢？
我们来看，这个游戏呢，是说在一个分割成
w*h的一个正方格子的一个矩形的板上来进行，
来进行，方格子，恩每一个格子上呢，
可以有游戏卡或者是没有，
那么这样的一个正方，一个矩形上面有n个这样的游戏卡的一个问题，
具体要怎么做呢？ 他是说那么我们会认为两个游戏卡之间会有一个路径相连，
注意，这条路径只包含水平，或者是竖直的直线段，
啊，只能是直线，不能是斜线也不能是任何的曲线。
同时呢，路径不能穿过别的游戏卡，
你只能从没有游戏卡的地方通过， 诶，有同学会说，这不就连连看吗？
这是一个稍，从规则上略复杂，但实际中间更简单的一个版的连连看，啊。
那么这一个连连看本身呢，这个小游戏呢，他是允许路径
径临时的离开矩形板的，阿我们通常对于连连看来讲就是一个维护一个U型这样的一个，啊，
连接线，然后这一个问题来讲，
我们会看到比方说，我们需要去连接，
(1,3)位置这个游戏卡和(4,4)这个游戏卡，
那么我们就可以让他这个 连接线，
驶出这个整个矩形板的范围， 也就是说在外面来连接起来，这样两个游戏卡就是允许的。
那么我们对于(2,3)这个游戏卡和(5,3)这个游戏卡呢，
我们就可以让他通过穿过这样的方式来进行，
那么这样呢注意就是，这个路径本身他就不只是一个U型了，他又拐了一下，啊。
那么如果对于， (2,3)这个游戏卡和(3,4) 这个游戏卡，那么这两个游戏卡呢
就怎么样都是不相连的是嘛，因为你不管怎么样连结他都要去通过其他的游戏卡片，才可以实现，
所以我们说，我们在这个游戏小游戏当中呢，需要找寻一个合适的路径
这个路径本身呢可以将两个卡片连接起来，但是不穿过其他的卡片。
所以我们在问题当中，就是要去判断一下，
是否存在一条满足我们刚才看到题意的路径， 这个路径能够连接两个相应的游戏卡。
那么对于这个程序的输入来讲的话呢，还输入包含了多组的数据，
那么首先第一个呢，就是关于这个矩形板相应的一组数据，啊，
也就是说第一行中间呢，是两个整数，分别是w和h，
那么用来描述这个矩形的宽和长，
那么接着呢，这个下面的h行阿，h行中间，包含了w个字符，
那么这 w个字符中间呢，有用x表示的，表示说这个地方呢是有一张游戏卡，
如果是一个空格呢，则表示没有游戏卡
那么输入的接着的话呢，会输入四个整数，
这四个整数呢分别是x1, y1和x2, y2， 那么x1,
y1呢他是，x1, y1和x2, y2呢他是这个，啊， 大于等于1，小于等于w的。
也就是说这是描述着游戏卡所在的这个矩形板上的横坐标，啊，横坐标
那么接着呢就是y阿，这个y值的话呢，他就是小于大于等于1，小于等于h的，
那么这个x和y这个坐标呢，就分别描述了，
这个游戏片的位置，那么由于我们要考虑是连接两个游戏片，
所以呢他会给出一对儿值来，
那么我们会看到，如果说呢，这一行中间有四个0， 表示呢这一个测试数据呢就结束了。
那么，如果上如果一行中间给出w和等于0， w和h都等于0，那么表示所有的输入呢，就结束了。
那么相应的，刚才是输入数据的一个描述，输出数据呢，我们会对于一个矩形板呢，
每一个矩形板呢都会去输出一个Board的一个number，那n就是相应输入数据的一个编号
那么对于每一组需要测试的一个游戏卡片的这样一个输出呢，只输出一行，
那么这一行的开头呢是指pair m，m呢就是呢这一个测试卡片的编号，
那么每一个矩形板都从一开始编， 那么呢如果说你能找到一个合适的路径，他们两个游戏卡是可以相互连接的，
那么我们就需要去找到这个连接这两个卡片的所有路径当中，
连接那个线段数中那个最少的路径，也就是说要找到那个最短路径， 输出k
segments，也就是说利用多少段，多少个线段可以构成这个路径。
那么k就是我们找到这最优路经中，包含了线段的数目，
那么如果他本身是不能相连，我们就要去在这个pair后面去输出这个impossible，那没有找到合适的路径，
那么注意就是，每一组数据之后会输出一个空行，
我们看到，这是一个样例的输入和输出，
对于样例的输入来讲，我们首先看到的是w和h，就是说我们有一个w是5，
h是4的这样的一个矩形板， 在这个矩形板上头呢，有标记6x，会用叉，来标记说哪里放了
游戏板阿游戏卡，之后给出了若干个这样三组，
这个x1, x1, y1, y2这样的一个对应的这个
嗯，游戏卡片的这一个坐标值，
最后呢，是用来标记说，我们当前的这一个，嗯，
游戏结束， 我们会看到相应的这样样例输出呢，
就是这个给出一个board，在这个例子当中只有一个一张矩形板，
那么其中有三对儿，有三对儿这个
游戏游戏卡对儿要去判断，
对于第一个来讲呢，他有四个线段，第二个呢是三个，而对于第三个呢，他不能找到合适的路径。
我们来看一看，
这个问题本身，他是应该怎么去考虑程序设计的一个思路呢？
我们看到，这样的一个游戏卡也好，或者我们说是一个迷宫问题也好
那么他最大的特点在于，他每一步的探测的方式呢，都几户是相同的，
也就是说，整个程序具有很强的自相似性，
这个自相似性呢，表现在你每走一步，
你每到当前的游戏卡片或者是空位上以后，
那么你的探测方式都是相同的，没有任何区别
不论你的当前的路径走到了哪一个空格上，那么他们都有呢这样的一个
前后左右几种方向来进行选择的一个方式，
因此呢我们说，对于迷宫问题来讲，最简单的方法就是去使用递归。
因为你每一次碰到呢这个新的情景，都是一个具有相同性质的一个子问题的一个方式， 所以用递归的方式去解决是最为容易的。
那么我们还要通过枚举的方式，
來找到从起点到终点的路径。也就是说我们要看，如何能够
去找，譬如说，如果说我们走不通了，那么我们就需要去换一个方向，
那么我们每一个点上都有四个方向，那么如果四个方向都走不通，
那么我们就需要去回溯到上一步的这个地方，
然后换一个地方去走，所以呢，依次的这个选择下去，最终呢，就可以找到相应的终点。
此外的话呢，要注意一点，在这一个题目当中，
计算路径的数目呢，是指，经过的这个，
就通常来讲迷宫问题是指说经过的这个格子的数目，
而在我们当前的这个问题当中呢，
这个所谓的路径，是指包含了水平或者竖直的直线段，
那么这样会注意一下就是，我们需要去纪录，每一步走的方向。
也就是说上一步走的方向，若跟当前这一步走的方向相同的时候，
那么我们做递归搜索的时候呢，这个路径的数呢本身是不变，
也就是说他不一定只是，他不是考虑通过这个格子的数目，
而是考虑方向。如果这个方向就是说方向一直不变，即便我穿过一系列
这个格子，那么它仍然是1，但是如果一旦方向发生变化的时候呢，那么路径呢这个通过了这个
呃线段的数目就会自然地加1。
那么还要注意的就是，因为我们路径本身呢只包含了这个
水平或者竖直的线段 但是呢我们路，路径虽然不能够穿过其中的游戏卡片，但是允许你呢
通过这个穿，离开矩形板，也就是说在外部来进行连接。
所以呢为了程序设计的方便，我们需要在原先这个
矩形板的外圈再进行增补一圈，也就是说我们
在外面添上一圈格子
那么有了这样的一个增添的方式，类似我们之前在枚举里面讲的那个
呃熄灯问题。我们通过这样一圈的增加之后呢，就可以有效地保证我
在处理的时候，是跟这个，不管它是在边界上，还是在 这个内部，都是通过一样的方式来进行处理的。
那么接着的话呢，我们考虑，我们去
描述这个迷宫本身，啊也就是说我们这个当前的这个矩形板
那么我们需要去设置一个二维数组的话，在这里边称为叫做board，那么这个
二维数组呢中间呢存放了，分别存放了空格和X,啊
对于没有游戏片，卡片的地方呢，我们就存了空格，有卡片的地方呢，就存X。
此外的话呢，我们在搜索的过程中间，我们需要有一个记录 啊记录说当前的这个格子是否已经走过了，啊
那么我们就有一个二维数组mark，用来标记说我的这个格子
是否已经走过，如果呢没有走过呢就是0，走过了就是1。
此外呢，我们还有几个全局变量，比如说我们有一个记录这个
最优步数，最少这个步数的这个值，啊，那么它用来记录从起点
到终点，最少的这个路径数。
那么此外的话还有这个关于矩形板的这个宽和高。
另外呢，因为它是一个迷宫问题，啊，它涉及到一个
搜索方向的问题，所以呢我们会看到，我们这个每一步的这个走法 我们通，也通过一个二维数组来描述，啊
我们看到呢，这个如果我们去设计一个当前的位置称为叫now_x和now_y的话呢 那么我们在当前这个点上
如果它分别向这个东西南北，是吧，东，西，南，北
南北来进行走，那时候的话呢，我们会看到它呢实际上呢就是
通过去累加一个我们在这里
列举好了一个to数组中间的一个元素，是吧？也就是让它的这个
横坐标或者纵坐标进行这个变化，那么如果它是这个向
东走，那么我们就让它的这个y
累加1，啊；如果是这个向 南走，那么我们就让它的这个
x呢来加1。
完了之后的话呢，我们就看到，如果是这个向西走呢，就让它的这个
y值来减1；如果是北走呢，我们就让它这个
呃，x减1，啊反正有了这样的一个呃数组的定义之后呢，我们就可以进一步地
去描述说我的x,y下一个位置是什么，是吧
比如说我们如果定义好这个方向
是i,啊定义好这个方向是i 那么这个时候的话呢，我就可以去利用我当前的这个
to数组当中的取它的第1为，啊
让它等于i,然后分别让它的这个x坐标和
x值和y值呢去累加上其相应的这个
to数组当中第i行中间的第1个元素和第2个元素。
那么就可以知道说我的x,y这两个值是如何变化的。
那么别忘了就是你要去相应的记录一下你的这个方向值
因为你要去考虑下一步走的时候和前一步的方向是否一致
来进行进一步的这个是否更新，呃 这个最小步数的一个判断。
那么此外的话呢，我们还要最后去判断一点呢就是我们
要去考虑这个新位置，也就是我们搜索的这个路径走到的这个新位置本身是否有效，是吧？
那么首先需要考虑的第1点就是你产生了这个新的位置x和y
它是在边界之内的，是吧？也就是说你不能够超出我的这个矩形板的范围
所以呢，我们会看到x必须是大于-1，小于w+2
啊y呢必须是大于-1，小于h+2。
第2个呢，第2个条件是说本身这个位置
是没有游戏板，啊我们说路径是不允许穿过游戏板的
并且呢是没有走过的，啊我们不能循环地去走，所以呢我们呢要注意这个条件呢是说我们的这个
游戏板的这个对应的这个位置呢它是空的
并且呢是，如果去查找，这个mark的那个数组，它也是等于false。
第3个条件呢是说我们已经到达了终点，啊也就是
如果我发现我这个时候的x和y就是我所希望的那个目标值
并且呢相应的这个板子上呢
中间的这个游戏卡片呢也就是我对应的填的这个x。
那么有了这样的3点之后，我们会看到，那么x y的有效终止的条件呢就是
当你是满足，首先是T1与上
T2或者T3，啊也就是说要么达到了这个终止条件，要么本身它
穿过的是一条有效的路径是吧？这两，二者之一都可以保证
新生成的这个x和y呢是一个有效的一个位置。
那么我们这个程序的最关键的实现呢就在于
这个路径搜索的过程中间，为了使用的递归函数，啊这个递归函数呢
它会用在每一个当前路径所在点的位置上，如何进行下一步搜索
这样的一个递归的一个问题。
那么这个递归函数呢，它包含的参数呢，首先由我当前这个
路径所在位置的x和y值，啊横纵坐标
以及我的目标终点的游戏卡片所在的这个位置，end_x和end_y
以及呢我到目前为止所保留的这个
通过的这个，路径通过的这个，呃
一共的线段数，啊也就是我这个路径包含的这个 啊数，数目。
最后呢，就是我还要去记录我的这条路径所，目前走的这个方向，啊int(f)
所以呢，我们会看到，这个
这几个参数本身，它实际上就描述了我的这个路径的特点 以及最后利用f来判断说它是否
跟上一步到达now_x,now_y的这个方向是一致，也就是说是否要用来更新我的这个step数。
我们来看一下具体的这个参考程序，啊在我们这个程序当中呢
我们当然首先呢定义好了一个矩形的这个板子，啊矩形的这个板子，那么它是一个
二维数组，那么这个二维数组呢，它中间就要去存放我相应的这个是空格还是
X；接着呢我定义了一系列的这个全局的变量，以及呢用这个
to这样的一个数组，二维数组，啊保存了相应的这个
沿不同方向走所定义的这个方向。
最后呢，就是一个mark数组，我们说呢用来去标记说我当前的这个游戏卡片是否
有，或者这个当前的这个空格是否被走到了，那我们接着看
这个我们刚才提到关于递归中间的这个，最重要的这个函数Search
这个函数的实现。啊，那么在Search当中呢，我们首先第一步就应该去判断说
我当前走过的这个路径已经通过了这个step数，它是否大于我已经
保存的目前知道的这个，呃minstep，也就是说，如果当前这个路径的数量
已经大于我保存的这个minstep这样的一个临时量
那么就说明我目前走过的这条路径不是连接这两个游戏卡片中间最优的路径，是吧？
在这种情况下呢就直接return，啊，那么这实际上是一个去简化我的这个搜索的过程的这样的一个方式。
那么如果呢，本身它不是大于的 那么我们接着看，那么也就是说我搜索下一步要走到的这个位置now_x和now，now_y
呢，它是否又和我的这个目标的这个游戏卡片是一致的，它是否等于end_x和end_y
那么如果它已经到达了终点，啊也就是说我通过这一步走，它已经到达终点的话呢，那么我要去看一看说
这个时候，ministep
是不是大于我 这条路径所通过的这个数量。如果呢 step
当前的这条 路径和 step 呢更小，我就用它来更新我的 ministep.
那么如果它既不是说需要
提前终止的路径，也没有走到这个目标的游戏卡片的这个位置上，
那么我们就要看，我们对于当前的这个，所出的这个路径。
我们就要去枚举它下一步所走的方向。啊，我们说了，一共有四种，让 i 呢从0一直呢，到3。
那么这四种方向呢，我们可以去， 依次地去计算其相应的
x 和 y 的值。也就是说用now_x 和 now_y
去计算一下说，看一看它通过下一步的这样的一个走序，所得到的这个新位置的值。
完了之后呢我们就要去判断一下，说，看一看这个计算出来的
x 和 y 是否满足我们刚才提到的这个
T1&&(T2/T3)这样的一个，
啊，终止条件。就是说它是否有超出矩形板的位置。或者是，它有，
这个穿过某个卡片。以及它是这个，
啊，达到目标卡片的所在的位置上。这样的一个，终止的条件。
那么呢如果呢这个，新的这个位置是有效的，x和y是有效的，
那么我们就将其相应的位置 在 mark 举证上呢，置为true.
比如说标记一下这个新位置是一个有效位。
然后呢，接着呢我们就要去看什么呢。我们就要去看
它如果是和上一步，就是说我当前的这个方向 i,
我不是枚举了每一个走的方向吗？如果这个 i 本身适合f,
你就全当那这个参数它保存的是上一次走过的方向。如果是一致的话， 那么我就去叠带地去调用
search， 去调用 search，这个时候我们会看到，
传入了这个新的 now_x 就变成了x, now_y 就是 y, 啊。
这个相应的这个step呢保持不变，然后去传递 i 这个方向。
那么如果说 f 和 i 呢， 方向是不一致的，不等，那么就走
else, 象让它去 search x, y 作为参数，end_x, end_y.
注意，是step加1.
然后去更新这个 i 作为方向指。
那么我们可以看到，也就是说，我不论是走这四个方向中间的哪一个，
那么，我都要去 判断一下，通过这一步走寻之后得到的这一个x和
y 是否有效。
如果是有效的，那么我就进一步去判断它的方向是否跟上一步的 f 传达的参数是一致的。
如果是一致的，就让它去调用前面这个search, 递归的。如果呢，
不一致，就让它的这个递归调用 search 的函数中间的这个step的参数要加1.
那么如果说我去， search
了一圈，我当前这一圈枚举的这个新的一步走下去呢，最后呢， 都导致，啊，
无解。也就是说我新的这一步走下去之后是不可以,这个方向是走不下去的话呢，那么我就要
去回朔，啊，回来, 回朔回来。我就要把相应我刚才已经置为true 的
mark 这个值， 置为是false,也就是说,说明这个位置是
不曾走过的，来回到原先的这个位置重新来进行计算。
那么对于这个程序的main 函数来讲，其实是很简单，
它主要就是用来去处理这个数据的输入输出，啊。我们首先去读入w和h
完了之后呢，如果w和h是零，这个程序就结束，啊。
否则的话呢，这个board number就让它＋＋ 完了之后我们就让它去输出，我对应处理的是第几个矩形板。
那么有了这个矩形板之后呢，我就每一次getchar读进来 这个相应的这个矩形板中间存放的是空格还是叉啊。
之后的话要注意就是我们需要在这个矩形板的外圈
去增加一圈格子。从而保证呢我每一次搜索的时候都可以去调用我的这个递归的这个search递归函数。
之后呢，那么我们就相应地，把这个我们要判断的游戏卡依次地
存放在我当前的这个begin_x begin_y和 end_x end_y
这样的一个 值当中。之后呢我们就可以让这个
count ＋＋，我们让这个搜寻的这个技术呢
开始。
那么注意一开始我们可以让这个ministep设置为一个很大的值。
也就是说所有的这个路径呢都是满足，每一次更新都可以小于这个ministep.
之后我们就可以进行这个递归的搜索的这样的一个方式，啊。
注意在这个递归搜索当中的话呢我们首先呢是从这个开始的这个卡片开始，啊
所以相应的step呢也是零。方向呢就是也不进行标记。
那么完了之后的话呢我们就依次地去调用刚才的那个search函数。从而呢最终实现
这个，不断递归，去按照，沿不同方向进行搜索这样的一个工作。
那么，这时候如果说你的ministep呢本身是小于原来这个值就
说明我的这个ministep被我的当前的路径所更新了的话那么我们就去输出相应的这个
count值，和ministep，就是说我们去输出一下对于我是计算了哪一个
这个对应的这个游戏卡片顿儿。以及它相应的这条路径所通过的这个线段数。
否则的话呢，我们就会输出对应的这个 游戏卡片顿呢是没有找到合适的路径的。
那么这就是关于这个小游戏这样的一个题目当中 程序的一个基本的实现。
我们会看到呢，对于这个题目而言呢。其实最重要的地方呢就在于递归条件当中
对于迷宫问题问题自相似性，实际上是利用这个递归的这个方式来进行实现的。
那么，每一步的探测。就是说你走到当前的这个块儿上的时候，
你去找寻哪个方向来进行走 是问题的关键。而每一步的这个，进行探测的
时候的方式呢是相同的，所以从而使得你可以利用递归的方式
来进行实现，啊。那么，我们在设计这个search的这个函数的时候呢，注意就是，
我们始终让它先朝着一个方向走下去。如果走不通呢，则换
方向来走。那么如果四个方向都走不通的话呢， 则需要回到上一步，啊。回到上一步，换一个方向去走。
然后依次走下去，直到走道终点为止。所以这就是我们在这个程序当中有一个这个，
啊，需要，有些时候需要去回朔。将原来mark的那个
二维举证呢要重新置为false的一个原因就是我们让它回朔回去。
本来已经置为true之后我们就不会回到当前的那个点上了。但是呢，因为我们发现
继续往下走呢已经没有合适的这个方式了。那么我们这个时候就要进行合适的回朔来计算。
那么最后一点就是要注意。这个路径的这个计算呢，它实际上呢是要沿某个方向的。相同的时候呢，
如果上一步的方向和这一步的方向相同的时候呢，那么这个路径数是不变的。否则呢会需要去加 1.
所以这就是关于这个小游戏的递归实现的一个问题的一个求解。
