第06章 指针.ppt

《第06章 指针.ppt》由会员分享，可在线阅读，更多相关《第06章 指针.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、存在算法调用自己的情况：存在算法调用自己的情况：若一个算法直接的或间接的若一个算法直接的或间接的调用自己本身调用自己本身，则称这，则称这个算法是递归算法。个算法是递归算法。（1 1）问题的定义是递推的）问题的定义是递推的阶乘阶乘函数的函数的常见定义常见定义是：是：6.16.1递归的概念递归的概念2也可也可定义为：定义为：写成写成函数形式，则为：函数形式，则为：这种函数定义的方法是这种函数定义的方法是用阶乘函数用阶乘函数自己本身定义了阶乘函数，自己本身定义了阶乘函数，称公式（称公式（63）是阶乘函数的）是阶乘函数的递推定义式递推定义式。3（2）问题的解法存在自调用）问题的解法存在自调用 一一个个

2、典典型型的的例例子子是是在在有有序序数数组组中中查查找找一一个个数数据元素是否存在的据元素是否存在的折半查找算法折半查找算法。图图6-1 6-1 折半查找过程折半查找过程 46.26.2递归算法的执行过程递归算法的执行过程 例例6-1 6-1 给给出出按按照照公公式式6-36-3计计算算阶阶乘乘函函数数的的递递归归算算法法，并给出并给出n=3n=3时递归算法的执行过程。时递归算法的执行过程。设计：按照公式设计：按照公式6-36-3计算阶乘函数的递归算法如下：计算阶乘函数的递归算法如下：longintFact(intn)intx;longinty;if(n0)/nhigh)return-1;/查

3、找不成功查找不成功mid=(low+high)/2;if(x=amid)returnmid;/查找成功查找成功elseif(xamid)returnBSearch(a,x,low,mid-1);/在下半区查找在下半区查找elsereturnBSearch(a,x,mid+1,high);/在上半区查找在上半区查找例例6-2给出在有序数组给出在有序数组a中查找数据元素中查找数据元素x是否存在的是否存在的递归算法，并给出如图递归算法，并给出如图6-1所示实际数据的递归算法的所示实际数据的递归算法的执行过程。递归算法如下：执行过程。递归算法如下：8测试主函数设计如下：测试主函数设计如下：#inclu

4、demain(void)inta=1,3,4,5,17,18,31,33;intx=17;intbn;bn=BSearch(a,x,0,7);if(bn=-1)printf(x不在数组不在数组a中中);elseprintf(x在数组在数组a的下标的下标%d中中,bn);9BSearchBSearch(a,x,0,7)(a,x,0,7)的递归调用过程如图的递归调用过程如图6-36-3所示，所示，其中，其中，实箭头表示函数调用，虚箭头表示函数的返回值实箭头表示函数调用，虚箭头表示函数的返回值。图图6-3 6-3 BSearchBSearch(a,x,0,7)(a,x,0,7)的递归调用过程的递归调

5、用过程 106.36.3递归算法的设计方法递归算法的设计方法 递递归归算算法法既既是是一一种种有有效效的的算算法法设设计计方方法法，也也是是一一种种有有效效的的分分析析问问题题的的方方法法。递递归归算算法法求求解解问问题题的的基基本本思思想想是是：对对于于一一个个较较为为复复杂杂的的问问题题，把把原原问问题题分分解解成成若若干干个个相相对对简简单单且且类类同同的的子子问问题题,这这样样，原问题就可递推得到解。原问题就可递推得到解。适宜于用递归算法求解的问题的适宜于用递归算法求解的问题的充分必要条件是：充分必要条件是：（1 1）问题具有某种可借用的类同自身的子问题描述的性质；）问题具有某种可借用

6、的类同自身的子问题描述的性质；（2 2）某一有限步的子问题（也称作本原问题）有直接的解存在。）某一有限步的子问题（也称作本原问题）有直接的解存在。当当一一个个问问题题存存在在上上述述两两个个基基本本要要素素时时，该该问问题题的的递递归归算算法法的的设设计计方法是：方法是：（1 1）把对原问题的求解设计成包含有对子问题求解的形式。）把对原问题的求解设计成包含有对子问题求解的形式。（2 2）设计递归出口。）设计递归出口。11例例6-3 6-3 设设计计模模拟拟汉汉诺诺塔塔问问题题求求解解过过程程的的算算法法。汉汉诺诺塔塔问问题题的的描描述述是是：设设有有3 3根根标标号号为为A A，B B，C C

7、的的柱柱子子，在在A A柱柱上上放放着着n n个个盘盘子子，每每一一个个都都比比下下面面的的略略小小一一点点，要要求求把把A A柱柱上上的的盘盘子子全全部部移移到到C C柱柱上上，移移动动的的规规则则是是：（1 1）一一次次只只能能移移动动一一个个盘盘子子；（2 2）移移动动过过程程中中大大盘盘子子不不能能放放在在小小盘盘子子上上面面；（3 3）在在移移动动过过程程中中盘盘子子可以放在可以放在A A，B B，C C的任意一个柱子上。的任意一个柱子上。问题分析问题分析：可以用递归方法求解可以用递归方法求解n n个盘子的汉诺塔问题。个盘子的汉诺塔问题。基本思想基本思想：1 1个盘子的汉诺塔问题可直

8、接移动。个盘子的汉诺塔问题可直接移动。n n个盘子的汉诺个盘子的汉诺塔问题可递归表示为，首先把上边的塔问题可递归表示为，首先把上边的n-1n-1个盘子从个盘子从A A柱移到柱移到B B柱，柱，然后把最下边的一个盘子从然后把最下边的一个盘子从A A柱移到柱移到C C柱，最后把移到柱，最后把移到B B柱的柱的n-1n-1个盘子再移到个盘子再移到C C柱。柱。4 4个盘子汉诺塔问题的递归求解示意图如图个盘子汉诺塔问题的递归求解示意图如图6-46-4所示。所示。12图图6-4 6-4 汉诺塔问题的递归求解示意图汉诺塔问题的递归求解示意图13算法设计：算法设计：首先，盘子的个数首先，盘子的个数n n是必

9、须的一个输入参数，是必须的一个输入参数，对对n n个盘子个盘子,我们可从上至下依次编号为我们可从上至下依次编号为1,2,1,2,n n；其次，其次，输入参数还需有输入参数还需有3 3个柱子的代号个柱子的代号,我们令我们令3 3个柱子的参数名个柱子的参数名分别为分别为fromPegfromPeg，auxPegauxPeg和和toPegtoPeg；最后，汉诺塔问题的求最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是解是一个处理过程，因此算法的输出是n n个盘子从柱子个盘子从柱子fromPegfromPeg借助柱子借助柱子auxPegauxPeg移动到柱子移动到柱子toPegtoPeg的移动步

10、骤，我的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：们设计每一步的移动为屏幕显示如下形式的信息：Move Disk i from Peg X to Peg YMove Disk i from Peg X to Peg Y这样，汉诺塔问题的这样，汉诺塔问题的递归算法可设计如下：递归算法可设计如下：14voidtowers(intn,charfromPeg,chartoPeg,charauxPeg)if(n=1)/递归出口递归出口printf(%s%c%s%cn,movedisk1frompeg,fromPeg,topeg,toPeg);return;/把把n-1个圆盘从个圆盘从fro

11、mPeg借助借助toPeg移至移至auxPegtowers(n-1,fromPeg,auxPeg,toPeg);/把圆盘把圆盘n由由fromPeg直接移至直接移至toPegprintf(%s%d%s%c%s%cn,movedisk,n,frompeg,fromPeg,topeg,toPeg);/把把n-1个圆盘从个圆盘从auxPeg借助借助fromPeg移至移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);15测试主函数如下：测试主函数如下：#includevoidmain(void)Towers(4,A,C,B);程序运行的输出信息如下：程序运行的输出信息如下：

12、16MoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk3fromPegAtoPegBMoveDisk1fromPegCtoPegAMoveDisk2fromPegCtoPegBMoveDisk1fromPegAtoPegBMoveDisk4fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk2fromPegBtoPegAMoveDisk1fromPegCtoPegAMoveDisk3fromPegBtoPegCMoveDisk1fromPegAtoPeg

13、BMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegC17 总结如下：总结如下：递归算法的执行过程是递归算法的执行过程是不断地自调用不断地自调用，直，直到到达递归出口才结束自调用过程；到达递归出口后，递到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按归算法开始按最后调用的过程最先返回最后调用的过程最先返回的次序返回；返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束到最外层的调用语句时递归算法执行过程结束。186.46.4递归过程和运行时栈递归过程和运行时栈对于非递归函数，调用函数在调用被调用函数前，系统要对于非递归函数，调用函数

14、在调用被调用函数前，系统要保存保存以下两类以下两类信息信息：（1 1）调用函数的返回地址；）调用函数的返回地址；（2 2）调用函数的局部变量值。）调用函数的局部变量值。当执行完被调用函数，返回调用函数前，系统首先要当执行完被调用函数，返回调用函数前，系统首先要恢复恢复调用调用函数的函数的局部变量值局部变量值，然后，然后返回返回调用函数的调用函数的返回地址返回地址。递归函数被调用时，系统要作的工作和非递归函数被调用时递归函数被调用时，系统要作的工作和非递归函数被调用时系统要作的工作在系统要作的工作在形式上类同形式上类同，但，但保存信息的方法不同保存信息的方法不同。递归函数被调用时，系统的运行时栈

15、也要保存上述两类信息。递归函数被调用时，系统的运行时栈也要保存上述两类信息。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，每一层递归调用所需保存的信息构成运行时栈的一个工作记录，在每进入下一层递归调用时，系统就建立一个新的在每进入下一层递归调用时，系统就建立一个新的工作记录工作记录，并，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为运行的递归函数的工作记录，

16、所以栈顶的工作记录也称为活动记活动记录。录。196.56.5递归算法的效率分析递归算法的效率分析斐波那契数列斐波那契数列Fib(n)Fib(n)的递推定义是：的递推定义是：求第求第n n项斐波那契数列的项斐波那契数列的递归函数递归函数如下：如下：longFib(intn)if(n=0|n=1)returnn;/递归出口递归出口elsereturnFib(n-1)+Fib(n-2);/递归调用递归调用20用归纳法可以证明求用归纳法可以证明求Fib(n)的递归的递归调用次数调用次数等于等于2n-1；计算斐波那契数列的递归函数计算斐波那契数列的递归函数Fib(n)的的时间复时间复杂度为杂度为O(2n

17、)。计算斐波那契数列计算斐波那契数列Fib(n)问题，我们问题，我们也可根据公式写出也可根据公式写出循环方式求解的函数如下：循环方式求解的函数如下：图图6-6 6-6 Fib(5)Fib(5)的递归调用树的递归调用树 21longFib2(intn)longintoneBack,twoBack,current;inti;if(n=0|n=1)returnn;elseoneBack=1;twoBack=0;for(i=2;i=n;i+)current=oneBack+twoBack;twoBack=oneBack;oneBack=current;returncurrent;22上述循环方式的计算

18、斐波那契数列的函数上述循环方式的计算斐波那契数列的函数Fib2(n)的时的时间复杂度为间复杂度为O(n)。对比循环结构的对比循环结构的Fib2(n)和递归结构的和递归结构的Fib(n)可发现，可发现，循环结构循环结构的的Fib2(n)算法在计算第算法在计算第n项的斐项的斐波那契数列时波那契数列时保存了保存了当前已经计算得到的当前已经计算得到的第第n-1项和第项和第n-2项的斐波那契数列项的斐波那契数列，因此其，因此其时间复杂度为时间复杂度为O(n)；而而递归递归结构结构的的Fib(n)算法在计算第算法在计算第n项的斐波那契数列时，项的斐波那契数列时，必须必须首先计算第首先计算第n-1项和第项和

19、第n-2项的斐波那契数列项的斐波那契数列，而某次递归，而某次递归计算得出的斐波那契数列，如计算得出的斐波那契数列，如Fib(n-1)、Fib(n-2)等等无法无法保存保存，下一次要用到时还需要重新递归计算，因此其，下一次要用到时还需要重新递归计算，因此其时时间复杂度为间复杂度为O(2n)。236.66.6递归算法到非递归算法的转换递归算法到非递归算法的转换 有些问题需要用低级程序设计语言来实现，而低级程序设计语有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，

20、存在如下结构算法。一般来说，存在如下两种情况的递归算法两种情况的递归算法。（1 1）存在）存在不借助堆栈的循环结构的非递归算法不借助堆栈的循环结构的非递归算法，如阶乘计算问，如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。这种情况，题、斐波那契数列的计算问题、折半查找问题等。这种情况，可可以直接选用循环结构的算法。以直接选用循环结构的算法。（2 2）存在）存在借助堆栈的循环结构的非递归算法借助堆栈的循环结构的非递归算法，所有递归算法都，所有递归算法都可以借助堆栈转换成循环结构的非递归算法，如下边例可以借助堆栈转换成循环结构的非递归算法，如下边例6-46-4设计的设计的汉诺塔问题的借助堆

21、栈的循环结构的非递归算法。此时汉诺塔问题的借助堆栈的循环结构的非递归算法。此时可以把递可以把递归算法转换成相应的非递归算法，归算法转换成相应的非递归算法，有两种转换方法：有两种转换方法：一种方法是一种方法是借助堆栈借助堆栈，用非递归算法形式化模拟递归算法的执行过程；，用非递归算法形式化模拟递归算法的执行过程；另一另一种方法是种方法是根据要求解问题的特点，根据要求解问题的特点，设计借助堆栈的循环结构算法。设计借助堆栈的循环结构算法。这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。下面讨论的例和递归函数的运

22、行特点相吻合。下面讨论的例6-46-4是第二种情况下是第二种情况下的第一种转换方法的例子的第一种转换方法的例子24顺序堆栈的顺序堆栈的数据元素类型数据元素类型Datatype定义如下：定义如下：StructDataTypeintretAddr;/代表返回地址的数值代表返回地址的数值intnPara;/参数参数1charfromPegPara;/参数参数2chartoPegPara;/参数参数3charauxPegPara;/参数参数4;例例6-4借借助助堆堆栈栈模模拟拟系系统统的的运运行行时时栈栈，把把汉汉诺诺塔塔问问题题的的递递归归算算法法转转换换为为非递归算法。非递归算法。25算法设计：汉

23、诺塔问题的算法设计：汉诺塔问题的非递归函数设计如下：非递归函数设计如下：voidSimTowers(intn,charfromPeg,chartoPeg,charauxPeg)/把把n个盘子从个盘子从fromPeg柱借助柱借助auxPeg柱移到柱移到toPeg柱柱DataTypecurrArea;SeqStacks;chartemp;shortinti;26/当前工作区初始化当前工作区初始化currArea.retAddr=1;currArea.nParam=n;currArea.fromParam=fromPeg;currArea.auxParam=auxPeg;currArea.toPar

24、am=toPeg;S.Push(CurrArea);27/以下模拟递归出口以下模拟递归出口start:if(currArea.nPara=1)coutmovedisk1frompegcurrArea.fromParamtoPegcurrArea.toParamendl;i=currArea.retAddr;currArea=s.Pop();switch(i)case1:gotolable1;case2:gotolable2;case3:gotolable3;28/以下模拟递归自调用过程以下模拟递归自调用过程s.Push(currArea);currArea.nParam-;Temp=currA

25、rea.auxParam;currArea.toParam=currArea.toParam;currArea.toParam=temp;currArea.retAddr=2;gotostart;29/以下模拟返回第一次递归调用以下模拟返回第一次递归调用lable2:coutmovedisk“currarea.nParamfrompegcurrarea.fromPegParamtopeg“currarea.toParamendl;s.Push(currArea);currArea.nParam-;temp=currArea.auxParam;currArea.toParam=currArea.

26、toParam;currArea.toParam=temp;currArea.retAddr=3;gotostart;30/以下模拟返回第二次递归调用以下模拟返回第二次递归调用lable3:i=currarea.retAddr;currArea=s.Pop();switch(i)case1:gotolable1;case2:gotolable2;case3:gotolable3;/以下模拟返回主调函数以下模拟返回主调函数lable1:return;由由于于汉汉诺诺塔塔问问题题本本身身算算法法的的复复杂杂度度就就是是O(2n)，所所以以这这个个模模拟拟算算法的法的时间复杂度也是时间复杂度也是O(

27、2n)。316.76.7设计举例设计举例6.7.1 6.7.1 一般递归算法设计举例一般递归算法设计举例例例6-5 6-5 设设计计一一个个输输出出如如下下形形式式数数值值的的递递归归算法。算法。n n n .nn n n .n.3 3 3 3 3 3 2 22 21 132问问题题分分析析：该该问问题题可可以以看看成成由由两两部部分分组组成成：一一部部分分是是输输出出一一行行值值为为n的的数数值值；另另一一部部分分是是原原问问题题的的子子问问题题，其其参参数数为为n-1。当当参参数数减减到到0时时不不再再输输出出任任何何数数据据值值，因因此此递递归归的的出出口口是是当当参参数数n0时空语句返

28、回。时空语句返回。算法设计：递归算法设计如下：算法设计：递归算法设计如下：voidDisplay(intn)inti;for(i=1;i=n;i+)coutsetw(s)n;cout0)Display(n-1);/递归递归/n=0为递归出口，递归出口为空语句为递归出口，递归出口为空语句33例例6-6设计求解设计求解委员会问题委员会问题的算法。委员会问题是：的算法。委员会问题是：从一个有从一个有n个人的团体中抽出个人的团体中抽出k(kn)个人组成一个委个人组成一个委员会，计算共有多少种构成方法。员会，计算共有多少种构成方法。问题分析：问题分析：从从n个人中抽出个人中抽出k(kn)个人的问题是一个

29、个人的问题是一个组合问题。把组合问题。把n个人固定位置后，从个人固定位置后，从n个人中抽出个人中抽出k个个人的问题可分解为两部分之和：第一部分是第一个人人的问题可分解为两部分之和：第一部分是第一个人包括在包括在k个人中，第二部分是第一个人不包括在个人中，第二部分是第一个人不包括在k个人个人中。对于第一部分，则问题简化为从中。对于第一部分，则问题简化为从n-1个人中抽出个人中抽出k-1个人的问题；对于第二部分，则问题简化为从个人的问题；对于第二部分，则问题简化为从n-1个个人中抽出人中抽出k个人的问题。图个人的问题。图6-7给出了给出了n=5,k=2时问题时问题的分解示意图。的分解示意图。34图

30、图6-7 6-7 委员会问题分解示意图委员会问题分解示意图 35当当n=k或或k=0时，该问题可直接求解，数值均为时，该问题可直接求解，数值均为1，这是算法的递归出口。因此，委员会问题的这是算法的递归出口。因此，委员会问题的递推定递推定义式义式为：为：intComm(intn,intk)if(n1|kn)return0;if(k=0)return1;if(n=k)return1;returnComm(n-1,k-1)+Comm(n-1,k);36例例6-7求两个正整数求两个正整数n和和m最大公约数的最大公约数的递推定义式递推定义式为：为：要求：要求：（1 1）编写求解该问题的递归算法；）编写求

31、解该问题的递归算法；（2 2）分分析析当当调调用用语语句句为为GcdGcd(30,(30,4)4)时时算算法法的的执执行行过过程程和和执执行行结果；结果；（3 3）分分析析当当调调用用语语句句为为GcdGcd(97,(97,5)5)时时算算法法的的执执行行过过程程和和执执行行结果；结果；（4 4）编写求解该问题的循环结构算法。）编写求解该问题的循环结构算法。37解：（解：（1）递归算法如下：）递归算法如下：intGcd(intn,intm)if(n0|mn)returnGcd(m,n);elsereturnGcd(m,n%m);（2）调用语句为调用语句为Gcd(30,4)时，因时，因mn，递归

32、调用递归调用Gcd(4,2)；因因mn，递归调用递归调用Gcd(97,5)；因因mn，递归调用递归调用Gcd(5,2)；因因mn，递递归调用归调用Gcd(2,1)；因因mn，递归调用递归调用Gcd(1,0)；因因m=0，到达递归出口，函数最终返回值为到达递归出口，函数最终返回值为n=1，即即5和和97的最的最大公约数为大公约数为1。386.7.2 6.7.2 回溯法及其回溯法及其设计举例设计举例 回溯法是递归算法的一种特殊形式，回溯法的回溯法是递归算法的一种特殊形式，回溯法的基本思想是：基本思想是：对一个包括有很多结点，每个结点有若干个搜索分支的问题，把对一个包括有很多结点，每个结点有若干个搜

33、索分支的问题，把原问题分解为对若干个子问题求解的算法。原问题分解为对若干个子问题求解的算法。当搜索到某个结点、当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支一结点，继续搜索这个结点的其他尚未搜索过的分支；如果发现；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。为止。39