c语言_递归算法ppt课件

.,1,计算机语言与程序设计,谌卫军,清华大学软件学院,IntroductiontoComputerProgramming,.,2,第八章递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,.,3,从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，老和尚正在给小和尚讲故事。讲的是什么故事呢？他说，从前,.,4,Recursion-SeeRecursion.Inordertounderstandrecursion,onemustfirstunderstandrecursion.,.,5,C语言允许嵌套地调用函数，也就是说，在调用一个函数的过程中，又去调用另一个函数。,函数的嵌套调用,voidmain()study_english();,voidstudy_english()reading();listening();writing(),voidlistening(),.,6,函数的嵌套调用有一个特例，即递归调用，也就是说，在调用一个函数的过程中，又出现了直接或间接地去调用该函数本身。,voidtell_story()intold_monk,young_monk;tell_story();/tell_story函数的递归调用,函数的递归调用,?,.,7,voidtell_story()staticintold_monk,young_monk;old_monk=old_monk+1;/年龄大了一岁young_monk=young_monk+1;if(old_monkS；1#青蛙从YS；3#青蛙从LY；4#青蛙从LR；3#青蛙从YR；1#青蛙从SY；2#青蛙从SR；1#青蛙从YR；,.,49,对于S=1，y=1的情形，从另外一个角度来分析若没有石柱S，最多可过y+1=2只青蛙。有了石柱S后，最多可过2*2=4只青蛙。步骤1：1#和2#从LS；步骤2：3#和4#从LR；步骤3：1#和2#从SR；,Y,S,L,R,:1#,2#,:3#,4#,:1#,2#,Y,Y,Y,.,50,对于S=1，y1的情形若没有石柱S，最多可过y+1只青蛙。有了石柱S后，最多可过2*(y+1)只青蛙。步骤1：前y+1只从LS；步骤2：后y+1只从LR；步骤3：前y+1只从SR；,Y,S,L,R,:前y+1只,:后y+1只,:前y+1只,Y,Y,Y,.,51,对于S=2，y1的情形若只有石柱S1，最多可过2*(y+1)只青蛙。有了石柱S2后，最多可过只青蛙。,Y,S1,L,R,4*(y+1),S2,.,52,采用归纳法，可得出如下的递归形式：Jump(S,y)=2*Jump(S-1,y)；意思是：先让一半的青蛙利用y片荷叶和S-1根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用y片荷叶和S-1根石柱，落在右岸的R上面；最后再让先前的一半青蛙，利用y片荷叶和S-1根石柱，落在右岸的R上面。递归边界：Jump(0,y)=y+1,.,53,voidmain()intS,y;printf(请输入石柱和荷叶的数目：);scanf(%d%d,.,54,8.2.6快速排序,快速排序的基本思路：1、在数组a中，有一段待排序的数据，下标从l到r。2、取al放在变量value中，通过由右、左两边对value的取值的比较，为value选择应该排定的位置。这时要将比value大的数放右边，比它小的数放左边。当value到达最终位置后（如下标m），由它划分了左右两个集合l.m-1、m+1.r。然后转第1步，再用相同的思路分别去处理左集合和右集合。,.,55,令qsort(l,r)表示将数组元素从下标为l到下标为r的共r-l+1个元素进行从小到大的快速排序。目标：1、让value=al2、将value放在am中，lmr3、使al,al+1,am-1=am4、使amam+1,am+2,ar,.,56,例子：数组a当中有7个元素等待排序。,l,r,首先，让value=al=a0=5,value,5,a,0,1,2,3,4,5,6,下标,.,57,第二步，从r=6开始，将ar与value进行比较。若arvalue，则r-，继续比较。否则，al=ar，l+。,value,5,a,0,1,2,3,4,5,6,下标,4,.,58,第三步，从l=1开始，将al与value进行比较。若alvalue，则l+，继续比较。否则，ar=al，r-。,value,5,a,0,1,2,3,4,5,6,下标,6,.,59,又回到第二步，从r=5开始，将ar与value进行比较。若arvalue，则r-，继续比较。否则al=ar，l+。,value,5,a,0,1,2,3,4,5,6,下标,3,.,60,又回到第三步，从l=3开始，将al与value进行比较。若alvalue，则l+，继续比较。否则，ar=al，r-。,value,5,a,0,1,2,3,4,5,6,下标,7,.,61,现在lr，已经找到了value的正确位置，把value中的值放回到数组当中。,value,5,a,0,1,2,3,4,5,6,下标,5,.,62,下面的任务：用刚才介绍的方法，对5左、右两侧的两段数据，分别进行排序。,a,0,1,2,3,4,5,6,下标,.,63,最后的结果：,a,0,1,2,3,4,5,6,下标,具体实现：几重循环语句？,参考程序：略,.,64,第八章递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,.,65,在程序设计当中，有相当一类求一组解、或求全部解或求最优解的问题，不是根据某种确定的计算法则，而是利用试探和回溯（Backtracking）的搜索技术求解。回溯法也是设计递归算法的一种重要方法，它的求解过程实质上是一个先序遍历一棵“状态树”的过程，只不过这棵树不是预先建立的，而是隐含在遍历的过程当中。,.,66,8.3.1分书问题,有五本书，它们的编号分别为1，2，3，4，5，现准备分给A,B,C,D,E五个人，每个人的阅读兴趣用一个二维数组来加以描述：,希望编写一个程序，输出所有的分书方案，让人人皆大欢喜。,.,67,假定这5个人对这5本书的阅读兴趣如下表：,12345ABCDE,人,书,.,68,解题思路：,1、定义一个整型的二维数组，将上表中的阅读喜好用初始化的方法赋给这个二维数组。可定义：intLike66=0,0,0,0,1,1,0,0,1,1,0,0,1,0,0,1,1,0,1,0,0,0,0,1,0,0,0,1,0,0,1;,.,69,2、定义一个整型一维数组BookFlag6用来记录书是否已被选用。用后五个下标作为五本书的标号，被选用的元素值为1,未被选用的值为0,初始化皆为0.intBookFlag6=0;,.,70,3、定义一个整型一维数组BookTaken6用来记录每一个人选用了哪一本书。用数组元素的下标来作为人的标号，用数组元素的值来表示书号。如果某个人还没有选好书，则相应的元素值为0。初始化时，所有的元素值均为0。intBookTaken6=0;4、循环变量i表示人，j表示书，i,j1,2,3,4,5,.,71,一种方法：枚举法。把所有可能出现的分书方案都枚举出来，然后逐一判断它们是否满足条件，即是否使得每个人都能够得到他所喜欢的书。缺点：计算量太大。,.,72,如何抽取出递归形式？,.,73,voidperson(inti);intLike66=0,0,0,0,1,1,0,0,1,1,0,0,1,0,0,1,1,0,1,0,0,0,0,1,0,0,0,1,0,0,1;intBookFlag6=0;intBookTaken6=0;voidmain()person(1);,.,74,voidperson(inti)/尝试给第i个人分书intj,k;for(j=1;j=5;j+)/尝试把每本书分给第i个人if(BookFlagj!=0)|(Likeij=0)continue;/失败BookTakeni=j;/把第j本书分给第i个人BookFlagj=1;if(i=5)/已找到一种分书方案for(k=1;ki,表明这一步不可能走j级台阶,函数返回；否则，转第三步；第三步：这一步走j级台阶，即paces=j;如果i-j=0，说明已经到达地面了，也就是已经找到一种方案了，把它显示出来；否则的话，接着走下一步，TryStep(i-j,s+1)；第四步：j=j+1，如果j3，转第二步；否则函数结束。,能否用分治策略？,.,80,8.3.3八皇后问题,在88的棋盘上，放置8个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：（1）不在棋盘的同一行；（2）不在棋盘的同一列；（3）不在棋盘的同一对角线上。因此可以推论出，棋盘共有8行，故至多有8个皇后，即每一行有且仅有一个皇后。这8个皇后中的每一个应该摆放在哪一列上是解该题的任务。,.,81,.,82,数据的定义（1）：,i第i行（个）皇后，1i8；j第j列，1j8；Queeni第i行皇后所在的列；Columnj第j列是否安全，0,1；,.,83,12345678,1,2,3,4,5,6,7,8,.,84,数据的定义（2）：,Down-7.7记录每一条从上到下的对角线，是否安全，0,1Up2.16记录每一条从下到上的对角角线，是否安全，0,1,.,85,利用以上的数据定义：当我们需要在棋盘的(i,j)位置摆放一个皇后的时候，可以通过Column数组、Down数组和Up数组的相应元素，来判断该位置是否安全；当我们已经在棋盘的(i,j)位置摆放了一个皇后以后，就应该去修改Column数组、Down数组和Up数组的相应元素，把相应的列和对角线设置为不安全。,.,86,voidTryQueen(inti);intQueen9=0;intColumn9=0;intDown15=0;intUp15=0;voidmain()TryQueen(1);,.,87,voidTryQueen(inti)/摆放第i行的皇后intj,k;for(j=1;j=8;j+)/尝试把该皇后放在每一列if(Columnj|Downi-j+7|Upi+j-2)continue;/失败Queeni=j;/把该皇后放在第j列上Columnj=1;Downi-j+7=1;Upi+j-2=1;if(i=8)/已找到一种解决方案for(k=1;k=8;k+)printf(%d,Queenk);printf(n);elseTryQueen(i+1);/摆放第i+1行的皇后Queeni=0;/回溯，把该皇后从第j列拿起Columnj=0;Downi-j+7=0;Upi+j-2=0;,.,88,共92组解，部分答案如下：方案1：15863724方案2：16837425方案3：17468253方案4：17582463方案5：24683175方案6：25713864方案7：25741863方案8：26174835方案9：26831475方案10：27368514,.,89,假设在棋盘上事先已经摆放了一个国王，位置为，即第X行第Y列，在摆放八个皇后时，要求皇后间不能互相攻击且不能被国王攻击。国王的攻击范围如下图所示：,思考题：对题目做如下的修改,.,90,先输入某一个皇后所在的位置，即第X行第Y列，在此情形下，如何摆放其余的7个皇后，要求找到所有解决方案。,.,91,8.3.4过河问题,问题描述：M条狼和N条狗（NM）渡船过河，从河西到河东。在每次航行中，该船最多能容纳2只动物，且最少需搭载1只动物。安全限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。请问：能否找到一种方案，使所有动物都能顺利过河。如果能，移动的步骤是什么？,.,92,如何描述系统的当前状态？,位置：河西岸、河东岸、河；对象：船、狼、狗。,问题分析,.,93,三元组（W、D、B）,Wolf,Dog,Boat,例如：(2,2,W),.,94,若M2、N2,(2,2,W),(0,2,E),(1,2,W),(0,0,E),(2,0,W),(1,0,E),.,95,问题实质：在一个有向图中寻找一条路径；状态转换：如何从一个结点跳转到另一个结点；状态树？,问题分析,.,96,如何避免访问重复的结点？如何用简练的语句实现状态的转换？如何将5种情形归纳为同一种形式？,技术难点,.,97,#include#defineMAX_M20#defineMAX_N20intM,N;structStatusintW,D,B;steps1000;ints=0,num=0;intflagsMAX_MMAX_N2=0;voidCrossRiver(intW,intD,intB);intIsValid(intw,intd,intb);,.,98,voidmain()scanf(%d%d,.,99,if(B=0)f=-1;elsef=1;for(j=1;j0,.,102,22Solutions1:220021120101200001Solutions2:220021120101110001,Solutions3:220111120101200001Solutions4:220111120101110001,.,103,8.3.5排列问题,n个对象的一个排列，就是把这n个不同的对象放在同一行上的一种安排。例如，对于三个对象a,b,c，总共有6个排列：abcacbbacbcacabcban个对象的排列个数就是n!。,.,104,如何生成排列？,基于分治策略的递归算法：假设这n个对象为1,2,3,n；对于前n-1个元素的每一个排列a1a2an-1，1ain-1，通过在所有可能的位置上插入数字n，来形成n个所求的排列，即：na1a2an-1a1na2an-1a1a2nan-1a1a2an-1n,.,105,例如：生成1,2,3的所有排列,permutation(3)permutation(2)permutation(1),permutation(1)：1,permutation(2)：21，12,permutation(3)：321，231，213，312，132，123,.,106,基于回溯策略的递归算法：基本思路：每一个排列的长度为N，对这N个不同的位置，按照顺序逐一地枚举所有可能出现的数字。定义一维数组NumFlagN+1用来记录1-N之间的每一个数字是否已被使用，1表示已使用，0表示尚未被使用，初始化皆为0；,.,107,定义一维数组NumTakenN+1，用来记录每一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字，则相应的数组元素值为0。初始化时，所有元素值均为0；循环变量i表示第i个位置，j表示整数j，i,j1,2,N。,.,108,假定N=3,.,109,#defineN3voidTryNumber(inti);intNumFlagN+1=0;intNumTakenN+1=0;main()TryNumber(1);,.,110,voidTryNumber(inti)intj,k;for(j=1;j=N;j+)if(NumFlagj!=0)continue;NumTakeni=j;NumFlagj=1;if(i=N)for(k=1;k=N;k+)printf(%d,NumTakenk);printf(n);elseTryNumber(i+1);NumTakeni=0;NumFlagj=0;,.,111,问题描述：,编写一个程序，它接受用户输入的一个英文单词（长度不超过20个字符），然后