《2022年高中信息技术 全国青少年奥林匹克联赛教案 递归与回溯法》由会员分享，可在线阅读，更多相关《2022年高中信息技术 全国青少年奥林匹克联赛教案 递归与回溯法（16页珍藏版）》请在金锄头文库上搜索。
1、2022年高中信息技术 全国青少年奥林匹克联赛教案 递归与回溯法课题：递归与回溯目标：知识目标：递归概念与利用递归进行回溯能力目标：回溯算法的应用重点：回溯算法难点：回溯算法的理解板书示意：1） 递归的理解2） 利用递归回溯解决实际问题（例14、例15、例16、例17、例18）3） 利用回溯算法解决排列问题（例19）授课过程：什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之是递归。例如，我们可以这样定义
2、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的执行过程。由上述程序可以看出
3、，递归是一个反复执行直到递归终止的过程。设一个未知函数f，用其自身构成的已知函数g来定义：为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2) ，上述这种用自身的简单情况来定义自己的方式称为递归定义。递归有如下特点：它直接或间接的调用了自己。一定要有递归终止的条件，这个条件通常称为边界条件。与递推一样，每一个递推都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件，在通过边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址）保存起来，直至求出递
4、归边界值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；由此可见，递归算法的效率往往很低，费时和费内存空间。但是递归也有其长处，它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性。特别是在难于找到从边界到解的全过程的情况下，如果把问题进一步，其结果仍维持原问题的关系，则采用递归算法编程比较合适。递归算法适用的一般场合为： 数据的定义形式按递归定义。如裴波那契数列的定义： 对应的递归程序
5、为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;
6、 数据之间的关系（即数据结构）按递归定义。如树的遍历，图的搜索等。 问题解法按递归算法实现。例如回溯法等。对于和，可以用堆栈结构将其转换为非递归算法，以提高算法的效率以及减少内存空间的浪费。下面以经典的N皇后问题为例，看看递归法是怎样实现的，以及比较递归算法和非递归算法效率上的差别。例15：N皇后问题图14 八皇后的两组解在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。分析：由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置都要进行试探和纠正，这就是“回溯”的思想。在N个皇后未放置完成前，摆放第I个
7、皇后和第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.M
8、axN 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;
9、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(Q
10、ueens 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:a
11、rray 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 be
12、gin 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.使用递归可以使蕴含复杂
