汉诺塔课件PPT课件

1、Contents7.1 为什么要用函数为什么要用函数7.2 怎样定义函数怎样定义函数7.3 调用函数调用函数7.4 函数声明和函数原型函数声明和函数原型7.5 函数的嵌套调用函数的嵌套调用第1页/共86页Contents7.6 函数的递归调用函数的递归调用7.7 数组作函数参数数组作函数参数7.8 局部变量和全局变量局部变量和全局变量7.9 变量存储方式和生存期变量存储方式和生存期7.10 变量的声明和定义变量的声明和定义第2页/共86页复习复习将事先编好的函数，采用将事先编好的函数，采用“组装组装”的办法简化的办法简化程序设计的过程。程序设计的过程。1. 模块化程序设计思路模块化程序设计思路

2、main( )a( )b( )c( )d( )e( )f( )h( )g( )m( )第3页/共86页复习复习将事先编好的函数，采用将事先编好的函数，采用“组装组装”的办法简化的办法简化程序设计的过程。程序设计的过程。function 功能。所以，从本质意义来说函数功能。所以，从本质意义来说函数就是用来完成一定功能的。就是用来完成一定功能的。1. 模块化程序设计思路模块化程序设计思路2. 函数是从英文哪个单词翻译过来的函数是从英文哪个单词翻译过来的第4页/共86页复习复习将事先编好的函数，采用将事先编好的函数，采用“组装组装”的办法简化的办法简化程序设计的过程。程序设计的过程。function

3、 功能。所以，从本质意义来说函数功能。所以，从本质意义来说函数就是用来完成一定功能的。就是用来完成一定功能的。则使用函数可以实现代码的（则使用函数可以实现代码的（ ）性）性。1. 模块化程序设计思路模块化程序设计思路2. 函数是从英文哪个单词翻译过来的函数是从英文哪个单词翻译过来的3. 若程序中要多次实现某一功能若程序中要多次实现某一功能第5页/共86页复习复习将事先编好的函数，采用将事先编好的函数，采用“组装组装”的办法简化的办法简化程序设计的过程。程序设计的过程。function 功能。所以，从本质意义来说函数功能。所以，从本质意义来说函数就是用来完成一定功能的。就是用来完成一定功能的。则

4、使用函数可以实现代码的（则使用函数可以实现代码的（ 重用重用 ）性）性。1. 模块化程序设计思路模块化程序设计思路2. 函数是从英文哪个单词翻译过来的函数是从英文哪个单词翻译过来的3. 若程序中要多次实现某一功能若程序中要多次实现某一功能第6页/共86页复习复习 形参形参 实参实参4. 函数调用过程函数调用过程int max(int x,int y) int z; z=(xy)?x,y; return z; c = max( a , b ); (main函数)值值39第7页/共86页复习复习int max(int x,int y) int z; z=(xy)?x,y; return z; c

5、= max( a , b ); (main函数) 形参形参 实参实参值值394. 函数调用过程函数调用过程第8页/共86页复习复习int max(int x,int y) int z; z=(xy)?x,y; return z; c = max( a , b ); (main函数) 形参形参 实参实参值值3994. 函数调用过程函数调用过程第9页/共86页复习复习int max(int x,int y) int z; z=(xy)?x,y; return z; c = max( a , b ); (main函数)调用前，形参调用前，形参x和和y不占内存不占内存调用时，为形参调用时，为形参x和和

6、y分配内存分配内存结束时，结束时，释放释放x和和y 形参形参 实参实参值值3994. 函数调用过程函数调用过程第10页/共86页复习复习 声明的作用声明的作用5. 函数声明函数声明把函数头信息把函数头信息,如如int max(int x,int y)通知给编译系统，以便在调用时系统通知给编译系统，以便在调用时系统按按此此检查检查调用的合法性调用的合法性。c = max ( a , b );第11页/共86页复习复习在在 哪里哪里 对对 谁谁 进行声明：进行声明：主调函数内部对被调用函数进行声明主调函数内部对被调用函数进行声明5. 函数声明函数声明若若main()调用调用max()，则在（，则在

7、（ ）函数）函数内部，对（内部，对（ ）函数进行声明。）函数进行声明。第12页/共86页复习复习在在 哪里哪里 对对 谁谁 进行声明：进行声明：主调函数内部对被调用函数进行声明主调函数内部对被调用函数进行声明5. 函数声明函数声明若若main()调用调用max()，则在（，则在（main）函数）函数内部，对（内部，对（max）函数进行声明。）函数进行声明。第13页/共86页复习复习声明方法：函数原型（首部）加分号声明方法：函数原型（首部）加分号5. 函数声明函数声明void main() int a,b; int max(int x, int y); 第14页/共86页复习复习与函数定义的区别

8、：函数定义是指对函数功能与函数定义的区别：函数定义是指对函数功能的确立。包括函数首部和函数体两部分的确立。包括函数首部和函数体两部分5. 函数声明函数声明int max(int x , int y) int z; z=xy?x:y; return z; 与变量类似，与变量类似，先定义，后使用。先定义，后使用。第15页/共86页复习复习在（在（ ）情况下，声明也可以被省略。）情况下，声明也可以被省略。5. 函数声明函数声明int max(int x , int y) int z; z=xy?x:y; return z; void main() int a=3,b=9,c; c = max(a,

9、b); 第16页/共86页复习复习在（在（ ）情况下，声明也可以被省略。）情况下，声明也可以被省略。5. 函数声明函数声明int max(int x , int y) int z; z=xy?x:y; return z; void main() int a=3,b=9,c; c = max(a, b); 主函数和其它函数，主函数和其它函数，表面上平行并列表面上平行并列的关系，的关系，实际上是主调与被调实际上是主调与被调的关系的关系第17页/共86页复习复习一个函数的执行过程中，又去调用另一函数。一个函数的执行过程中，又去调用另一函数。6. 函数的嵌套调用函数的嵌套调用int max4(int

10、a , int b ,int c , int d) int m,n; m=max2(a,b); n=max2(c,d); return max2(m,n);第18页/共86页复习复习一个函数的执行过程中，又去调用一个函数的执行过程中，又去调用自己本身自己本身。一种特殊的嵌套调用一种特殊的嵌套调用int fun(int n) int c; if(n=1) c = 0; else c = n*fun(n-1) return c;第19页/共86页复习复习一个函数的执行过程中，又去调用一个函数的执行过程中，又去调用自己本身自己本身。一种特殊的嵌套调用一种特殊的嵌套调用int fun(int n) i

11、nt c; if(n=1) c = 0; else c = n*fun(n-1) return c;第20页/共86页7.6 函数的递归调用函数的递归调用定义定义函数执行的过程中，函数执行的过程中，直接或者间接的调用直接或者间接的调用该函数本身，称为函该函数本身，称为函数的递归调用。数的递归调用。包括：回溯和递推包括：回溯和递推 两个过程两个过程 int fun(int n) z=n*fun(n-1); 第21页/共86页引例：了解递归问题的回溯和递归两个过程引例：了解递归问题的回溯和递归两个过程例例7.6 有有5个学生，个学生，问第问第5个学生几岁，他说比第个学生几岁，他说比第4个学生大个学

12、生大2岁。岁。问第问第4个学生几岁，他说比第个学生几岁，他说比第3个学生大个学生大2岁。岁。问第问第3个学生几岁，他说比第个学生几岁，他说比第2个学生大个学生大2岁。岁。问第问第2个学生几岁，他说比第个学生几岁，他说比第1个学生大个学生大2岁。岁。问第问第1个学生几岁，他说自己个学生几岁，他说自己10岁。岁。请问第请问第5个学生几岁？个学生几岁？ 假设此问题中，求年龄的函数为假设此问题中，求年龄的函数为int age(int n)第22页/共86页公式公式age(n)=10 n=1age(n-1) +2 n1第23页/共86页公式公式age(n)=10 n=1age(n-1) +2 n1推导公

13、式方法：推导公式方法： 1. 一般第一次回溯，例如由一般第一次回溯，例如由age(5)=age(4)+2,之后再抽象成一般形式，就可推导出上述公式。之后再抽象成一般形式，就可推导出上述公式。 2. 添加结束条件，即添加结束条件，即n=1或或0时的值。时的值。 第24页/共86页公式公式age(n)=10 n=1age(n-1) +2 n1推导公式方法：推导公式方法： 1. 一般第一次回溯，例如由一般第一次回溯，例如由age(5)=age(4)+2,之后再抽象成一般形式，就可推导出上述公式。之后再抽象成一般形式，就可推导出上述公式。 2. 添加结束条件，即添加结束条件，即n=1或或0时的值。时的

14、值。 推导出公式是解决递归问题的关键推导出公式是解决递归问题的关键第25页/共86页按照公式书写程序按照公式书写程序公式左边公式左边函数首部函数首部公式右边公式右边函数体函数体age(n)=10 n=1age(n-1) +2 n1第26页/共86页int age(int n) if(n=1) return 10; else return age(n-1)+2; 公式左边公式左边函数首部函数首部公式右边公式右边函数体函数体age(n)=10 n=1age(n-1) +2 n1按照公式书写程序按照公式书写程序第27页/共86页int age(int n) if(n=1) return 10; el

15、se return age(n-1)+2; 公式左边公式左边函数首部函数首部公式右边公式右边函数体函数体age(n)=10 n=1age(n-1) +2 n1按照公式书写程序按照公式书写程序注意：函数体中有函数自己注意：函数体中有函数自己第28页/共86页练习练习 例例7.7用递归方法求用递归方法求n！ 1.验证此问题是否可使用递归方法验证此问题是否可使用递归方法2. 推导公式：推导公式： （1） 一般第一次回溯一般第一次回溯 （2） 添加结束条件，即添加结束条件，即n=1或或0时的值。时的值。 第29页/共86页3层层15层层64层层Hanoi（汉诺）塔问题（汉诺）塔问题第30页/共86页

16、古典数学问题。古典数学问题。问题描述：古代有个一梵塔，塔内有问题描述：古代有个一梵塔，塔内有三个座三个座A、B、C，开始时开始时A座上有座上有64个盘子，盘子大小不等，个盘子，盘子大小不等，大的在下大的在下，小的在上小的在上。有一个老和尚想把这。有一个老和尚想把这64个盘子个盘子从从A座移到座移到C座座，但，但规定每次只允许移动一个盘子规定每次只允许移动一个盘子，且在移动过程，且在移动过程中，中，3个座上的盘子始终都是大的在下，小的在上。移个座上的盘子始终都是大的在下，小的在上。移动中可以利用动中可以利用B座座。要求。要求写出移动盘子的步骤写出移动盘子的步骤。ABCHanoi问题原型问题原型6

17、4第31页/共86页ABC第32页/共86页ABC（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C将三个盘子从将三个盘子从A移动到移动到C第33页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第34页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2

18、）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第35页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第36页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第37页/共86页ABC将三个盘子从将三个盘

19、子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第38页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第39页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个

20、紫色的从个紫色的从B移动到移动到C第40页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第41页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第42页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动

21、到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第43页/共86页ABC将三个盘子从将三个盘子从A移动到移动到C（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将）将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到C第44页/共86页（1）先将）先将2个紫色的从个紫色的从A移动到移动到B（2）将将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到CABC将三个盘子从将三个盘子从A移动到移动到C第45页/共86页ABC（1）将两个盘

22、子从将两个盘子从A移动到移动到B第46页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第47页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第48页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移

23、动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第49页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第50页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第51页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色

24、的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第52页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第53页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第54页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移

25、动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第55页/共86页ABC（1）将两个盘子从将两个盘子从A移动到移动到B先将先将1个绿色的从个绿色的从A移动到移动到C将将1个紫色的从个紫色的从A移动到移动到B最后将最后将1个绿色的从个绿色的从C移动到移动到B第56页/共86页（1）先将先将2个紫色的从个紫色的从A移动到移动到B（2）将将1个黄色的从个黄色的从A移动到移动到C（3）最后将）最后将2个紫色的从个紫色的从B移动到移动到CABC将三个盘子从将三个盘子从A移动到移动到C第57页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动

26、到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第58页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第59页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第60页/共86页ABC（3）将两个盘子从

27、将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第61页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第62页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第63页/共86页

28、ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第64页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第65页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移

29、动到C第66页/共86页ABC（3）将两个盘子从将两个盘子从B移动到移动到C先将先将1个绿色的从个绿色的从B移动到移动到A将将1个紫色的从个紫色的从B移动到移动到C最后将最后将1个绿色的从个绿色的从A移动到移动到C第67页/共86页（1）先将先将2个紫色的从个紫色的从A移动到移动到B（2）将将1个黄色的从个黄色的从A移动到移动到C（3）最后将最后将2个紫色的从个紫色的从B移动到移动到C将三个盘子从将三个盘子从A移动到移动到CABC第68页/共86页ABC思考：思考：1. ( 3, A, B, C ) 全程中全程中 第第1个个被移动的盘子位于被移动的盘子位于哪个座哪个座？ 此时该座此时该座共有几

30、个盘子共有几个盘子？ 这个这个被移动被移动的盘子是的盘子是哪个哪个？ 此位置此位置就是递推的开始就是递推的开始。第69页/共86页ABC思考：思考：2. 递推出递推出( 3, A, B, C )的移动序列。的移动序列。 并在动画中验证。并在动画中验证。3. 64个盘子或个盘子或n个盘子如何移动。个盘子如何移动。 结论：结论：Hanoi问题是典型的递归问题，问题是典型的递归问题，可以使用递归的方法解决。可以使用递归的方法解决。第70页/共86页推导公式：推导公式： 1. 一般第一次回溯，例如由一般第一次回溯，例如由age(5)=age(4)+2, 再抽象成一般形式，就可推导出上述公式。再抽象成一

31、般形式，就可推导出上述公式。 2. 添加结束条件，即添加结束条件，即n=1或或0时的值。时的值。 ABC第71页/共86页（3,A,B,C）（2,A,C,B） (2,B,A,C)(A-C)第一次回溯第一次回溯ABC推导公式：推导公式：进行抽象，进行抽象，3变成变成n，ABC变成变成xyz。第72页/共86页（n,x,y,z）（2,A,C,B） (2,B,A,C)(A-C)抽象：抽象：ABC推导公式：推导公式：3 A B C第73页/共86页（n,x,y,z）（n-1,x,z,y） (2,B,A,C)(A-C)抽象：抽象：ABC推导公式：推导公式：3 A B C第74页/共86页（n,x,y,z）