c语言_递归算法

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,117,计算机语言与程序设计,谌 卫 军,清华大学软件学院,Introduction to Computer Programming,第,八章 递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,从前有座山，山上有座庙，庙里有一个老和尚,和一个小和尚，老和尚正在给小和尚讲故事。,讲的是什么故事呢？他说，从前,Recursion,-,See,Recursion,.,In order to understand recursion, one must first understand recursion.,C,语言允许嵌套地调用函数，也就是说，在调用,一个函数的过程中，又去调用另一个函数,。,函数的嵌套调用,void main( ),study_english,( );,void,study_english,( ),reading( );,listening( );,writing( ),void listening( ),函数的嵌套调用有一个特例，即递归调用，也就,是说，在调用一个函数的过程中，又出现了直接,或间接地去调用该函数本身,。,void tell_story( ),int old_monk, young_monk;,tell_story ( ); / tell_story,函数的递归调用,函数的递归调用,?,void tell_story( ),static int old_monk, young_monk;,old_monk = old_monk + 1; /,年龄大了一岁,young_monk = young_monk + 1;,if(old_monk = 60) /,递归形式,tell_story ( );,else,printf(,对不起，已退休！,); /,递归边界,在语法上（简单）,递归即为普通的函数调用。,在算法上（难）,如何找到递归形式？,如何找到递归边界？,如何编写递归程序？,递归算法的类型,递归算法可以分为两种类型：,基于分治策略的递归算法；,基于回溯策略的递归算法。,第,八章 递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,分而治之（,divide-and-conquer,）的算法,设计思想：,Divide,：把问题划分为若干个子问题；,Conquer,：以,同样的方式,分别去处理各个子问题；,Combine,：把各个子问题的处理结果综合起来，形成最终的处理结果。,8.2.1,分而治之,玛特露什卡,调用,调用,调用,调用,调用,调用,如何编写基于分治策略的递归程序？,在算法分析上，要建立分治递归的思维方式。,在编程实现上，要建立,递归信心,（,To turst the recursion,Jerry Cain, stanford,）。,如何建立分治递归的思维方式？,基本原则：,目标驱动,！,计算,n,!,：,n,! =,n,* (,n,-1)!,，且,1! = 1,。,递归形式,递归边界,调用,调用,fact(3),fact(2),fact(1),void main( ),int,n,;,printf(,请输入一个整数：,);,scanf(%d, ,printf(%d! = %d n, n, fact(n);,int fact(int n),if(n = 1) return(1);,else return(n * fact(n-1);,请输入一个整数：,3,3! = 6,调用和返回的递归示意图,如何建立递归信心？,函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是的话，那么大家会不会相互干扰、相互妨碍？,main,的栈帧,m,3,void main( ),int,m,;,printf(,请输入一个整数：,);,scanf(%d, ,printf(%d! = %dn, m, fact(m);,int fact(int n),if(n = 1) return(1);,else return(n * fact(n-1);,3,n,fact,的栈帧,2,n,fact,的栈帧,1,n,fact,的栈帧,8.2.2,寻找最大值,问题描述：,给定一个整型数组,a,，找出其中的最大值。,如何设计相应的,递归算法,？,如何来设计相应的递归算法？,目标：,maxa0, a1, an-1,可分解为：,maxa0, maxa1, an-1,另外已知,maxx,x,这就是递归算法的,递归形式,和,递归边界,，据,此可以编写出相应的递归函数。,int Max(int a, int first, int n),int max;,if(first = n-1) return afirst;,max = Max(a, first+1, n);,if(max R) return(-1);,mid = (L + R)/2;,if(x = bmid),return mid;,else if(x Y,；,2#,青蛙从,L, S,；,1#,青蛙从,Y, S,；,3#,青蛙从,L, Y,；,4#,青蛙从,L, R,；,3#,青蛙从,Y, R,；,1#,青蛙从,S, Y,；,2#,青蛙从,S, R,；,1#,青蛙从,Y, R,；,对于,S = 1,，,y = 1,的情形，从另外一个角度来分析,若没有石柱,S,，最多可过,y+1,=,2,只青蛙。,有了石柱,S,后，最多可过,2*2 = 4,只青蛙。,步骤,1,：,1#,和,2#,从,L, S,；,步骤,2,：,3#,和,4#,从,L, R,；,步骤,3,：,1#,和,2#,从,S, R,；,Y,S,L,R,: 1#, 2#,: 3#, 4#,: 1#, 2#,Y,Y,Y,对于,S = 1,，,y 1,的情形,若没有石柱,S,，最多可过,y+1,只青蛙。,有了石柱,S,后，最多可过,2*(y+1),只青蛙。,步骤,1,：前,y+1,只 从,L, S,；,步骤,2,：后,y+1,只 从,L, R,；,步骤,3,：前,y+1,只 从,S, R,；,Y,S,L,R,:,前,y+1,只,:,后,y+1,只,:,前,y+1,只,Y,Y,Y,对于,S = 2,，,y 1,的情形,若只有石柱,S1,，最多可过,2*(y+1),只青蛙。,有了石柱,S2,后，最多可过 只青蛙。,Y,S1,L,R,4*(y+1),S2,步骤,1,：前,2*(y+1),只 从,L, S2,；,步骤,2,：后,2*(y+1),只 从,L, R,；,步骤,3,：前,2*(y+1),只 从,S2, R,；,Y,S1,Y,S1,Y,S1,采用归纳法，可得出如下的递归形式：,Jump(S, y) = 2 * Jump(S-1, y),；,意思是：先让一半的青蛙利用,y,片荷叶和,S-1,根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用,y,片荷叶和,S-1,根石柱，落在右岸的,R,上面；最后再让先前的一半青蛙，利用,y,片荷叶和,S-1,根石柱，落在右岸的,R,上面。,递归边界：,Jump(0, y) = y + 1,void main( ),int S, y;,printf(,请输入石柱和荷叶的数目：,);,scanf(%d %d, ,printf(,最多,有,%d,只青蛙过河,n, Jump(S, y);,int Jump(int S, int y),if(S = 0) return( y + 1 );,return(,2 * Jump(S-1, y),);,8.2.6,快速排序,快速排序的基本思路：,1,、在数组,a,中，有一段待排序的数据，下标从,l,到,r,。,2,、取,al,放在变量,value,中，通过由右、左两边对,value,的取值的比较，为,value,选择应该排定的位置。这时要将比,value,大的数放右边，比它小的数放左边。当,value,到达最终位置后（如下标,m,），由它划分了左右两个集合,l.m-1,、,m+1.r,。然后转第,1,步，再用,相同的思路,分别去处理左集合和右集合。,令,qsort(l, r),表示将数组元素从下标为,l,到下标为,r,的共,r-l+1,个元素进行从小到大的快速排序。,目标：,1,、让,value = al,2,、将,value,放在,am,中，,l, m r,3,、使,al, al+1, , am-1 = am,4,、使,am am+1, am+2, , ar,例子：数组,a,当中有,7,个元素等待排序。,5,2,6,1,7,3,4,l,r,首先，让,value = al = a0 = 5,value,5,a,0,1,2,3,4,5,6,下标,5,2,6,1,7,3,4,l,第二步，从,r=6,开始，将,ar,与,value,进行比较。若,ar, value,，则,r-,，继续比较。否则，,al = ar,，,l +,。,value,5,r,a,0,1,2,3,4,5,6,下标,4,l,4,2,6,1,7,3,4,第三步，从,l=1,开始，将,al,与,value,进行比较。若,al, value,，则,l+,，继续比较。否则，,ar = al,，,r -,。,value,5,r,a,0,1,2,3,4,5,6,下标,l,l,6,r,4,2,6,1,7,3,6,又回到第二步，从,r=5,开始，将,ar,与,value,进行比较。若,ar, value,，则,r-,，继续比较。否则,al = ar,，,l +,。,value,5,a,0,1,2,3,4,5,6,下标,l,r,3,l,4,2,3,1,7,3,6,又回到第三步，从,l=3,开始，将,al,与,value,进行比较。若,al, value,，则,l+,，继续比较。否则，,ar = al,，,r -,。,value,5,a,0,1,2,3,4,5,6,下标,r,l,l,7,r,4,2,3,1,7,7,6,现在,l,r,，已经找到了,value,的正确位置，把,value,中的值放回到数组当中。,value,5,a,0,1,2,3,4,5,6,下标,l,r,5,4,2,3,1,5,7,6,下面的任务：用刚才介绍的方法，对,5,左、右两侧的两段数据，分别进行排序。,a,0,1,2,3,4,5,6,下标,1,3,2,4,a,0,1,2,3,4,5,6,下标,l,r,6,7,a,0,1,2,3,4,5,6,下标,l,r,1,2,3,4,5,6,7,最后的结果：,a,0,1,2,3,4,5,6,下标,具体实现：几重循环语句？,参考程序：略,第,八章 递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,在程序设计当中，有相当一类求一组解、或求,全部解或求最优解的问题，不是根据某种确定的,计算法则，而是利用试探和回溯（,Backtracking,）,的搜索技术求解。回溯法也是设计递归算法的一种,重要方法，它的求解过程实质上是一个先序遍历一,棵“状态树”的过程，只不过这棵树不是预先建立的，,而是隐含在遍历的过程当中。,8.3.1,分书问题,有五本书，它们的编号分别为,1,，,2,，,3,，,4,，,5,，,现,准备分给,A, B, C, D, E,五个人，每个人的阅读兴趣用一个二维数组来加以描述：,希望编写一个程序，输出所有的分书方案，让人人皆大欢喜。,假定这,5,个人对这,5,本书的阅读兴趣如下表：,1 2 3 4 5,A,B,C,D,E,0,0,1,1,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,人,书,解题思路：,1,、定义一个整型的二维数组，将上表中的阅读喜好用初始化的方法赋给这个二维数组。可定义：,int Like,6,6, = 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,;,2,、定义一个整型一维数组,BookFlag6,用来记录书是否已被选用。用后五个下标作为五本书的标号，被选用的元素值为,1,未被选用的值为,0,初始化皆为,0.,int BookFlag6 = ,0,;,3,、定义一个整型一维数组,BookTaken6,用来记录每一个人选用了哪一本书。用数组元素的下标来作为人的标号，用数组元素的值来表示书号。如果某个人还没有选好书，则相应的元素值为,0,。初始化时，所有的元素值均为,0,。,int,BookTaken,6 = 0;,4,、循环变量,i,表示人，,j,表示书，,i, j, 1, 2, 3, 4, 5,一种方法：,枚举法,。,把所有可能出现的分书方案都枚举出来，,然后逐一判断它们是否满足条件，即是否,使得每个人都能够得到他所喜欢的书。,缺点：计算量太大。,i=1,j=1,j=2,i=2,j=3,j=5,i=3,j=1,i=3,j=2,j=4,i=4,j=2,j=4,i=4,j=5,i=5,j=4,j=5,j=5,j=2,i=5,j=4,j=2,j=1,j=4,i=4,j=5,j=1,i=5,j=4,j=1,i=3,j=5,i=2,j=4,如何抽取出递归形式？,void person( int i );,int Like66 = 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;,int BookFlag6 = 0;,int BookTaken6 = 0;,void main( ),person( 1 );,void,person,(int,i)/,尝试给第,i,个人分书,int,j, 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; k i,表明这一步不可能走,j,级台阶,函 数,返回,；否则，转第三步；,第三步：这一步走,j,级台阶，即,paces = j;,如果,i - j = 0,，说明已经到达地面了，也就是 已经找到一种方案了，把它显示出来；否则 的话，接着走下一步，,TryStep(i-j, s+1),；,第四步：,j = j +1,，如果,j,3,，转第二步；否则函数 结束。,能否用分治策略？,8.3.3,八皇后问题,在,8,8,的棋盘上，放置,8,个,皇后,（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：,（,1,）不在棋盘的同一行；（,2,）不在棋盘的同一列；（,3,）不在棋盘的同一对角线上。,因此可以推论出，棋盘共有,8,行，故至多有,8,个皇后，即每一行有且仅有一个皇后。这,8,个皇后中的每一个应该摆放在哪一列上是解该题的任务。,数据的定义（,1,）：,i,第,i,行（个）皇后，,1, i 8,；,j,第,j,列，,1, j 8,；,Q,ueeni,第,i,行皇后所在的列；,Columnj,第,j,列是否,安全,，,0, 1,；,1 2 3 4 5 6 7 8,1,2,3,4,5,6,7,8,数据的定义（,2,）：,Down-7,.,7 ,记录每一条从上到下的对 角线，是否安全，,0,1,Up2.16,记录每一条从下到上的对角 角线，是否安全，,0,1,利用以上的数据定义：,当我们需要在棋盘的,( i, j ),位置摆放一个皇后的时候，可以通过,Column,数组、,Down,数组和,Up,数组的相应元素，来判断该位置是否安全；,当我们已经在棋盘的,( i, j ),位置摆放了一个皇后以后，就应该去修改,Column,数组、,Down,数组和,Up,数组的相应元素，把相应的列和对角线设置为不安全。,void TryQueen( int i );,int Queen9 = 0 ;,int Column9 = 0 ;,int Down15 = 0 ;,int Up15 = 0 ;,void main( ),TryQueen( 1 );,void,TryQueen,(int i)/,摆放第,i,行的皇后,int j, 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);,else TryQueen(i + 1);/,摆放第,i+1,行的皇后,Queeni = 0;/,回溯，把该皇后从第,j,列拿起,Columnj = 0; Downi-j+7 = 0; Upi+j-2 = 0;,共,92,组解，部分答案如下：,方案1：1 5 8 6 3 7 2 4,方案2：1 6 8 3 7 4 2 5,方案3：1 7 4 6 8 2 5 3,方案4：1 7 5 8 2 4 6 3,方案5：2 4 6 8 3 1 7 5,方案6：2 5 7 1 3 8 6 4,方案7：2 5 7 4 1 8 6 3,方案8：2 6 1 7 4 8 3 5,方案9：2 6 8 3 1 4 7 5,方案10：2 7 3 6 8 5 1 4,假设在,棋盘上事先已经摆放了一个国王,，位置为,，,即,第X行第Y列,，,在摆放八个皇后时，要求皇后间不能互相攻击且不能被国王攻击。,国王的攻击范围如下图所示：,思考题：对题目做如下的修改,先输入某一个皇后所在的位置,，即第X行第Y列，,在此情形下，如何摆放其余的,7,个皇后，要求找到所有解决方案。,8.3.4,过河,问题,问题描述：,M,条狼和,N,条狗（,N,M,）渡船过河，从河西到河东。在每次航行中，该船最多能容纳,2,只动物，且最少需搭载,1,只动物。安全限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。,请问：能否找到一种方案，使所有动物都能顺利过河。如果能，移动的步骤是什么？,如何描述系统的当前状态？,位置：河西岸、河东岸、河；,对象：船、狼、狗。,问题分析,三元组,（,W,、,D,、,B,）,Wolf,Dog,Boat,例如：,(2, 2, W),若,M,2,、,N,2,(2, 2, W),(0, 2, E),(1, 2, W),(0, 0, E),(2, 0, W),(1, 0, E),问题实质：在一个有向图中寻找一条,路径,；,状态转换：如何从一个结点,跳转,到另一个结点；,状态树？,问题分析,如何避免访问,重复的,结点？,如何用,简练的,语句实现状态的转换？,如何将,5,种情形,归纳,为同一种形式？,技术难点,#include ,#define MAX_M 20,#define MAX_N 20,int M, N;,struct Status,int W, D, B;,steps1000;,int s = 0, num = 0;,int flagsMAX_MMAX_N2 = 0;,void CrossRiver(int W, int D, int B);,int IsValid(int w, int d, int b);,void main( ),scanf(%d %d, ,flagsMN0 = 1;,steps0.W = M;,steps0.D = N;,steps0.B = 0;,s = 1;,CrossRiver(M, N, 0);,void CrossRiver(int W, int D, int B),int i, j, f;,int w, d, b;,if(B = 0) f = -1;,else f = 1;,for(j = 1; j = 5; j+),switch(j),case 1: w = W + f*1; d = D; break;,case 2: w = W + f*2; d = D; break;,case 3: d = D + f*1; w = W; break;,case 4: d = D + f*2; w = W; break;,case 5: w = W + f*1; d = D + f*1; break;,b = 1 - B;,if(IsValid(w, d, b),flagswdb = 1;,stepss.W = w;,stepss.D = d;,stepss.B = b;,s+;,if(w = 0 & d = 0 & b = 1),num +;,printf(Solutions %d: n, num);,for(i = 0; i 0 ,if(N-d 0) ,return 1;,2 2,Solutions 1:,2 2 0,0 2 1,1 2 0,1 0 1,2 0 0,0 0 1,Solutions 2:,2 2 0,0 2 1,1 2 0,1 0 1,1 1 0,0 0 1,Solutions 3:,2 2 0,1 1 1,1 2 0,1 0 1,2 0 0,0 0 1,Solutions 4:,2 2 0,1 1 1,1 2 0,1 0 1,1 1 0,0 0 1,8.3.5,排列,问题,n,个对象的一个排列，就是把这,n,个不同的,对象放在同一行上的一种安排。例如，对于,三个对象,a,b,c,，总共有,6,个排列：,a b c,a c b,b a c,b c a,c a b,c b a,n,个对象的排列个数就是,n!,。,如何生成排列？,基于分治策略的递归算法：,假设这,n,个对象为,1, 2, 3, ,n,；,对于前,n-1,个元素的每一个排列,a,1,a,2,a,n,-1,，,1,a,i,n,-1,，,通过在所有可能的位置上插入数字,n,，来形成,n,个所求的排列，即：,n,a,1,a,2,a,n,-1,a,1,n,a,2,a,n,-1,a,1,a,2,n,a,n,-1,a,1,a,2,a,n,-1,n,例如：生成,1,2,3,的所有排列,permutation(3),permutation(2),permutation(1),permutation(1),：,1,permutation(2),：,2 1,，,1 2,permutation(3),：,3 2 1,，,2 3 1,，,2 1 3,，,3 1 2,，,1 3 2,，,1 2 3,基于回溯策略的递归算法：,基本思路：每一个排列的长度为,N,，对这,N,个不同的位置，按照顺序逐一地枚举所有可能出现的数字。,定义一维数组,NumFlagN+1,用来记录,1-N,之间的每一个数字是否已被使用，,1,表示已使用，,0,表示尚未被使用，初始化皆为,0,；,定义一维数组,NumTakenN+1,，用来记录每一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字，则相应的数组元素值为,0,。初始化时，所有元素值均为,0,；,循环变量,i,表示第,i,个位置，,j,表示整数,j,，,i, j,1, 2, , N,。,i=1, ,i=2,j=1,1 ,j=1,i=3,j=2,1 2,j=3,i=3,1 3,j=1,j=2,j=3,1 2 3,j=1,j=2,1 3 2,j=3,i=2,j=2,2 ,i=3,j=1,2 1,j=2,j=3,i=3,2 3,j=1,j=2,j=3,2 1 3,j=1,2 3 1,j=2,j=3,i=2,j=3,3 ,i=3,j=1,3 1,j=3,j=2,i=3,3 2,j=1,j=2,3 1 2,j=3,j=1,3 2 1,j=2,3,假定,N=3,#define N 3,void TryNumber( int i );,int NumFlagN+1 = 0;,int NumTakenN+1 = 0;,main( ),TryNumber( 1 );,void TryNumber(int i),int j, 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);,else TryNumber(i + 1);,NumTakeni = 0;,NumFlagj = 0;,问题描述：,编写一个程序，它接受用户输入的一个,英文单词（长度不超过,20,个字符），然后,输出由这个单词的各个字母所组成的所有,排列。有两个条件：第一、这个单词的,各个字母允许有相同的；第二、不能输出,重复的排列。,例如：,请输入一个英文单词：,boy,boy,byo,oby,oyb,ybo,yob,请输入一个英文单词：,bob,bob,bbo,obb,讨论,i=1, ,i=2,j=1,b ,j=1,i=3,j=2,b o,j=3,i=3,b b,j=1,j=2,j=3,b o b,j=1,j=2,b b o,j=3,i=2,j=2,o ,i=3,j=1,o b,j=2,j=1,j=2,j=3,o b b,j=3,假定单词为：,bob,j=3,#define MAXSIZE,20,void TryChar(char *word, int i, int length);,int CharFlagMAXSIZE = 0;,int CharTakenMAXSIZE = 0;,main( ),char wordMAXSIZE;,int length;,printf(,请输入一个单词：,);,scanf(%s, word);,length = strlen(word);,TryChar(word, 1, length);,void TryChar(char *word, int i, int length),int j, k;,for(j = 1; j = length; j+),if (CharFlagj =,1) continue;,for(k = 1; k j; k+),if(CharFlagk = 0),/,在同一结点不能测试相同的两个字符，,/,减,1,是为了对齐下标,。,if(wordk - 1 = wordj - 1) break;,if(k j) continue;,CharTakeni = j;,CharFlagj = 1;,if(i = length),for(k = 1; k = length; k+),printf(%c , wordCharTakenk - 1);,printf(n);,else TryChar(word, i + 1, length);,CharTakeni = 0;,CharFlagj = 0;,下 课 啦,!,