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+FJAns Then Begin 修改最优解 Ans:=Now; Out:=Ou; End; For K:=J To N Do 选取物品 If WKm 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 im 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;