递归回溯搜索优秀PPT.ppt

导入练习v例1，N!。N!=N*(N-1)!，因此求N!转化为求(N-1)!。这就是一个递归的描述。例2：裴波那契数列的定义：递归的概念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个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。vprogramhannuota;vvarvn:integer;vprocedurehnt(a,b,c,n:integer);vbeginvifn=1thenwriteln(a,-,c)velsebeginhnt(a,c,b,n-1);writeln(a,-,c);hnt(b,a,c,n-1);end;vend;vbeginvwrite(pleaseinputn:);vread(n);vhnt(1,2,3,n);vend.汉诺塔问题的递推解法v设设f(n)为为n 个盘子从个盘子从1柱移到柱移到3柱所需移动的最少盘次。柱所需移动的最少盘次。当当n=1时，时，f(1)=1。v当当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步得出总共移动盘子的次数为：步得出总共移动盘子的次数为：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，请输出一种解，若无解输出“NOANSWER”。练习2v快速排序vvara:array1.10000oflongint;vn,i:longint;vprocedureqsort(s,t:longint);vvari,j,x:longint;vbeginvi:=s;j:=t;x:=ai;vwhile(ij)dobeginvwhile(ij)and(x=aj)dodec(j);vai:=aj;vwhile(ij)and(ai=x)doinc(i);vaj:=ai;vend;vai:=x;vifsi-1thenqsort(s,i-1);vifj+1nthen输出结果velseforj:=下界to上界dovbeginvxi:=hj;vif可行满足限界函数和约束条件thenbegin置值；try(i+1);取消置值；end;vend;vend;v例4：N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解全部的摆放方法。八皇后的两组解v分析：v由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行摸索和订正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的摸索方法是相同的，因此完全可以接受递归的方法来处理。v下面是放置第I个皇后的的递归算法：vProcedureTry(I:integer)；v搜寻第I行皇后的位置vvarvj:integer;vbeginvifI=n+1then输出方案；vforj:=1tondovif皇后能放在第I行第J列的位置thenbeginv放置第I个皇后；v对放置皇后的位置进行标记；vTry（I+1）v对放置皇后的位置释放标记；vEnd;vEnd;vN皇后问题的递归算法的程序如下：vprogramN_Queens;vconstvMaxN=100;最多皇后数vvarvA:array1.MaxNofBoolean;同列-竖线被限制标记vB:array2.MaxN*2ofBoolean;i+j和相等-左下到右上斜线被限制标记vC:array1MaxN.MaxN1ofBoolean;j-i差相等-左上到右下斜线被限制标记vX:array1.MaxNofInteger;记录皇后的解vTotal:Longint;解的总数vN:Integer;皇后个数vprocedureOut;输出方案vvarvI:Integer;vbeginvInc(Total);Write(Total:3,:);vforI:=1toNdoWrite(XI:3);vWriteln;vend;vprocedureTry(I:Integer);v搜寻第I个皇后的可行位置vvarvJ:Integer;vbeginvifI=N+1thenOut;N个皇后都放置完毕，则输出解vforJ:=1toNdovifAJandBJ+IandCJIthenbeginvXI:=J;vAJ:=False;vBJ+I:=False;vCJI:=False;vTry(I+1);搜寻下一皇后的位置vAJ:=True;vBJ+I:=True;vCJI:=True;vend;vend;vbeginvWrite(QueensNumbers=);vReadln(N);vFillChar(A,Sizeof(A),True);vFillChar(B,Sizeof(B),True);vFillChar(C,Sizeof(C),True);vTry(1);vWriteln(Total=,Total);vend.v上机练习题v1.添加自然数问题。（add.pas）v要求找出具有下列性质的数的个数(包含输入的自然数n)：v先输入一个自然数n(n=500),然后对此自然数依据如下方法进行处理:v.不作任何处理;v.在它的左边加上一个自然数,但该自然数不能超过原数的一半;v.加上数后,接着按此规则进行处理,直到不能再加自然数为止.v输入文件：add.in,一行，n的值。v输出文件：add.out，一行，依据规则可产生的自然数个数。v样例：v输入文件：v6v满足条件的数为6v16v26v126v36v136v输出文件v6vvarn,i:integer;vs:real;vprocedureqiu(x:integer);vvark:integer;vbeginvifx0thenvbeginvs:=s+1;vfork:=1toxdiv2doqiu(k)vendvend;vbeginvreadln(n);vs:=0;vqiu(n);vwriteln(s)vend.v2.跳马问题。（jump.pas）v在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。v输出文件：jump.out，一行，路径条数。vprogramjump;vvarvh:array-1.7,-1.7ofinteger;va,b:array1.8ofinteger;vi,j,num:integer;vprocedureprint;vvari,j:integer;vbeginvnum:=num+1;vifnum=5thenvbeginvfori:=1to5dovbeginvforj:=1to5dowrite(hi,j:4);vwriteln;vend;vwriteln;vend;vend;vvproceduretry(x,y,i:integer);vvarj,u,v:integer;vbeginvforj:=1to8dovbeginvu:=x+aj;vv:=y+bj;vifhu,v=0thenvbeginhu,v:=i;vifi=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:array1.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;dx8:=-1;dy8:=-1;读入数据读入数据:坐标坐标procedurereaddata;beginassign(input,a.in);reset(input);readln(n);fori:=1tondoforj:=1tondobeginread(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)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时，输出：11122122应用之一：排列组合问题v2.由键盘输入正整数N，生成1到N的不重复全排列。（1=N=9）例如：输入2时，输出：1221v3.输出从N个元素中选取M个元素的各种排列（1N、M9）。v例如：N=3vM=2v输出：v12v13v21v23v31v32v4.输出从N个元素中选取M个元素的各种组合（1N、M9）。v例如：N=3vM=2v输出：v12v13v23v5.已知两个自然数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（135）（136）（146）（246）v共有4种取法。v提示：（135）和（315）属于一种取法。v输入（b.in）：一行，n和k，中间用空格隔开。v输出（b.out）：一行，取法的种数。v样例：v输入：63v输出：4过河卒v棋盘上A点有一个过河卒，须要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和全部跳动一步可达的点称为对方马的限制点。因此称之为“马拦过河卒”。v棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数)，同样马的位置坐标是须要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。v【输入】v一行四个数据，分别表示B点坐标和马的坐标。v【输出】v一个数据，表示全部的路径条数。v【样例输入】v6632v【样例输出1】v17v题目分析：v本题是一道典型的深度优先搜寻题目。v须要处理好的细微环节有：v1.读入“马”的坐标，限制好八个方向。v2.在（n,m）棋盘上限制好“马”所能跳出的边界。v3.按向下、向右两个方向搜寻，只要当前没有走到（n,m）点且下一节点为访问过，则搜寻。vprogramzu;vconstvdx:array1.8ofshortint=(2,1,-1,-2,-2,-1,1,2);vdy:array1.8ofshortint=(1,2,2,1,-1,-2,-2,-1);vvarn,m,x,y:longint;vg:array-2.22,-2.22ofboolean;vi,ans:longint;vprocedurego(a,b:longint);vbeginvif(a=n)and(b=m)theninc(ans)elsebeginvif(a+1=n)andga+1,b=truevthengo(a+1,b);vif(b+1=m)andga,b+1=truevthengo(a,b+1);vend;vend;vbeginvassign(input,zu.in);reset(input);vassign(output,zu.out);rewrite(output);vreadln(n,m,x,y);vfillchar(g,sizeof(g),true);vgx,y:=false;vfori:=1to8dovgx+dxi,y+dyi:=false;vans:=0;vgo(0,0);vwriteln(ans);vclose(input);close(output);vend.