递归回溯搜索教学教材

1、递归回溯搜索递归的概念v由函数或者过程调用引起。v一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。 v例3：汉诺塔问题：有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。输出总共移动的次数。ABCv分析：在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。v

2、program hannuota;vvarvn:integer;vprocedure hnt(a,b,c,n:integer);vbeginv if n=1 then writeln(a,-,c)v else begin hnt(a,c,b,n-1);writeln(a,-,c);hnt(b,a,c,n-1);end;vend;vbeginvwrite(please input n:);vread(n);vhnt(1,2,3,n);vend.汉诺塔问题的递推解法v设设f(n)为为n 个盘子从个盘子从1柱移到柱移到3柱所需移动的最少盘次。柱所需移动的最少盘次。当当n=1时，时，f(1)=1。v当

3、当n=2时，时，f(2)=3。v以此类推，当以此类推，当1柱上有柱上有n(n2)个盘子时，我们可以利用下列个盘子时，我们可以利用下列步骤：步骤：v第一步：先借助第一步：先借助3柱把柱把1柱上面的柱上面的n-1个盘子移动到个盘子移动到2柱上，柱上，所需的移动次数为所需的移动次数为f(n-1)。v第二步：然后再把第二步：然后再把1柱最下面的一个盘子移动到柱最下面的一个盘子移动到3柱上，只柱上，只需要需要1次盘子。次盘子。v第三步：再借助第三步：再借助1柱把柱把2柱上的柱上的n-1个盘子移动到个盘子移动到3上，所需上，所需的移动次数为的移动次数为f(n-1)。v由以上由以上3步得出总共移动盘子的次数

4、为：步得出总共移动盘子的次数为：f(n-1)+1+ f(n-1)。v 所以：所以：f(n)=2 f(n-1)+1 现在就可以用递推现在就可以用递推做了做了vf(1)=1vf(2)=3vf(3)=7vf(4)=15f(n)= 2n-1现在可以用数学方法做了现在可以用数学方法做了练习1：简单背包问题。v有一个背包容量为s，现有n件物品，重量分别为s1、s2、s3。Si（1=i=n）,假设si均为正数，从这n件物品中选择若干件物品放入背包，使得放入总重量恰好为s，请输出一种解，若无解输出“NO ANSWER”。练习2v快速排序vvar a:array1.10000 of longint;vn,i:l

5、ongint;vprocedure qsort(s,t:longint);vvar i,j,x:longint;vbeginvi:=s;j:=t;x:=ai;vwhile (ij) do beginv while (ij) and (x=aj) do dec(j);v ai:=aj;v while (ij) and (ai=x) do inc(i);v aj:=ai;v end;vai:=x;vif si-1 then qsort(s,i-1);vif j+1n then 输出结果velse for j:=下界 to 上界 dovbeginvxi:=hj;vif 可行满足限界函数和约束条件 t

6、hen begin 置值；try(i+1); 取消置值；end;vend;vend; v例4：N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。八皇后的两组解v分析：v由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。v下面是放置第I个皇后的的递归算法：vProcedure Try(I:integer)；v搜索第I行皇后的位置vvarv j:i

7、nteger;vbeginv if I=n+1 then 输出方案；v for j:=1 to n do v if 皇后能放在第I行第J列的位置 then beginv 放置第I个皇后；v 对放置皇后的位置进行标记；v Try（I+1） v 对放置皇后的位置释放标记；vEnd;vEnd;vN皇后问题的递归算法的程序如下：vprogram N_Queens;v constv MaxN = 100;最多皇后数v varv A:array 1.MaxN of Boolean; 同列-竖线被控制标记v B:array 2.MaxN * 2 of Boolean;i+j和相等-左下到右上斜线被控制标记v

8、 C:array 1MaxN.MaxN1 of Boolean;j-i差相等-左上到右下斜线被控制标记v X: array 1 . MaxN of Integer; 记录皇后的解v Total: Longint;解的总数v N: Integer;皇后个数v procedure Out;输出方案v varv I: Integer;v beginv Inc(Total); Write(Total: 3, :);v for I := 1 to N do Write(XI: 3);v Writeln;v end;vprocedure Try(I: Integer);v搜索第I个皇后的可行位置v var

9、v J: Integer;v beginv if I = N + 1 then Out; N个皇后都放置完毕，则输出解v for J := 1 to N dov if AJ and BJ + I and CJ I then beginv XI := J;v AJ := False;v BJ + I := False;v CJ I := False;v Try(I + 1);搜索下一皇后的位置v AJ := True;v BJ + I := True;v CJ I := True;v end;v end;vbeginv Write(Queens Numbers = );v Readln(N);v

10、 FillChar(A, Sizeof(A), True);v FillChar(B, Sizeof(B), True);v FillChar(C, Sizeof(C), True);v Try(1);v Writeln(Total = , Total);v end.v上机练习题v1.添加自然数问题。（add.pas） v要求找出具有下列性质的数的个数(包含输入的自然数n)：v先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理:v. 不作任何处理;v. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;v. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.v 输

11、入文件：add.in,一行，n的值。v输出文件：add.out，一行，按照规则可产生的自然数个数。v样例：v输入文件：v6v满足条件的数为 6 v 16v 26v 126v 36v 136v输出文件v6 vvar n,i:integer;v s:real;vprocedure qiu(x:integer);vvar k:integer;vbeginv if x0 thenv beginv s:=s+1;v for k:=1 to x div 2 do qiu(k)v endvend;vbeginv readln(n);v s:=0;v qiu(n);v writeln(s)vend.v2. 跳

12、马问题。（jump.pas）v在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。v输出文件：jump.out，一行，路径条数。 vprogram jump;v varv h:array-1.7,-1.7 of integer;v a,b:array1.8 of integer;v i,j,num:integer;v procedure print;v var i,j:integer;v beginv num:=num+1;v if num=5 thenv beginv for i:=1 to 5 dov beg

13、inv for j:=1 to 5 do write(hi,j:4);v writeln;v end;v writeln;v end; v end;v vprocedure try(x,y,i:integer);v var j,u,v:integer;v beginv for j:=1 to 8 dov beginv u:=x+aj;v v:=y+bj;v if hu,v=0 thenv begin hu,v:=i;v if i=1)and(i=1)and(j(2,1)-(3,1)-(2,2)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)分析分析: a:a

14、rray1.maxn,1.maxnof 0.1; 记录迷宫坐标记录迷宫坐标 c:array1.maxn,1.maxnof 0.1; 访问标志访问标志:0:没走没走;1:已走已走 b:array0.maxn*maxn of integer;记录路径方向记录路径方向 dx,dy:array1.8of integer; 方向位移方向位移 8个方向的位移个方向的位移: dx1:=0; dy1:=-1; dx2:=1; dy2:=-1; dx3:=1; dy3:=0; dx4:=1; dy4:=1; dx5:=0; dy5:=1; dx6:=-1; dy6:=1; dx7:=-1; dy7:=0; dx

15、8:=-1; dy8:=-1;读入数据读入数据: 坐标坐标procedure readdata;begin assign(input,a.in); reset(input); readln(n); for i:=1 to n do for j:=1 to n do begin read(aj,i);i:纵坐标;j:横坐标 cj,i:=0; end; close(input);递归算法递归算法:procedure try(i:integer);搜索第搜索第i步应到达的位置步应到达的位置 var k:integer; begin for k:=1 to 8 do begin if (x+dxk=1

16、)and(x+dxk=1)and(y+dyk,(,x,y,); end; writeln; end;主程序主程序:begin readdata; x:=1; y:=1; try(1);end.1.由键盘输入正整数N，生成1到N 的全排列。（1= N =9）例如：输入2时，输出：1 11 22 12 2 应用之一： 排列组合问题v2.由键盘输入正整数N，生成1到N 的不重复全排列。（1= N =9）例如：输入2时，输出：1 22 1v3.输出从N个元素中选取M个元素的各种排列（1N、M9）。v例如：N=3v M=2v输出：v1 2v1 3v2 1v2 3v3 1v3 2 v4.输出从N个元素中选

17、取M个元素的各种组合 （1N、M9）。v例如：N=3v M=2v输出：v1 2v1 3v2 3v5.已知两个自然数n和k（n,k=100），从1，2，n中任取k个数，要求所取的k个数中，任意两个数不能相差1。编程求有多少种取法。v如：n=6 ，k=3,，从1，2，3，4，5，6中取3个数，任意两个数不能相差1，取法如下：v（1 3 5） （1 3 6） （1 4 6） （2 4 6）v共有4种取法。v提示：（1 3 5）和（3 1 5）属于一种取法。v输入（输入（b.in）：）：一行，n和k，中间用空格隔开。v输出（输出（b.out）：）：一行，取法的种数。v样例：v输入：6 3v输出：4过河

18、卒v 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。v棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。v【输入】【输入】v 一行四个数据，分别表示B点坐标和马的坐标。 v【输出】【输出】v 一个数据，表示所有的路径条数。v【样例输入】【样例输入】v6 6 3 2v【样例输出【样例输出1】v17v题目分析：v本题是一道典型的深度优先搜索题目。v需要处理好的细节有：v1.读入“马”的坐标，控制好八个方向。v2.在（n,m）棋盘上控制好“马”所能跳出的边界。v3.按向下、向右两个方向搜索，只要当前没有走到（n,m）点且下一节点为访问过，则搜索。vprogram zu;vconstv dx:array1.8 of shortint=(2,1,-1,-2