第08章 递归与搜索上

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第8章 递归与搜索(上),第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,上；,完成任务！,层层下放！递归调用！,Answer:,递归的结束条件：,最后 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,A,B,C);,/,n=2,void hanoi(n,A,C,B),if(n=1),else,hanoi(1,A,B,C);,move(A,B);,hanoi(