理学递归与搜索上PPT学习教案

1、会计学1理学递归与搜索上理学递归与搜索上在数学上，求n的阶乘，有两种表示方法： 这两种表示方法实际上对应到两种不同的算法思想。第种表示方法中，求n！要反复把1、2、3、(n-2)、(n-1)、n累乘起来，是循环的思想，要用来实现，代码如下：int n, F=1;scanf( %d, &n );for( i=1; i=n; i+ ) F = F*i;printf( %d的阶乘为%d, n, F );第1页/共38页第种表示方法，求n！时需要用到(n-1)！。如果有一个函数能实现求n的阶乘，则该函数在求n！时要使用到表达式：，Factorial(n-1)表示调用Factorial( )函数去求(n

2、-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, &A );printf( %d!=%dn, A, Factorial(A) );return 0;该程序的运行示例如下：该程序的运行示例如下： 44!=24第2页/共38页int Factorial( int n )if( n0 ) return -1;else i

3、f( n=0 | n=1 ) return 1;else return n*Factorial(n-1);Factorial( )函数有一个特点，它在执行过程中又调用了Factorial( )函数，这种函数称为。具体来说，在执行一个函数过程中，又，如图8.1所示，这种函数调用称为；包含递归调用的函数称为。第3页/共38页假设要求3!，其完整的执行过程如图8.2所示，具体过程为：执行函数的开头部分；当执行到Factorial函数调用“”时，流程转而去执行函数，并将实参3传递给形参n；执行函数的开头部分；当执行到递归调用Factorial(n-1)函数时，此时n-1=2，所以要转而去执行函数；执行

4、函数的开头部分；当执行到递归调用Factorial(n-1)函数时，此时n-1=1，所以要转而去执行函数；第4页/共38页执行函数，此时因为n的值为1，所以返回1，而不是再递归调用下去，即，Factorial(1)函数执行完毕，返回到上一层，即返回函数中；执行完函数的剩余语句，返回到函数中；执行完函数的剩余语句，返回到函数中；继续执行函数的剩余部分直到整个程序执行完毕。第5页/共38页。猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下一个桃子了。求第1天共

5、摘了多少个桃子。假设Ai为第i天吃完后剩下的桃子的个数，本题要求的是A0。有以下递推式子： A1：第1天吃完后剩下的桃子数 A2：第2天吃完后剩下的桃子数 A9：第9天吃完后剩下的桃子数以上递推过程可分别用和实现。第6页/共38页如果x1，x2表示前后两天吃完后剩下的桃子数，则有递推关系：。从第9天剩下1个桃子，反复递推9次，则可求第1天共摘下的桃子数。这里包含了反复的思想，可以用循环结构来实现，代码如下：#include int main( )int day, x1, x2;day = 9;x2 = 1;while( day0 )x1 = (x2+1)*2; / 第1天的桃子数是第2天桃子数

6、加1后的2倍 x2 = x1;day-;printf( total=%dn, x1 );return 0;该程序的输出结果：该程序的输出结果： total=1534第7页/共38页前面所述的递推关系也可以采用下面的方式描述。假设第n天吃完后剩下的桃子数为，第n+1天吃完后剩下的桃子数为，则存在的推关系：。这种递推关系可以用递归函数实现，代码如下：#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;该程序的输出结果：该程序的输出结果

7、： total=1534以上递推关系式存在什么特点，为什么可以用递归函数实现？第8页/共38页采用递归思想递推Fibonacci数列中的每一项，并输出前20项的值。Fibonacci数列各项的递推关系是：，这种递推关系式很用实现。代码如下：#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(

8、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 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 89 144 233 377 610 987 1597 2584 4181 6765第9页/共38页输入两个正整数，求其最大公约数数论中有一个求最大公约数的算法称为，又

9、称。其基本思想及执行过程为(设m为两正整数中较大者，n为较小者)： ，即r = u%v，否则执行第(3)步；。在初等数学里是如何求两个数的最大公约数？第10页/共38页例如，假设输入的两个正整数为18和33，则m = 33，n = 18。求最大公约数的过程如下图所示。r=u%v=15u=v=18v=r=15r=u%v=3u=v=15v=r=3u=m=33v=n=18因此18和33的最大公约数是v=3r=u%v=0第11页/共38页辗转相除法可以采用的方法，即实现，如下面的代码：#include int gcd( int u, int v )/求u和v的最大公约数int r;while( (r=

10、u%v)!=0 ) u=v; v=r; return(v);int main( )int m, n, t;printf( Please input two positive integers : );scanf( %d%d, &m, &n );if( mB (表示将 A柱 最上面的 1 个盘子移到 B柱 上)l AC (将 A 此时最上面的 1 个盘子移到 C 上)l BC (将 B 上的盘子移到 C 上)v 又如：移动 3 个盘子的情况，需要 7 步l AC l ABl CBl ACl BAl BCl AC请尝试写出当盘子数 n=5时具体的移动的步骤。第15页/共38页n个盘子至少需要移动多

11、少步？比如n=64。现在我想不出移完64个盘子的步骤，但如果有另外一个人能想出怎样移完63个盘子，我只要移最后1个盘子就可以了！646362ABC12 646362ABC12 646362ABC12 646362ABC12 第16页/共38页第一个人移动64个盘子(AC)的过程：1.命令第 2 个人将 63 个盘子从 A 移到B 上；2.自己将剩余的最底下最大的那 1 个盘子从 A 移到 C 上；3.再命令第 2 个人将 63 个盘子从 B 移到 C 上；4.完成任务！第2个人移动63个盘子(AB)的过程：1.命令第 3 个人将 62 个盘子从 A 移到C 上；2.自己将剩余的最底下最大的那

12、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.完成任务！完成任务！层层下放！递归调用！层层下放！递归调用！第17页/共38页 v递归的结束条件：l 最后 1 个人（第 64 个人）只需要移动 1

13、个盘子。v 注意：l 第 1 个人完成任务的前提是：第 2 个人完成了任务l 第 2 个人完成任务的前提是：第 3 个人完成了任务l l 第 63 个人完成任务的前提是：第 64 个人完成了任务v 所以：l 只有当第 64 个人完成任务后，第 63 个人才能完成任务；只有第 264 个人完成任务后，第 1 个人才能完成任务！ 典型的递归问题！递归的结束条件是什么？第18页/共38页321ABC32ABC13ABC213ABC21ABC231ABC213ABC213ABC213进一步分析：v 欲将 A 上 3 个盘子移到 C 上，用递归思想可以分解为以下 3 步：1) 将 A 上 2 个盘子移到

14、 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 移到 Bl 第 3 步又可以用递归方法分解为：u 将 B 上 1 个盘子从 B 移到 A u 将 B 上 1 个盘子从 B 移到 C u 将 A 上 1 个盘子从 A 移到 C第19页/共38页l 综上，便可得到移动 3 个盘子的步骤为u AC u ABu CBu ACu BAu BCu

15、 AC第20页/共38页v将 n 个盘子从 A 移到 C 可以分解为以下 3 个步骤：； 。v上面第 1 步和第 3 步，都是把 n-1 个盘子从 1 个座移到另 1 个座上， 采用的办法是相同的，只是座的名字不同而已。为使之一般化，可以将第 1 步和第 3 步表示为：l将 one 座上 n-1 个盘子移到 two 座（借助 three 座）。l只是在第 1 步和第 3 步中，one、two、three 和 A、B、C 的对应关系不同。l对第 1 步，对应关系是：oneA，twoB，threeC 。l对第 3 步，对应关系是：oneB，twoC，threeA 。第21页/共38页v 因此，将上

16、面 3 个步骤分为 2 类操作：l 将 n-1 个盘子从 1 个座移到另 1 个座上 （当 n1 时）；l 将最后 1 个盘子从 1 个座上移到另 1 个座上 。 设计程序v 分别用 2 个函数实现以上 2 类操作：l 设计 hanoi 函数实现第 1 类操作；u 函数 hanoi( n, one, two, three ) 将实现把 n 个盘子从 one 座借助 two 座移到 three 座的过程；l 设计 move 函数实现第 2 类操作；u 函数 move( x, y ) 将实现把 1 个盘子从 x 座移到 y 座的过程。x 和 y 是代表 A、B、C 座之一，根据每次不同情况分别以

17、A、B、C 代入。第22页/共38页#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, &m ); printf( The steps of moving %d disks:n, m ); return 0;void move(char x, char y)printf( %c-%cn, x, y );/将将n个盘从个盘从one座借助座借助two座，移到座，移

18、到three座座void hanoi(int n,char one, char two,char three) void move(char x,char y);/声明声明 if(n=1) else hanoi(n-1,one,three,two); 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 座移到 t

19、hree 座的过程；第23页/共38页分析m=3时7个步骤是怎么输出来的，依次输出哪个步骤？/n=3void hanoi(n,A,B,C)if(n=1) elsehanoi(2,A,C,B);move(A,C);hanoi(2,B,A,C);/m=3int main()hanoi(m,A,B,C);/n=2void hanoi(n,A,C,B)if(n=1) elsehanoi(1,A,B,C);move(A,B);hanoi(1,C,A,B);/n=1void hanoi(n,A,B,C)if(n=1) move(A,C);else/n=2void hanoi(n,B,A,C)if(n=1)

20、 elsehanoi(1,B,C,A);move(B,C);hanoi(1,A,B,C);/n=1void hanoi(n,C,A,B)if(n=1) move(C,B);else/n=1void hanoi(n,B,C,A)if(n=1) move(B,A);else/n=1void hanoi(n,A,B,C)if(n=1) move(A,C);else第24页/共38页运行情况如下：运行情况如下：input the number of disks: 4The steps of moving 4 disks:ABACBCABCACBABACBCBACABCABACBC第25页/共38页#i

21、nclude int count = 0;/Fibonacci函数递归调用次数int Fibonacci( int n )count+;if( n=0 | n=1 ) return 1;else return ( Fibonacci(n-1) + Fibonacci(n-2) );void main()Fibonacci(20);printf( count=%dn, count );第26页/共38页第27页/共38页题目来源：ZOJ Monthly, December 2003题号：ZOJ2060定义另外一个Fibonacci数列：F(0) = 7，F(1) = 11，F(n) = F(n-

22、1) + F(n-2)，(n=2)。输入文件包含多行，每行为一个整数n，n 1,000,000。第三种输入方式!对输入文件中的每个整数n，如果F(n)能被3整除，输出yes，否则输出no。nonoyesno0123第28页/共38页本章例8.3讲解了用递归思想求Fibonacci数列各项，但在本题中因为n的值最大可以取到1,000,000。我们先用下面的程序输出前30项对3取余的结果：#include int f(int n)if(n=0) return 1;else if(n=1) return 2;else return ( f(n-1)+f(n-2) )%3;int main( )for

23、( int i=0; i30; i+ )printf( %d , f(i) );前30项对3取余得到的余数分别为：1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1。分析这些余数我们发现。如果我们把这8个余数存放到一个数组f0，对输入的任意整数n，则。按照这种方法可以很快判断f(n)是否能被3整除。第29页/共38页#include int f(int n) /求第n项对3取余得到的余数if(n=0) return 1;else if(n=1) return 2;else return ( f(n-1)+f(n-2) )%3;

24、int main( )int f08;for( int i=0; i8; i+ ) /把前8项的余数保存下来f0i = f(i);int n;while( scanf( %d, &n )!=EOF )if( f0n%8=0 ) printf( yesn );else printf( non );return 0;第30页/共38页题目来源：Asia 2004, Shanghai (Mainland China), Preliminary题号：ZOJ2423，POJ2083是存在“自相似”的一个物体或一种量，从某种技术角度来说，这种“自相似”是全方位的。定义如下：度数为1的分形很简单，为：X度数

25、为2的分形为：X X XX X如果用代表度数为的盒形分形，则度数为 的盒形分形可以地定义为：你的任务是。第31页/共38页输入文件包含多个测试数据，每个测试数据占一行，包含一个正整数n，n7。第二种输入方式!对每个测试数据，用符号“X”输出盒形分形。在每个测试数据对应的输出之后输出一个短划线符号“-”，否则得到的是“格式错误”的结果。这道题目在ZOJ和POJ上对输出的要求不一样；在ZOJ上要求在每行的末尾不要输出多余的空格，而在POJ上要求每行的宽度一样，这样某些行末尾有若干个空格。第32页/共38页X-X X XX X-X X X X X XX X X X X X X X XX X X X

26、X XX X X X-123-1第33页/共38页首先注意到度数为n的盒形分形，其大小是。可以用字符数组来存储盒形分形中各字符。因为n7，而36 = 729，因此可以。其次，度数为n的盒形分形可以由以下递推式子递推式子表示： B(n-1) B(n-1)B(n) = B(n-1) B(n-1) B(n-1)第34页/共38页 B(n-1) B(n-1)B(n) = B(n-1) B(n-1) B(n-1)因此，可以用一个来设置度数为n的盒形分形。假设，它由5个度数为n-1的盒形分形组成，其起始位置分别为：、和，其中。该递归函数的是：。另外，题目中提到“”，因此在字符数组Fractal每行最后一个“X”字符之后，应该设置串结束符标志0。第35页/共38页#include #include #define MAXSCALE 730 /n为最大值7时，分形的大小是3636，而36 = 729/函数功能：从(startX,startY)位置开始设置