2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 递归与回溯法.doc

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 递归与回溯法课题：递归与回溯目标：知识目标：递归概念与利用递归进行回溯能力目标：回溯算法的应用重点：回溯算法难点：回溯算法的理解板书示意：1） 递归的理解2） 利用递归回溯解决实际问题（例14、例15、例16、例17、例18）3） 利用回溯算法解决排列问题（例19）授课过程：什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。例如，我们可以这样定义N!，N!=N*(N-1)!，因此求N!转化为求 (N-1)!。这就是一个递归的描述。因此，可以编写如下递归程序：program Factorial; var N: Integer; T: Longint; function Fac(N: Integer): Longint; begin if N = 0 then Fac := 1 else Fac := N * Fac(N - 1) end; begin Write(N = ); Readln(N); T := Fac(N); Writeln(N! = ,T); end.图13 递归调用示例图图13展示了N=3的执行过程。由上述程序可以看出，递归是一个反复执行直到递归终止的过程。设一个未知函数f，用其自身构成的已知函数g来定义：为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2) ，上述这种用自身的简单情况来定义自己的方式称为递归定义。递归有如下特点：它直接或间接的调用了自己。一定要有递归终止的条件，这个条件通常称为边界条件。与递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递归边界值f(0)=a。然后返回调用函数。返回的过程中，中间结果相继出栈恢复，f(1)=g(1,a)f(2)=g(2,f(1)直至求出f(n)=g(n,f(n-1)。递归按其调用方式分直接递归递归过程P直接自己调用自己；间接递归即P包含另一过程D，而D又调用P；由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。递归算法适用的一般场合为： 数据的定义形式按递归定义。如裴波那契数列的定义： 对应的递归程序为function fib(n: Integer): Integer; begin if n = 0 then fib := 1 递归边界 else if n = 1 then fib := 2递归边界 else fib := fib(n 2) + fib(n 1);递归 end;这类递归问题可转化为递推算法，递归边界为递推的边界条件。例如上例转化为递推算法即为function fib(n: Integer): Integer; begin f0 := 1; f1 := 2;递推边界 for I := 2 to n do fI := fI 1 + fI 2; fib := f(n); end; 数据之间的关系（即数据结构）按递归定义。如树的遍历，图的搜索等。 问题解法按递归算法实现。例如回溯法等。对于和，可以用堆栈结构将其转换为非递归算法，以提高算法的效率以及减少内存空间的浪费。下面以经典的N皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别。例15：N皇后问题图14 八皇后的两组解在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个皇后和第I+1个皇后的试探方法是相同的，因此完全可以采用递归的方法来处理。下面是放置第I个皇后的的递归算法：Procedure Try(I:integer)；搜索第I行皇后的位置var j:integer;begin if I=n+1 then 输出方案； for j:=1 to n do if 皇后能放在第I行第J列的位置 then begin 放置第I个皇后； 对放置皇后的位置进行标记； Try（I+1） 对放置皇后的位置释放标记；End;End;N皇后问题的递归算法的程序如下：program N_Queens; const MaxN = 100;最多皇后数 var A:array 1.MaxN of Boolean; 竖线被控制标记 B:array 2.MaxN * 2 of Boolean; 左上到右下斜线被控制标记 C:array 1MaxN.MaxN1 of Boolean;左下到右上斜线被控制标记 X: array 1 . MaxN of Integer; 记录皇后的解 Total: Longint;解的总数 N: Integer;皇后个数 procedure Out;输出方案 var I: Integer; begin Inc(Total); Write(Total: 3, :); for I := 1 to N do Write(XI: 3); Writeln; end; procedure Try(I: Integer);搜索第I个皇后的可行位置 var J: Integer; begin if I = N + 1 then Out; N个皇后都放置完毕，则输出解 for J := 1 to N do if AJ and BJ + I and CJ I then begin XI := J; AJ := False; BJ + I := False; CJ I := False; Try(I + 1);搜索下一皇后的位置 AJ := True; BJ + I := True; CJ I := True; end; end; begin Write(Queens Numbers = ); Readln(N); FillChar(A, Sizeof(A), True); FillChar(B, Sizeof(B), True); FillChar(C, Sizeof(C), True); Try(1); Writeln(Total = , Total); end.N皇后问题的非递归算法的程序：program N_Queens;const MaxN = 100; 最多皇后数 var A:array 1.MaxN of Boolean; 竖线被控制标记 B:array 2.MaxN * 2 of Boolean; 左上到右下斜线被控制标记 C:array 1MaxN.MaxN1 of Boolean;左下到右上斜线被控制标记 X: array 1 . MaxN of Integer; 记录皇后的解 Total: Longint;解的总数 N: Integer;皇后个数procedure Out;输出方案 var I: Integer; begin Inc(Total); Write(Total: 3, :); for I := 1 to N do Write(XI: 3); Writeln; end;procedure Main;var K: Integer;begin X1 := 0; K := 1; while K > 0 do begin if XK <> 0 then begin AXK := True; BXK + K := True; CXK K := True; end; Inc(XK);while(XK<=N)and not(AXKand BXK+Kand CXKK)do Inc(XK);寻找一个可以放置的位置 if XK <= N then if K = N then Out else begin AXK := False; BXK + K := False; CXK K := False; Inc(K); XK := 0;继续放置下一个皇后 end else Dec(K);回溯 end;end; begin Write(Queens Number = ); Readln(N); FillChar(A, Sizeof(A), True); FillChar(B, Sizeof(B), True); FillChar(C, SizeofI, True); Main; Writeln(Total = , Total); end.使用递归可以使蕴含复杂关系的问题，结构变得简洁精炼。看看下面的例题。例16:新汉诺（hanoi）塔问题设有n各大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称之为初始状态。问题要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。移动时有如下要求： 一次只移动一个盘； 不允许把大盘移到小盘上边；输入：输入文件第1行是状态中圆盘总数；第24行是分别是初始状态中A、B、C柱上的圆盘个数和从上到下每个圆盘的编号；第57行是分别是目标状态A、B、C柱上的圆盘个数和从上到下每个圆盘的编号。输出：每行写一步的移动方案，格式为：Move I圆盘 form P柱 to Q柱。最后输出最少步数。输入样例（如图）：63 1 2 32 4 51 606 1 2 3 4 5 6 0样例所描述的状态如图15所示。图15 样例图=输出样例：分析：要从初始状态移动到目标状态，就是把每个圆盘分别移动到自己的目标状态。而问题的关键一步就是：首先考虑把编号最大的圆盘移动到自己的目标状态，而不是最小的，因为编号最大的圆盘移到目标位置之后就可以不再移动了，而在编号最大的圆盘未移到目标位置之前，编号小的圆盘可能还要移动，编号最大的圆盘一旦固定，对以后的移动将不会造成影响。根据上面的分析可设计如下过程 Move(K, W);表示把编号K的圆盘从当前所在柱移动到W柱的过程。下面对样例进行分析。图16 样例移动过程将6号盘移动到B柱，在此之前一定将经历如图16所示的状态要移动6号盘首先要把15号盘全部移开，也就是说，既不能移动到6号盘的初始立柱上，也不能移动到6号盘的目标立柱上。显然这里要将它们移动到A柱。然后再将6号盘移到位。此时状态如图17所示。图17 样例移动过程同时我们注意到：把15盘移动到目标的过程和将6号盘移动到B柱的过程，从形式上是一样的，只是盘的编号不同而已。显然这是个递归过程，可以采用递归法实现。算法设计如下:procedure Move(K, W)；编号K的圆盘从当前所在柱移动到W柱 begin if K号盘已经在W立柱上 then Exit；递归边界 for I := K - 1 downto 1 do Move(I, 过渡立柱);将编号小于K的盘都移到过渡立柱上去 输出当前移动方案; 将K号盘移到W立柱上; Inc(Step);累计步数 end;程序设计如下： program New_Hanoi; const Inp = hanoi.in; Outp = hanoi.out; MaxN = 64; 最大圆盘数 Stake: array 1 . 3 of Char =(A, B, C); type Tnode = array 1 . MaxN of Byte; 记录圆盘所处的立柱编号 var N: Integer;圆盘数 Now,当前状态 Goal: Tnode;目标状态 Step: Longint;步数 procedure Init;读入数据 var I, J, L, X: Integer; begin Assign(Input, Inp); Reset(Input); Readln(N);读入圆盘数 for I := 1 to 3 do begin 读入初始状态 Read(L); for J := 1 to L do begin Read(X); NowX := I; end; Readln; end; for I := 1 to 3 do begin 读入目标状态 Read(L); for J := 1 to L do begin Read(X); GoalX := I; end; Readln; end; Close(Input); end; procedure Main; varI: Integer; procedure Move(K: Integer; W: Byte); var I, J: Word; begin if NowK = W then Exit; 若达到目标，则退出 J := 6 NowK W;计算过渡立柱编号 for I := K 1 downto 1 do将圆盘移动到过渡立柱 Move(I, J); Write(Move,K, From ,StakeNowK, to ,StakeW);Writeln(.); NowK := W;将K号盘移动到目标位置 Inc(Step);累计步数 end; begin Assign(Output, Outp); Rewrite(Output); for I := N downto 1 do从大到小对每一个圆盘进行处理 Move(I, GoalI); Writeln(Step);输出总步数 Close(Output); end; Begin Init; Main; End.例17背包问题：已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi。若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大分析：本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为I（1I-1号物品不选），问题又可以转化为有N-I个物品（即第I+1N号物品），容量为M-Wi的子问题如此反复下去，然后在所有可行解中选一个效益最大的便可。另外，为了优化程序，我们定义一个函数如下：FI表示选第IN个物品能得到的总效益。不难推出：FN=PnFI=FI+1+Pi（I=1N-1）假设当前已选到第I号物品，如果当前搜索的效益值+FI+1的值仍然比当前的最优值小，则没有必要继续搜索下去。参考程序：Program exam17;Var W,P :Array 1.50 Of Integer; F :Array 1.50 Of Integer;Ou,Out :Array 1.50 Of Boolean; Ou，Out数组记录选择物品的具体方案 M :Integer; N,U :Byte; Ans,Now :Integer; Ans记录最优解，Now记录当前效益值Procedure Init; 初始化Var I :Byte;Begin Fillchar(Out,Sizeof(Out),False); Ou:=Out; Assign(Input,Input.txt); Reset(Input); Readln(M,N); For I:=1 To N Do Readln(WI,PI); Close(Input);读入数据 FN+1:=0; For I:=N Downto 1 Do FI:=FI+1+PI;计算函数F的值 Ans:=0; Now:=0;End;Procedure Search(I:Integer; J:Byte);递归求解Var K :Byte;Begin If Now+FJ<=Ans Then Exit; 如果没有必要搜索下去，则返回到上一级 If Now>Ans Then Begin 修改最优解 Ans:=Now; Out:=Ou; End; For K:=J To N Do 选取物品 If WK<=I Then Begin Now:=Now+PK; OuK:=True; Search(I-WK,K+1); Now:=Now-PK; OuK:=False; End;End;Begin Init; Search(M,1); Assign(Output,Output.txt);输出 Rewrite(Output); Writeln(Ans); For U:=1 To N Do If OutU Then Write(U, ); Writeln; Close(Output);End.例18寻找国都名给出一个矩阵及一些国都名：o k d u b l i n dublina l p g o c e v tokyor a s m u s m b londono s l o n d o n romey i b l g l r c bonn图18k r z u r i c h pariso a i b x m u z oslot p q g l a m v lima要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。输入：在文本文件input.txt中的第一行有一个整数M和N，表示该字符矩阵的长和宽。接下来就是M*N的字符矩阵。字符矩阵后有一个整数K，表示国家都名的个数，接下来的K行，每一行都是一个国都名。输出：在文本文件output.txt中共有K行，第I行写入第I个国都名的起始位置及方向。起始位置用坐标表示，方向定义见图18。如没有找到国都名，输出No found。分析：将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到，则输出相应的信息。在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了。参考程序如下：program exam18;Const Fx : Array1.8,1.2 Of Shortint 定义八个方向 =(0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1); max = 100; 最大字符矩阵 Finp = Input.Txt; 输入文件名 Fout = Output.Txt; 输出文件名VarA :Array0.max+1,0.max+1 of Char;为了节约边界条件的判断，故增加边界范围 B :Array1.max,1.max Of Boolean; 标志数组，标志已经搜索过的路径 S, W :String; N,M,I,J,K :Integer; printed :Boolean;Procedure Init;Var I,J :Integer; Begin Assign(Input,Finp); Reset(Input); 采用重定向的手段，将输入文件与标准输入联系起来，这样对标准输入（键盘）的操作，相当对输入文件的操作 Assign(Output,Fout);Rewrite(Output);采用重定向的手段，将输出文件与标准输出联系起来， 这样对标准输出（屏幕）的操作，相当对输出文件的操作 Readln(M,N); For I:=1 To M Do Begin For J:=1 To N Do Read(AI,J); Readln; End;End;Procedure Out;Begin write(,J,k,); 输出起始位置的坐标 Writeln(:5,W); 输出路径 printed:=True 置已经打印的标志End;Procedure Work(T,X,Y:Integer);搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标Var I : Integer;Begin If T=Length(S)+1 Then begin 搜索完，打印输出 Out; exit end; For I:=1 To 8 Do 八个方向进行搜索 Begin X:=X+FxI,1; Y:=Y+FxI,2; 坐标变化 If (AX,Y=ST)And(BX,Y) Then Begin W:=W+Chr(I+48); 记录路径 BX,Y:=False; 设置已经搜索 Work(T+1,X,Y); 继续搜索下一个 Delete(W,Length(W),1);恢复原路径 BX,Y:=True; 恢复标志 End; X:=X-FxI,1; Y:=Y-FxI,2; 返回后，坐标恢复 End;End;Begin Init; Readln(N); For I:=1 To N Do 对所有的国都名进行处理 Begin Readln(S); 读入第I个国都名 printed:=False; Fillchar(B,Sizeof(B),True);未搜索之前清标志数组 For J:=1 To N Do begin 对字符矩阵进行搜索 For K:=1 To N Do Begin If printed Then Break; 已经打印了，跳出内循环 If AJ,K=S1 Then Work(2,J,K);从第一个字符开始搜 End; If printed Then Break; 已经打印了，跳出外循环 end; If Not printed Then Writeln(No found); End; Close(Input); Close(Output);End.例19采用递归方法，求N个元素中取出M个的排列，。（1）每个元素只能取一次。（2）每个元素可以取任意多次（即可重复的排列）。分析：此题用简单的递归搜索。设xI排列中的第I个元素，依次搜索每一个xI即可program exam19;const finp =input.txt; fout =output.txt; maxn =10;var n,m :integer; x :array1.maxnof integer; x数组记录当前排列 used:array1.maxnof boolean;usedI=True时表明第I个元素在当前排列中，反之亦然procedure init;初始化输入 var i :integer; begin write(input n, m:); readln(n,m); fillchar(used,sizeof(used),false) end;procedure pailie(i:integer);搜索 var j :integer; begin if i>m then begin for j:=1 to m do write(xj:5);writeln;输出一组解 end else for j:=1 to n do if not usedj then begin usedj:=true;修改usedI xi:=j;记录xi pailie(i+1);继续搜索排列的下一个 usedj:=false还原usedI end end;Begin init; pailie(1);End.（2）只需要将pailie过程中used标志数组去掉即可，这样，已经取过的数据可以继续取。修改如下：procedure pailie(i:integer);搜索xI var j :integer;begin if i>m then begin for j:=1 to m do write(xj:5);writeln;找到一组解，输出 end else for j:=1 to n do begin枚举xI xi:=j; 记录xI pailie(i+1)继续搜索xI+1 end end;