理学递归与搜索上

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第8章 递归与搜索,递归是一种重要的算法思想。,递归既可以实现,递推过程,，也可以实现求解诸多问题的通用思路,搜索,。,8.1 递归的基本思想,8.1.1 什么是递归,在数学上，求,n,的阶乘，有两种表示方法：,n！=n(n-1)(n-2)21,n！=n(n-1)！,这两种表示方法实际上对应到两种不同的算法思想。,第种表示方法中，求,n！,要反复把1、2、3、(,n-2)、(n-1)、n,累乘起来，是循环的思想，要用,循环结构,来实现，代码如下：,int,n,F=1;,scanf(%d,for,(i=1;i=n;i+)F=F*i;,printf(%d,的阶乘为%,d,n,F);,第种表示方法，求,n！,时需要用到(,n-1)！。,如果有一个函数,Factorial(int n),能实现求,n,的阶乘，则该函数在求,n！,时要使用到表达式：,n*Factorial(n-1),，Factorial(n-1),表示调用,Factorial(),函数去求(,n-1)！。,具体代码例8.1。,例8.1 递归求阶乘,#include,int,Factorial(,int,n),if,(n0),return,-1;,else,if,(n=0|n=1),return,1;,else,return,n*Factorial(n-1);,/,递归调用,Factorial,函数,int,main(),int,A;,scanf(%d,printf(%d!=%dn,A,Factorial(A);,return,0;,该程序的运行示例如下：,4,4!=24,int,Factorial(,int,n),if,(n0),x1=(x2+1)*2;,/,第1天的桃子数是第2天桃子数加1后的2倍,x2=x1;,day-;,printf(total=%dn,x1);,return,0;,该程序的输出结果：,total=1534,用递归思想实现：,前面所述的递推关系也可以采用下面的方式描述。假设第,n,天吃完后剩下的桃子数为,A(n),，,第,n+1,天吃完后剩下的桃子数为,A(n+1),，,则存在的推关系：,A(n)=(A(n+1)+1)*2,。这种递推关系可以用递归函数实现，代码如下：,#include,int,A(,int,n),if,(n=9),return,1;,else,return,(2*(A(n+1)+1);,int,main(),printf(total=%dn,A(0);,return,0;,该程序的输出结果：,total=1534,思考：,以上递推关系式存在什么特点，为什么可以用递归函数实现？,例8.3,采用递归思想递推,Fibonacci,数列中的每一项，并输出前20项的值。,分析：,Fibonacci,数列各项的递推关系是：,F(n)=F(n-1)+F(n-2),，,这种递推关系式很,适合,用,递归函数,实现。代码如下：,#include,int,Fibonacci(,int,n),if,(n=0|n=1),return,1;,else,return,(Fibonacci(n-1)+Fibonacci(n-2);,void,main(),int,i;,int,f20=0;,for,(i=0;i20;i+),/,调用递归函数求每项,fi=Fibonacci(i);,for,(i=0;i20;i+),if,(i%10=0)printf(n);,/,每行输出10个数据,printf(%6d,fi);,/,每个数据占6个字符的宽度,printf(n);,该程序的输出结果：,(,空一行),1 1 2 3 5 8 13 21 34 55,89 144 233 377 610 987 1597 2584 4181 6765,例8.4,输入两个正整数，求其最大公约数,分析：,数论中有一个求最大公约数的算法称为,辗转相除法,，又称,欧几里德(,Euclid),算法,。其基本思想及执行过程为(设,m,为两正整数中较大者，,n,为较小者)：,(1)令,u=m，v=n；,(2),取,u,对,v,的余数,，即,r=u%v，,如果,r,的值为0，则此时,v,的值就是,m,和,n,的最大公约数,，否则执行第(3)步；,(3),u=v，v=r，,即,u,的值为,v,的值，而,v,的值为余数,r。,并转向第(2)步,。,思考：,在初等数学里是如何求两个数的最大公约数？,分析(,continue)：,例如，假设输入的两个正整数为18和33，则,m=33，n=18。,辗转相除法,求最大公约数的过程如下图所示。,r=u%v=15,u=v=18,v=r=15,r=u%v=3,u=v=15,v=r=3,u=m=33,v=n=18,因此18和33的最大公约数是,v=3,r=u%v=0,辗转相除法可以采用,非递归,的方法，即,循环方法,实现，如下面的代码：,#include,int,gcd(,int,u,int,v),/,求,u,和,v,的最大公约数,int,r;,while,(r=u%v)!=0),u=v;v=r;,return,(v);,int,main(),int,m,n,t;,printf(Please input two positive integers:);,scanf(%d%d,if,(mB(,表示将,A,柱 最上面的 1 个盘子移到,B,柱 上,),AC(,将,A,此时最上面的 1 个盘子移到,C,上),BC(,将,B,上的盘子移到,C,上),又如：移动 3 个盘子的情况，需要 7 步,AC,AB,CB,AC,BA,BC,AC,思考：,请尝试写出当盘子数,n=5,时具体的移动的步骤。,思考：,n,个盘子至少需要移动多少步？比如,n=64。,现在我想不出移完64个盘子的步骤，但如果有另外一个人能想出怎样移完63个盘子，我只要移最后1个盘子就可以了！,64,63,62,A,B,C,1,2,64,63,62,A,B,C,1,2,64,63,62,A,B,C,1,2,64,63,62,A,B,C,1,2,第一个人移动64个盘子(,AC),的过程：,命令第 2 个人将 63 个盘子从,A,移到,B,上；,自己将剩余的最底下最大的那 1 个盘子从,A,移到,C,上；,再命令第 2 个人将 63 个盘子从,B,移到,C,上；,完成任务！,第2个人移动63个盘子(,AB),的过程：,命令第 3 个人将 62 个盘子从,A,移到,C,上；,自己将剩余的最底下最大的那 1 个盘子从,A,移到,B,上；,再命令第 3 个人将 62 个盘子从,C,移到,B,上；,完成任务！,第3个人移动62个盘子(,AC),的过程：,命令第 4 个人将 61 个盘子从,A,移到,B,上；,自己将剩余的最底下最大的那 1 个盘子从,A,移到,C,上；,再命令第 4 个人将 61个盘子从,B,移到,C,上；,完成任务！,层层下放！递归调用！,A,nswer:,递归的结束条件：,最后 1 个人（第 64 个人）只需要移动 1 个盘子。,注意：,第 1 个人完成任务的前提是：第 2 个人完成了任务,第 2 个人完成任务的前提是：第 3 个人完成了任务,第 63 个人完成任务的前提是：第 64 个人完成了任务,所以：,只有当第 64 个人完成任务后，第 63 个人才能完成任务；只有第 264 个人完成任务后，第 1 个人才能完成任务！,典型的递归问题！,思考：,递归的结束条件是什么？,3,2,1,A,B,C,3,2,A,B,C,1,3,A,B,C,2,1,3,A,B,C,2,1,A,B,C,2,3,1,A,B,C,2,1,3,A,B,C,2,1,3,A,B,C,2,1,3,进一步分析：,欲将,A,上 3 个盘子移到,C,上，用递归思想可以分解为以下 3 步：,将,A,上 2 个盘子移到,B,上（借助,C）,将,A,上 1 个盘子移到,C,上,将,B,上 2 个盘子移到,C,上（借助,A）,（,其中，第 2 步可以直接实现。）,第 1 步又可以用递归方法分解为：,将,A,上 1 个盘子从,A,移到,C,将,A,上 1 个盘子从,A,移到,B,将,C,上 1 个盘子从,C,移到,B,第 3 步又可以用递归方法分解为：,将,B,上 1 个盘子从,B,移到,A,将,B,上 1 个盘子从,B,移到,C,将,A,上 1 个盘子从,A,移到,C,综上，便可得到移动 3 个盘子的步骤为,AC,AB,CB,AC,BA,BC,AC,结论,将,n,个盘子从,A,移到,C,可以分解为以下 3 个步骤：,将,A,上,n-1,个盘子借助,C,先移到,B,上,；,把,A,上剩下的 1 个盘移到,C,上,；,将,n-1,个盘从,B,借助,A,移到,C,上,。,上面第 1 步和第 3 步，都是把,n-1,个盘子从 1 个座移到另 1 个座上，采用的办法是相同的，只是座的名字不同而已。为使之一般化，可以将第 1 步和第 3 步表示为：,将,one,座上,n-1,个盘子移到,two,座（借助,three,座）。,只是在第 1 步和第 3 步中，,one、two、three,和,A、B、C,的对应关系不同。,对第 1 步，对应关系是：,oneA，twoB，threeC。,对第 3 步，对应关系是：,oneB，twoC，threeA。,因此，将上面 3 个步骤分为 2 类操作：,将,n-1,个盘子从 1 个座移到另 1 个座上（当,n1,时）；,将最后 1 个盘子从 1 个座上移到另 1 个座上。,设计程序,分别用 2 个函数实现以上 2 类操作：,设计,hanoi,函数实现第 1 类操作；,函数,hanoi(n,one,two,three),将实现把,n,个盘子从,one,座借助,two,座移到,three,座的过程；,设计,move,函数实现第 2 类操作；,函数,move(x,y),将实现把 1 个盘子从,x,座移到,y,座的过程。,x,和,y,是代表,A、B、C,座之一，根据每次不同情况分别以,A、B、C,代入。,#,include,using,namespace,std;,int,main(),void hanoi(,int,n,char,one,char,two,char,three);,int,m;,printf(input the number of diskes:);,scanf(%d,printf(The steps of moving%d disks:n,m);,hanoi(m,A,B,C);,return,0;,void,move(,char,x,char,y),printf(%c-%cn,x,y);,/将,n,个盘从,one,座借助,two,座，移到,three,座,void,hanoi(,int,n,char,one,char,two,char,three),void,move(,char,x,char,y);/,声明,if,(n=1),move(one,three);,else,hanoi(n-1,one,three,two);,move(one,three);,hanoi(n-1,two,one,three);,函数调用,move(x,y),表示将 1 个盘子从,x,座移到,y,座的过程。,x,和,y,是代表,A、B、C,座之一，根据每次不同情况分别以,A、B、C,代入。,函数调用,hanoi(n-1,two,one,three),表示将,n-1,个盘子从,two,座借助,one,座移到,three,座的过程；,Hanoi(3,A,B,C),的执行过程,问题：,分析,m=3,时7个步骤是怎么输出来的，依次输出哪个步骤？,/,n=3,void hanoi(n,A,B,C),if(n=1),else,hanoi(2,A,C,B);,move(A,C);,hanoi(2,B,A,C);,/,m=3,int main(),hanoi(m