递归法和回溯法

《递归法和回溯法》由会员分享，可在线阅读，更多相关《递归法和回溯法（17页珍藏版）》请在金锄头文库上搜索。

1、递归法和回溯法递归法和回溯法递归法和回溯法有人说，回溯实际上是递归的展开，但实际上。两者的指导思想并不一致。打个比方吧，递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有 3 条路，将军命令 3 个小队分别去探哪条路能到出口，3 个小队沿着 3 条路分别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路只要人手足够（对照而言，就是计算机的堆栈足够） ，最后必将有人找到出口，从这人开始只要层层上报直属领导，最后，将军将得到一条通路。所不同的是，计算机的递归法是把这个并行过程串行化了。而回溯法则是一个人走迷宫的思维模拟他只能寄希望于自己的记忆力，如果他没有办法在分岔口留下标记

2、（电视里一演到什么迷宫寻宝，总有恶人去改好人的标记） 。想到这里突然有点明白为什么都喜欢递归了，他能够满足人心最底层的虚荣难道你不觉得使用递归就象那个分派士兵的将军吗？想想汉诺塔的解法，也有这个倾向， “你们把上面的 N1 个拿走，我就能把下面的挪过去，然后你们在把那 N1 个搬过来” 。笑谈，切勿当真。这两种方法的例程，我不给出了，网上很多。我只想对书上的递归解法发表点看法，因为书上的解法有偷梁换柱的嫌疑迷宫的储存不是用的二维数组，居然直接用岔路口之间的连接表示的简直是人为的降低了问题的难度。实际上，如果把迷宫抽象成（岔路口）点的连接，迷宫就变成了一个“图” ，求解入口到出口的路线，完全可以

3、用图的遍历算法来解决，只要从入口 DFS 到出口就可以了；然而，从二维数组表示的迷宫转化为图是个很复杂的过程。并且这种转化，实际上就是没走迷宫之前就知道了迷宫的结构，显然是不合理的。对此，我只能说这是为了递归而递归，然后还自己给自己开绿灯。但迷宫并不是只能用上面的方法来走，前提是，迷宫只要走出去就可以了，不需要找出一条可能上的最短路线确实，迷宫只是前进中的障碍，一旦走通了，没人走第二遍。下面的方法是一位游戏玩家提出来的，既不需要递归，也不需要栈来回溯玩游戏还是有收获的。另一种解法请注意我在迷宫中用粗线描出的路线，实际上，在迷宫中，只要从入口始终沿着一边的墙走，就一定能走到出口，那位玩家称之为“

4、靠一边走”如果你不把迷宫的通路看成一条线，而是一个有面积的图形，很快你就知道为什么。编程实现起来也很简单。下面的程序在 TC2 中编译，不能在 VC6 中编译为了动态的表现人的移动情况，使用了 gotoxy()，VC6 是没有这个函数的，而且堆砌迷宫的 219 号字符是不能在使用中文页码的操作系统的 32 位的console 程序显示出来的。如果要在 VC6 中实现 gotoxy()的功能还得用 API，为了一个简单的程序没有必要，所以，就用 TC2 写了，突然换到 C 语言还有点不适应。#include typedef struct hero int x,y,face; HERO;void

5、set_hero(HERO* h,int x,int y,int face)h-x=x;h-y=y;h-face=face;void go(HERO* h)if(h-face%2) h-x+=2-h-face;else h-y+=h-face-1;void goleft(HERO* h)if(h-face%2) h-y+=h-face-2;else h-x+=h-face-1;void turnleft(HERO* h)h-face=(h-face+3)%4;void turnright(HERO* h)h-face=(h-face+1)%4;void print_hero(HERO* h,

6、int b)gotoxy(h-x + 1, h-y + 1);if (b)switch (h-face)case 0: printf(“%c“, 24); break;case 1: printf(“%c“, 16); break;case 2: printf(“%c“, 25); break;case 3: printf(“%c“, 27); break;default: break;else printf(“ “);int maze1010 =0, 0, 0, 1, 0, 0, 0, 1, 0, 0,1, 0, 1, 1, 0, 1, 1, 1, 1, 0,1, 0, 0, 0, 0, 0

7、, 0, 0, 0, 0,0, 0, 1, 0, 1, 1, 0, 1, 1, 1,0, 0, 1, 0, 1, 1, 0, 0, 0, 1,1, 0, 1, 0, 1, 1, 0, 1, 0, 1,0, 0, 1, 0, 1, 1, 0, 1, 0, 1,0, 1, 1, 0, 0, 0, 0, 1, 0, 1,0, 0, 0, 0, 1, 0, 1, 1, 0, 1,0, 1, 1, 1, 1, 0, 0, 0, 0, 0;void print_maze()int i, j;for (i = 0; i = 0 goleft(if (h-x = 0 if (t.x = 0 class Nee

8、dlepublic:Needle() a.push_back(100); /每一个柱子都有一个底座void push(int n) a.push_back(n); int top() return a.back(); int pop() int n = a.back(); a.pop_back(); return n; int movenum(int n) int i = 1;while (ai n) i+; return a.size() - i; int size() return a.size(); int operator (int n) return an; private:vect

9、or a;void Hanoi(int n)Needle needle3, ns;/3 个柱子，ns 是转换柱子时的保存栈，借用了 Needle 的栈结构int source = 0, target, target_m = 2, disk, m = n; for (int i = n; i 0; i-) needle0.push(i);/在 A 柱上放 n 个盘子while (n)/问题规模为 n，开始搬动if (!m) source = ns.pop(); target_m = ns.pop();m = needlesource.movenum(ns.pop(); /障碍盘子搬走后，回到原来

10、的当前柱if (m % 2) target = target_m; else target = 3 - source - target_m;/规律 1 的实现if (needlesource.top() needletarget.top()/当前柱顶端盘子可以搬动时，移动盘子disk = needlesource.top();m-;cout disk “ move “ (char)(source + 0x41) “ to “ (char)(target + 0x41) endl;/显示搬动过程needletarget.push(needlesource.pop();/在目标柱上面放盘子if (

11、disk = n) source = 1 - source; target_m = 2; m = -n; 规律 3 的实现else/规律 2 的实现ns.push(needlesourceneedlesource.size() - m);ns.push(target_m); ns.push(source);m = needletarget.movenum(needlesource.top();target_m = 3 - source - target; source = target;这个算法实现比递归算法复杂了很多（递归算法在网上、书上随便都可以找到） ，而且还慢很多，似乎是多余的，然而，

12、这是有现实意义的。我不知道现在还在搬 64 个盘子的僧人是怎么搬的，不过我猜想一定不是先递归到 1 个盘子，然后再搬等递归出来，估计胡子一打把了（能不能在人世还两说） 。我们一定是马上决定下一步怎么搬，就如我上面写的那样，这才是人的正常思维，而用递归来思考，想出来怎么搬的时候，黄瓜菜都凉了。正像我们做事的方法，虽然我今生今世完不成这项事业，但我一定要为后人完成我能完成的，而不是在那空想后人应该怎么完成如果达不到最终的结果，那也一定保证向正确的方向前进，而不是呆在原地空想。由此看出，计算机编程实际上和正常的做事步骤的差距还是很大的我们的做事步骤如果直接用计算机来实现的话，其实并不能最优，原因就是，实际中的相关性在计算机中可能并不存在比如人脑的逆推深度是有限的，而计算机要比人脑深很多，论记忆的准确性，计算机要比人脑强很多。这也导致了一个普通的程序员和一个资深的程序员写的算法的速度常常有天壤之别。因为，后者知道计算机喜欢怎么思考。