递归与回溯算法精选文档.ppt

《递归与回溯算法精选文档.ppt》由会员分享，可在线阅读，更多相关《递归与回溯算法精选文档.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归与回溯算法1 1本讲稿第一页，共五十二页递归的定义递归的定义 所谓递归就是一个函数或过程可以直接或间接地调用自己。我们大家所谓递归就是一个函数或过程可以直接或间接地调用自己。我们大家都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个老都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里的故事是说庙里有一个老和尚正在给小和尚讲故事，故事里的故事是说。象。象这种形式，我们就可以称之为递归的一种形象描述，老和尚什么时

2、候这种形式，我们就可以称之为递归的一种形象描述，老和尚什么时候不向下讲了，故事才会往回返，最终才会结束。不向下讲了，故事才会往回返，最终才会结束。再如：前面多次提到的求再如：前面多次提到的求N!的问题。的问题。我们知道：当我们知道：当N0时，时，N!=N*(N-1)!，因此，求，因此，求N!的问题化成了求的问题化成了求N*(N-1)!的问题，而求的问题，而求(N-1)!的问题又与求的问题又与求N!的解法相同，只不过是求阶乘的的解法相同，只不过是求阶乘的对象的值减去了对象的值减去了1，当，当N的值递减到的值递减到0时，时，N!=1，从而结束以上过程，求，从而结束以上过程，求得了得了N!的解。的解

3、。2 2本讲稿第二页，共五十二页也就是说，求解也就是说，求解N!的过程可以用以下递归方法来表示：的过程可以用以下递归方法来表示：在这里，为了定义在这里，为了定义n!，就必须先定义，就必须先定义(n-1)!，为了定义，为了定义(n-1)!，又必须先定义，又必须先定义(n-2)!，上述这种用自身的简单情况来定，上述这种用自身的简单情况来定义自己的方式称为递归定义。义自己的方式称为递归定义。一个递归定义必须是有确切含义的，也就是说，必须一步比一一个递归定义必须是有确切含义的，也就是说，必须一步比一步简单，最后是有终结的，决不允许无限循环下去。步简单，最后是有终结的，决不允许无限循环下去。上面的例子中

4、，当上面的例子中，当N=0时定义一个数时定义一个数1，是最简单的情况，是最简单的情况，称为递归的边界，它本身不再使用递归定义。称为递归的边界，它本身不再使用递归定义。与递推一样，每一递归都有其边界条件。但不同的是，递推是由边与递推一样，每一递归都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式来求值，而递归则是从自身出发来达到边界界条件出发，通过递推式来求值，而递归则是从自身出发来达到边界条件。条件。3 3本讲稿第三页，共五十二页递归的调用递归的调用 在在Pascal程序中，子程序可以直接自己调用自己或间接调用自程序中，子程序可以直接自己调用自己或间接调用自己，则将这种调用形式称之为

5、递归调用。己，则将这种调用形式称之为递归调用。其中，我们将前者的调用方式称为简单递归，后者称为间接递归。其中，我们将前者的调用方式称为简单递归，后者称为间接递归。由于目前我们介绍、掌握的知识尚还无法实现间接递归，只有留待由于目前我们介绍、掌握的知识尚还无法实现间接递归，只有留待在以后的内容中我们再作介绍。本节只介绍直接递归。在以后的内容中我们再作介绍。本节只介绍直接递归。递归调用时必须符合以下三个条件：递归调用时必须符合以下三个条件：（1）可将一个问题转化为一个新的问题，而新问题的解决方法仍）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已

6、，即它们只与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。是有规律的递增或递减。（2）可以通过转化过程使问题回到对原问题的求解。）可以通过转化过程使问题回到对原问题的求解。（3）必须要有一个明确的结束递归的条件，否则递归会无止）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。境地进行下去。下面我们通过一些例子，来解释递归程序的设计。下面我们通过一些例子，来解释递归程序的设计。4 4本讲稿第四页，共五十二页programaa;vart:longint;n:integer;functionfac(n:integer):longint;beginifn

7、=0thenfac:=1elsefac:=fac(n-1)*n;end;例例1：按照以上的分析，用递归的方法来求：按照以上的分析，用递归的方法来求N！的解。！的解。程序如下：程序如下：测试数据：测试数据：输入：输入：inputn=5输出：输出：5!=120beginwrite(inputn=);read(n);ifn0thenwriteln(n0,dataerrer)elsebegint:=fac(n);writeln(n,!=,t)endend.5 5本讲稿第五页，共五十二页如图展示了程序的执行过程：如图展示了程序的执行过程：在在这这里，因里，因为为函数函数FAC的形参的形参是是值值形参，因

8、此每形参，因此每调调用一次用一次该该函函数，系数，系统统就就为为本次本次调调用的用的值值形参形参N开辟了一个存开辟了一个存储单储单元，以便存放元，以便存放它的它的实实参的参的值值。也就是。也就是说说，对对于于递归递归函数或函数或递归过递归过程，每当程，每当对对它它调调用一次用一次时时，系，系统统都要都要为为它的形它的形式参数与局部式参数与局部变变量（在函数或量（在函数或过过程中程中说说明的明的变变量）分配存量）分配存储单储单元元（这这是一个独立的是一个独立的单单元，元，虽虽然名然名字相同，但字相同，但实际实际上是互不相干的，上是互不相干的，只在本只在本层层内有效），并内有效），并记记下返回下返

9、回的地点，以便返回后程序从此的地点，以便返回后程序从此处处开始开始执执行。行。6 6本讲稿第六页，共五十二页例例2：读入一串字符倒序输出，以字符：读入一串字符倒序输出，以字符&为结束标志，用过程来实现。为结束标志，用过程来实现。分析：由题意可知，读一串字符当然只能一个个地读入，要倒序输出，分析：由题意可知，读一串字符当然只能一个个地读入，要倒序输出，就要一直读到字符就要一直读到字符&。如输入的一段字符为。如输入的一段字符为ABCDEFGH&，则倒，则倒序输出的结果应该是序输出的结果应该是&HGFEDCBA。（1）读入一个字符；）读入一个字符；（2）读（该字符后的）子串并倒序输出；）读（该字符后

10、的）子串并倒序输出；（3）然后输出读入字符（指（）然后输出读入字符（指（1）读入的字符）读入的字符）（4）在（）在（2）中若子串是空（即遇字符）中若子串是空（即遇字符&），表示子串已完，），表示子串已完，不再处理子串。不再处理子串。以上（以上（2）表示一操作依赖另一操作，所以需要用递归调用。）表示一操作依赖另一操作，所以需要用递归调用。（4）表示已知操作（递归的终止）。）表示已知操作（递归的终止）。7 7本讲稿第七页，共五十二页程序如下：程序如下：programaa;procedurereverse;varch:char;beginread(ch);ifch&thenreverse;write

11、(ch);end;beginreverse;writeln;end.测试数据：测试数据：输入：输入：abcdefghijklmn&输出：输出：&nmlkjihgfedcba8 8本讲稿第八页，共五十二页例例3：利用递归，将一个十进制整数：利用递归，将一个十进制整数K转化为转化为N进制整数（进制整数（N=10）。）。测试数据：测试数据：输入：输入：K和和N的值的值193输出：转化后的输出：转化后的N进制整数进制整数201programaa;varn,k:integer;proceduretentok(k,n:integer);varr:integer;beginr:=kmodn;k:=kdivn

12、;ifk0thententok(k,n);write(r);end;beginread(k,n);tentok(k,n);writeln;end.9 9本讲稿第九页，共五十二页递归的一般适合场合1数据的定义形式是按递归定义的数据的定义形式是按递归定义的.如：裴波那契数列的定义为：如：裴波那契数列的定义为：Fn=Fn-1+Fn-2F1=0F2=1beginread(n);s:=fib(n);writeln(s);end.测试数据：测试数据：输入：输入：5输出：输出：3programaa;varn:integer;s:longint;FunctionFIB(N:integer):integer;B

13、eginIfn=1thenFIB:=0Elseifn=2thenFIB:=1ElseFIB:=FIB(n-1)+FIB(n-2)End;1010本讲稿第十页，共五十二页例如；著名的例如；著名的Hanoi塔（汉诺塔）问题。塔（汉诺塔）问题。3数据之间的结构关系按递归定义的数据之间的结构关系按递归定义的例如：大家将在后面的学习内容中遇到的树的遍例如：大家将在后面的学习内容中遇到的树的遍历、图的搜索等问题。历、图的搜索等问题。2问题的求解方法是按递归算法来实现的。问题的求解方法是按递归算法来实现的。1111本讲稿第十一页，共五十二页判断运行结果1.programd1;vars,n:integer;f

14、unctionf(n:integer):integer;beginifn=1thenf:=1elsef:=n*n+f(n-1);end;beginwrite(inputn:);readln(n);s:=f(n);writeln(f(,n,)=,s)end.输入输入:inputn:3输出输出:练习一1212本讲稿第十二页，共五十二页2programd2;vara,b:integer;functionf(n:integer):integer;beginifn=1thenf:=1elseifn=2thenf:=2elsef:=f(n-1)+f(n-2);end;beginread(a);b:=f(a

15、);writeln(b);end.输入输入:4输出输出:1313本讲稿第十三页，共五十二页3programd3;vara,b,c,d:integer;procedurep(a:integer;varb:integer);varc:integer;begina:=a+1;b:=b+1;c:=2;d:=d+1;writeln(m,a,b,c,d);ifa=3时时f(N)=f(N-1)+f(N-2)1616本讲稿第十六页，共五十二页递归及其应用请计算请计算ack(m,n)的值。的值。(m,n=n）的最大公约数，应先将）的最大公约数，应先将m除以除以n；求得；求得余数余数r,如果等于零，除数如果等于零

16、，除数n就是就是m,n的最大公约数；如的最大公约数；如果果r不等于零，就用不等于零，就用n除以除以r，再看所得余数是否为零。，再看所得余数是否为零。重复上面过程，直到余数重复上面过程，直到余数r为零时，则上一次的余数为零时，则上一次的余数值即为值即为m,n的最大公约数。用其数学方式描述如下的最大公约数。用其数学方式描述如下:1919本讲稿第十九页，共五十二页programaa;varm,n,t:integer;functionf(m,n:integer):integer;varr:integer;beginif(mmodn)=0thenf:=nelsebeginr:=mmodn;f:=f(n,

17、r);end;end;beginreadln(m,n);ifm2)，记走法为f(n)：第1次走1个台阶，还剩(n-1)个台阶，走法为f(n-1)；第1次走2个台阶，还剩(n-2)个台阶，走法为f(n-2)。所以，f(n)=f(n-1)+f(n-2)。定义f(0)=1，则有：2121本讲稿第二十一页，共五十二页递归过程或函数直接（或间接）调用自身，但如果仅有这些操作，那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序，但它的参数、输入数据等均有所变化，并且在正常的情况下，随着调用的深入，必定会出现调用到某一层时，不再执行调用而是终止函数的执行。递归思路是把一

18、个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。递归分解不是随意地分解，要保证“大问题”和“小问题”相似相似。例：采用递归算法求实数数组A0.n中的最小值。2222本讲稿第二十二页，共五十二页算法1:设f(a,i)为数组元素a0.ai中的最小值。当i=0时，有f(a,i)=a0；假设f(a,i-1)已求出，则：算法2：设f(i,j)为ai.aj中的最小值。将a0.an看作一个线性表，它可以分解成a0.ai和ai+1.an两个子表，分别求得各自的最小值x和y，较小者就是a0.an中

19、的最小值。而求解子表中的最小值方法与总表相同，即再分别把它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止(该元素就是该表中的最小值)。2323本讲稿第二十三页，共五十二页functionmin(i,j:integer):real;varmid:integer;min1,min2:real;beginifi=jthenmin:=aielsebeginmid:=(i+j)div2;min1:=min(i,mid);min2:=min(mid+1,j);ifmin1,c)elsebeginmove(n-1,a,c,b);writeln(a,-,c);move(n-1,b,a,c);en

20、d;end;beginreadln(n);move(n,1,2,3);end.测试数据：测试数据：输入输入:3输出输出:1-31-23-21-32-12-31-32727本讲稿第二十七页，共五十二页例例7:数的计算数的计算（1）问题描述）问题描述我们要求找出具有下列性质数的个数我们要求找出具有下列性质数的个数(包含输入的包含输入的自然数自然数n):先输入一个自然数先输入一个自然数n(n0,N位数小于等于位数小于等于9位），用递归位），用递归方法把这个多位数颠倒过来输出。方法把这个多位数颠倒过来输出。（2）问题解析）问题解析由于由于N比较大，所以需要长整型。长整型的位数比较大，所以需要长整型。长

21、整型的位数=10位。位。（3）测试数据）测试数据输入：输入：12345678输出：输出：876543213131本讲稿第三十一页，共五十二页programaa;varn:Longint;procedurerd(number:Longint);beginwrite(numbermod10:1);number:=numberdiv10;ifnumber0thenrd(number);end;beginwrite(inputn=);readLn(n);rd(n);end.3232本讲稿第三十二页，共五十二页1.(文件名文件名:d6.pas)有一对雌雄兔，每两个月就繁殖有一对雌雄兔，每两个月就繁殖各一

22、对兔子。问各一对兔子。问N个月后共有多少对兔子？个月后共有多少对兔子？提示：提示：测试数据测试数据:输入输入:10输出输出:55练习二3333本讲稿第三十三页，共五十二页2.(文件名:d7.pas)计算组合数提示：测试数据测试数据:输入输入:62输出输出:153434本讲稿第三十四页，共五十二页3.前前N项和项和（1）问题描述）问题描述给定给定N(N=1)，用递归的方法计算，用递归的方法计算1+2+3+4+.+(N-1)+N,结果赋值给结果赋值给S。（2）测试数据）测试数据输入输入:5输出输出:s=153535本讲稿第三十五页，共五十二页程序提示:programaa;vart:integer;

23、s:Longint;functionfac(n:integer):Longint;beginifn=1thenfac:=（1）eLsefac:=（2）;end;beginread(t);s:=fac(t);writeLn(s=,（3）);end.3636本讲稿第三十六页，共五十二页搜索算法对于给定的问题,如果有简明的数学模型揭示问题的本质,我们尽量用解析法求解；如果无法建立数学模型,或者即使有一定的数学模型,但采用数学方法解决有一定的困难,我们只好用模拟或搜索来求解。尽管搜索的时间复杂度一般是指数级的，但在缺乏解决问题的有效模型时，搜索却是一种行之有效的解决问题的基本方法，而且使用搜索算法解决

24、问题时，在实现过程中有很大的优化空间。信息学奥赛中考察搜索算法，一是考察选手算法运用能力，二是考察选手算法优化能力。枚举法（穷举法）回溯（深度优先搜索）广度优先搜索3737本讲稿第三十七页，共五十二页回溯法是搜索算法中的一种控制策略，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。即：从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,如果有路可以走下去，就走到下一个状态，继续按照这种规则搜索；当这一条路走到“尽头”而没达到目标状态的时候,再倒回上一个出发点,从另一个可能出发,继续搜索，直到达到目标状态。3838本讲稿

25、第三十八页，共五十二页例：迷宫求解 从迷宫的入口进去后是如何找到出口的？从迷宫的入口进去后是如何找到出口的？如果你不了解迷宫结构显然只能是摸索着前进，比如先如果你不了解迷宫结构显然只能是摸索着前进，比如先往一个方向走，若走不通那就只能退回来再试试另一个方向。往一个方向走，若走不通那就只能退回来再试试另一个方向。但在走的过程中你一定会有意识地但在走的过程中你一定会有意识地“记住记住”你已经走过的路，你已经走过的路，否则你会被困在迷宫中永远也走不出来了。否则你会被困在迷宫中永远也走不出来了。计算机解迷宫时，通常用的是计算机解迷宫时，通常用的是“穷举求解穷举求解”的方法，即的方法，即从入口出发，顺某

26、一方向向前探索，若能走通，则继续往前走；从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止路都探索到为止,如果所有可能的通路都试探过，还是不能走如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。到终点，那就说明该迷宫不存在从起点到终点的通道。先看两个动画演示的例子。先看两个动画演示的例子。3939本讲稿第三十九页，共五十二页4040本讲稿第四十页，共五十二页4141本讲稿第四十一页，共五十二页由此，求迷宫中一条路径的算法的基本思想是

27、：若当前位置若当前位置“可通可通”，则纳入，则纳入“当前路径当前路径”，并继续，并继续朝朝“下一位置下一位置”探索；探索；若当前位置若当前位置“不可通不可通”，则应顺着，则应顺着“来的方向来的方向”退退回到回到“前一通道块前一通道块”，然后朝着除，然后朝着除“来向来向”之外的其他方之外的其他方向继续探索；若该通道块的四周四个方块均向继续探索；若该通道块的四周四个方块均“不可通不可通”，则应从，则应从“当前路径当前路径”上删除该通道块。上删除该通道块。4242本讲稿第四十二页，共五十二页例：n皇后问题在nn的国际象棋棋盘上，放置n个皇后，使任何一个皇后都不能吃掉另一个,需满足的条件是：同一行、同

28、一列、同一对角线上只能有一个皇后。求所有满足要求的放置方案。4343本讲稿第四十三页，共五十二页【分析】一、问题解的形式：x:array1.nofinteger;/xi:第i个皇后放在第i行，第xi列，保证所有皇后不同行问题的解变成求（x1，x2，xn）4皇后问题的解：（2，4，1，3），（3，1，4，2）4444本讲稿第四十四页，共五十二页二、放置第k(1=k0do/计算所有方案，回溯到第0行结束beginxk:=xk+1;/下一列while(xk=n)and(colxkorleftk+xkorrightk-xk)doxk:=xk+1;/尝试第k行上能放皇后的位置ifxk=nthen/第k行

29、的皇后可以放在xk列begin/设置列、对角线标志colxk:=true;leftk+xk:=true;rightk-xk:=true;k:=k+1;/进入下一行xk:=0;/初始化ifk=n+1then/n个皇后都放置完毕，输出解begintot:=tot+1;out;end;end5151本讲稿第五十一页，共五十二页else/无法放置第k行的皇后，回溯begink:=k-1;/返回上一行/清除列、对角线标志colxk:=false;leftk+xk:=false;rightk-xk:=false;end;end;/whilewriteln(tot);end./非递归算法5252本讲稿第五十二页，共五十二页