《[理学]第08章 递归与搜索上》由会员分享，可在线阅读，更多相关《[理学]第08章 递归与搜索上（39页珍藏版）》请在金锄头文库上搜索。
1、信息学院信息技术教研室程序设计方法及在线实践第8章 递归与搜索(上)2第8章 递归与搜索 递归是一种重要的算法思想。 递归既可以实现递推过程递推过程，也可以实现求解诸多 问题的通用思路搜索搜索。38.1 递归的基本思想8.1.1 什么是递归在数学上，求n的阶乘，有两种表示方法： n n！= n(n-1)(n-2)21= n(n-1)(n-2)21 n n！= n(n-1)= n(n-1)！这两种表示方法实际上对应到两种不同的算法思想。 第种表示方法中，求n！要反复把1、2、3、(n-2)、(n-1)、 n累乘起来，是循环的思想，要用循环结构循环结构来实现，代码如下：int n, F=1; sc
2、anf( “%d“, for( i=1; i int Factorial( int n ) if( n int main( ) int day, x1, x2; day = 9; x2 = 1; while( day0 ) x1 = (x2+1)*2; / 第1天的桃子数是第2天桃子数加1后的2倍 x2 = x1; day-; printf( “total=%dn“, x1 ); return 0; 该程序的输出结果： total=153410用递归思想实现：用递归思想实现： 前面所述的递推关系也可以采用下面的方式描述。假设第n天吃 完后剩下的桃子数为A(n)A(n)，第n+1天吃完后剩下的桃
3、子数为 A(n+1)A(n+1)，则存在的推关系：A(n) = ( A(n+1) + 1 ) * 2A(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思考：思考：以上递推关系式存在什么特点，为什么可以用递 归函数实现？11例例8.3 8.3 采用递归思想递推Fibonacci数列
4、中的每一项，并输出前 20项的值。分析：分析： Fibonacci数列各项的递推关系是：F(n) = F(n-1) + F(n-2)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; i int gcd( int u, int v )/求u和v
5、的最大公约数 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柱 上) l AC (将 A 此时最上面的 1 个盘子移到 C 上) l BC (将 B 上的盘子移到 C 上) v 又如：移动 3 个盘子的情况，需要 7 步 l AC l AB l CB l AC l BA l BC l AC思考：思考：请尝试写
6、出当盘子数 n=5时具体的移动的步骤。18思考：思考：n个盘子至少需要移动多少步？比如n=64。现在我想不出移完64个盘子的步 骤，但如果有另外一个人能想出 怎样移完63个盘子，我只要移最 后1个盘子就可以了！646362ABC1 2 646362ABC1 2 646362ABC1 2 646362ABC1 2 19第一个人移动64个盘子(AC)的过程： 1.命令第 2 个人将 63 个盘子从 A 移到B 上； 2.自己将剩余的最底下最大的那 1 个盘子从 A 移到 C 上； 3.再命令第 2 个人将 63 个盘子从 B 移到 C 上； 4.完成任务！第2个人移动63个盘子(AB)的过程： 1
7、.命令第 3 个人将 62 个盘子从 A 移到C 上； 2.自己将剩余的最底下最大的那 1 个盘子从 A 移到 B 上 ； 3.再命令第 3 个人将 62 个盘子从 C 移到 B 上； 4.完成任务！第3个人移动62个盘子(AC)的过程： 1.命令第 4 个人将 61 个盘子从 A 移到B 上； 2.自己将剩余的最底下最大的那 1 个盘子从 A 移 到 C 上； 3.再命令第 4 个人将 61个盘子从 B 移到 C 上； 4.完成任务！层层下放！递归调用！20A Answer :nswer :v递归的结束条件： l 最后 1 个人（第 64 个人）只需要移动 1 个盘子。 v 注意： l 第
8、1 个人完成任务的前提是：第 2 个人完成了任务 l 第 2 个人完成任务的前提是：第 3 个人完成了任务 l l 第 63 个人完成任务的前提是：第 64 个人完成了任务 v 所以： l 只有当第 64 个人完成任务后，第 63 个人才能完成任务 ；只有第 264 个人完成任务后，第 1 个人才能完成任 务！ 典型的递归问题！思考：思考：递归的结束条件是什么？21321ABC32ABC13 ABC213 ABC21ABC231ABC213ABC2 13ABC213 进一步分析： v 欲将 A 上 3 个盘子移到 C 上，用递归思想可以 分解为以下 3 步： 1) 将 A 上 2 个盘子移到
9、B 上（借助 C ） 2) 将 A 上 1 个盘子移到 C 上 3) 将 B 上 2 个盘子移到 C 上（借助 A ）（其中，第 2 步可以直接实现。） l 第 1 步又可以用递归方法分解为： u 将 A 上 1 个盘子从 A 移到 C u 将 A 上 1 个盘子从 A 移到 B u 将 C 上 1 个盘子从 C 移到 B l 第 3 步又可以用递归方法分解为： u 将 B 上 1 个盘子从 B 移到 A u 将 B 上 1 个盘子从 B 移到 C u 将 A 上 1 个盘子从 A 移到 C22l 综上，便可得到移动 3 个盘子的步骤为 u AC u AB u CB u AC u BA u B
10、C u AC23结论 v 将 n 个盘子从 A 移到 C 可以分解为以下 3 个步骤：1)1)将将 A A 上上 n-1 n-1 个盘子借助个盘子借助 C C 先移到先移到 B B 上上； 2)2)把把 A A 上剩下的上剩下的 1 1 个盘移到个盘移到 C C 上上； 3)3)将将 n-1 n-1 个盘从个盘从 B B 借助借助 A A 移到移到 C C 上上。 v 上面第 1 步和第 3 步，都是把 n-1 个盘子从 1 个座 移到另 1 个座上， 采用的办法是相同的，只是座的 名字不同而已。为使之一般化，可以将第 1 步和第 3 步表示为： l将 one 座上 n-1 个盘子移到 two
11、 座（借助 three 座）。 l只是在第 1 步和第 3 步中，one、two、three 和 A、B、C 的对应关系不同。 l对第 1 步，对应关系是：oneA，twoB，threeC 。 l对第 3 步，对应关系是：oneB，twoC，threeA 。24v 因此，将上面 3 个步骤分为 2 类操作： l 将 n-1 个盘子从 1 个座移到另 1 个座上 （当 n1 时）； l 将最后 1 个盘子从 1 个座上移到另 1 个座上 。 设计程序 v 分别用 2 个函数实现以上 2 类操作： l 设计 hanoi 函数实现第 1 类操作； u 函数 hanoi( n, one, two, t
12、hree ) 将实现把 n 个盘子从 one 座借助 two 座移到 three 座的过程；l 设计 move 函数实现第 2 类操作； u 函数 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“
13、, printf( “The steps of moving %d disks:n“, m );hanoihanoi(m,A,B,C);(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);move(one,three);elsehanoi(n-1,one,thre
14、e,two);move(one,three);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 座的过程；26Hanoi(3,A,B,C)的执行过程问题：问题：分析m=3时7个步 骤是怎么输出来的，依 次输出哪个步骤？/n=3 void hanoi(n
15、,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(1,C,A,B); /n=1 void hanoi(n,A,B,C) if(n=1) move(A,C); else /n=2 void hanoi(n,B,A,C) if(n=1) else hanoi(1,B,C,A); move(B,C); hanoi(1,A,B,C); /n=1 void hanoi(n,C,A,B) if(n=1) move(C,B); else /n=1 void hanoi(n,B,C,A) if(n=1) move(B,A); else /n=1 voi
