汉诺塔课件学习教案.pptx

会计学 1汉诺塔课件第一页，共87 页。Contents7.1 为什么要用函数(hnsh)7.2 怎样定义(dngy)函数7.3 调用函数7.4 函数声明(shngmng)和函数原型7.5 函数的嵌套调用第 1 页/共 86 页第二页，共87 页。Contents7.6 函数(hnsh)的递归调用7.7 数组作函数参数7.8 局部变量和全局变量7.9 变量(binling)存储方式和生存期7.10 变量的声明(shngmng)和定义第 2 页/共 86 页第三页，共87 页。复习(fx)将事先编好的函数，采用“组装”的办法简化(jinhu)程序设计的过程。1.模块化程序设计(chn x sh j)思路main()a()b()c()d()e()f()h()g()m()第 3 页/共 86 页第四页，共87 页。复习(fx)将事先编好的函数，采用“组装”的办法简化(jinhu)程序设计的过程。function 功能。所以(suy)，从本质意义来说函数就是用来完成一定功能的。1.模块化程序设计思路2.函数是从英文哪个单词翻译过来的第 4 页/共 86 页第五页，共87 页。复习(fx)将事先编好的函数，采用“组装(z zhun)”的办法简化程序设计的过程。function 功能(gngnng)。所以，从本质意义来说函数就是用来完成一定功能(gngnng)的。则使用函数可以实现代码的（）性。1.模块化程序设计思路2.函数是从英文哪个单词翻译过来的3.若程序中要多次实现某一功能第 5 页/共 86 页第六页，共87 页。复习(fx)将事先编好的函数，采用(ciyng)“组装”的办法简化程序设计的过程。function 功能。所以(suy)，从本质意义来说函数就是用来完成一定功能的。则使用函数可以实现代码的（重用）性。1.模块化程序设计思路2.函数是从英文哪个单词翻译过来的3.若程序中要多次实现某一功能第 6 页/共 86 页第七页，共87 页。复习(fx)形参 实参4.函数调用过程(guchng)int max(int x,int y)int max(int x,int y)int z;int z;z=(xy)?x,y;z=(xy)?x,y;return z;return z;c=max(a,b);c=max(a,b);(main函数(hnsh)值3 9第 7 页/共 86 页第八页，共87 页。复习(fx)int max(int x,int y)int max(int x,int y)int z;int z;z=(xy)?x,y;z=(xy)?x,y;return z;return z;c=max(a,b);c=max(a,b);(main 函数(hnsh)形参 实参值3 94.函数调用过程(guchng)第 8 页/共 86 页第九页，共87 页。复习(fx)int max(int x,int y)int max(int x,int y)int z;int z;z=(xy)?x,y;z=(xy)?x,y;return z;return z;c=max(a,b);c=max(a,b);(main函数(hnsh)形参 实参值3 994.函数调用过程(guchng)第 9 页/共 86 页第十页，共87 页。复习(fx)int max(int x,int y)int max(int x,int y)int z;int z;z=(xy)?x,y;z=(xy)?x,y;return z;return z;c=max(a,b);c=max(a,b);(main函数(hnsh)调用调用(dioyng)(dioyng)前，前，形参形参xx和和yy不占内存不占内存调用时，为形参调用时，为形参xx和和yy分配内存分配内存结束时，结束时，释放释放xx和和yy 形参 实参值3994.函数调用过程第 10 页/共 86 页第十一页，共87 页。复习(fx)声明(shngmng)的作用5.函数(hnsh)声明把函数头信息把函数头信息,如如int max(int x,int y)int max(int x,int y)通知给编译系统，以便在调用时系统通知给编译系统，以便在调用时系统按按此此检查检查调用的合法性调用的合法性。c=max(a,b);c=max(a,b);第 1 1 页/共 86 页第十二页，共87 页。复习(fx)在 哪里 对 谁 进行声明：主调函数(hnsh)内部对被调用函数(hnsh)进行声明5.函数(hnsh)声明若若main()main()调用调用max()max()，则在（，则在（）函数内）函数内部，对（部，对（）函数进行声明。）函数进行声明。第 12 页/共 86 页第十三页，共87 页。复习(fx)在 哪里 对 谁 进行(jnxng)声明：主调函数内部对被调用函数进行(jnxng)声明5.函数(hnsh)声明若若main()main()调用调用max()max()，则在（，则在（mainmain）函数）函数内部，对（内部，对（maxmax）函数进行声明。）函数进行声明。第 13 页/共 86 页第十四页，共87 页。复习(fx)声明方法：函数(hnsh)原型（首部）加分号5.函数(hnsh)声明void main()void main()int a,b;int a,b;int max(int x,int y);int max(int x,int y);第 14 页/共 86 页第十五页，共87 页。复习(fx)与函数定义的区别：函数定义是指对函数功能(gngnng)的确立。包括函数首部和函数体两部分5.函数(hnsh)声明int max(int x,int y)int max(int x,int y)int z;int z;z=xy?x:y;z=xy?x:y;return z;return z;与变量类似，先定义，后使用。第 15 页/共 86 页第十六页，共87 页。复习(fx)在（）情况(qngkung)下，声明也可以被省略。5.函数(hnsh)声明int max(int x,int y)int max(int x,int y)int z;int z;z=xy?x:y;z=xy?x:y;return z;return z;void main()void main()int a=3,b=9,c;int a=3,b=9,c;c=max(a,b);c=max(a,b);第 16 页/共 86 页第十七页，共87 页。复习(fx)在（）情况下，声明也可以(ky)被省略。5.函数(hnsh)声明int max(int x,int y)int max(int x,int y)int z;int z;z=xy?x:y;z=xy?x:y;return z;return z;void main()void main()int a=3,b=9,c;int a=3,b=9,c;c=max(a,b);c=max(a,b);主函数和其它函数，表面上平行并列 的关系，实际上是主调与被调 的关系第 17 页/共 86 页第十八页，共87 页。复习(fx)一个函数(hnsh)的执行过程中，又去调用另一函数(hnsh)。6.函数(hnsh)的嵌套调用int int max4max4(int a,int b,int c,int d)(int a,int b,int c,int d)int m,n;int m,n;m=m=max2max2(a,b);(a,b);n=n=max2max2(c,d);(c,d);return return max2max2(m,n);(m,n);第 18 页/共 86 页第十九页，共87 页。复习(fx)一个函数的执行过程(guchng)中，又去调用自己本身。一种(y zhn)特殊的嵌套调用int int fun(int n)fun(int n)int c;int c;if(n=1)c=0;if(n=1)c=0;else else c=n*c=n*fun(n-1)fun(n-1)return return c;c;第 19 页/共 86 页第二十页，共87 页。复习(fx)一个(y)函数的执行过程中，又去调用自己本身。一种(y zhn)特殊的嵌套调用int int fun(int n)fun(int n)int c;int c;if(n=1)c=0;if(n=1)c=0;else else c=n*c=n*fun(n-1)fun(n-1)return return c;c;第 20 页/共 86 页第二十一页，共87 页。7.6 函数(hnsh)的递归调用定义(dngy)函数执行的过程中，直接或者间接的调用该函数本身(bnshn)，称为函数的递归调用。包括：回溯和递推 两个过程 int fun(int n)z=n*fun(n-1);第 21 页/共 86 页第二十二页，共87 页。引例(yn l)：了解递归问题的回溯和递归两个过程例7.6 有5 个学生(xu sheng)，问第5 个学生(xu sheng)几岁，他说比第4 个学生(xu sheng)大2 岁。问第4 个学生(xu sheng)几岁，他说比第3 个学生(xu sheng)大2 岁。问第3 个学生(xu sheng)几岁，他说比第2 个学生(xu sheng)大2 岁。问第2 个学生(xu sheng)几岁，他说比第1 个学生(xu sheng)大2 岁。问第1 个学生(xu sheng)几岁，他说自己10 岁。请问第5 个学生(xu sheng)几岁？假设此问题中，求年龄的函数为int age(int n)第 22 页/共 86 页第二十三页，共87 页。公式(gngsh)age(n)=10 n=1age(n-1)+2 n1第 23 页/共 86 页第二十四页，共87 页。公式(gngsh)age(n)=10 n=1age(n-1)+2 n1推导公式方法：1.一般第一次回溯，例如由age(5)=age(4)+2,之后再抽象成一般形式，就可推导出上述公式。2.添加(tin ji)结束条件，即n=1 或0 时的值。第 24 页/共 86 页第二十五页，共87 页。公式(gngsh)age(n)=10 n=1age(n-1)+2 n1推导公式方法：1.一般(ybn)第一次回溯，例如由age(5)=age(4)+2,之后再抽象成一般(ybn)形式，就可推导出上述公式。2.添加结束条件，即n=1 或0 时的值。推导出公式是解决递归问题(wnt)的关键第 25 页/共 86 页第二十六页，共87 页。按照(nzho)公式书写程序公式(gngsh)左边函数首部 公式右边(yu bian)函数体age(n)=10 n=1age(n-1)+2 n1第 26 页/共 86 页第二十七页，共87 页。int age(int n)if(n=1)return 10;else return age(n-1)+2;公式左边(zu bian)函数首部 公式右边(yu bian)函数体age(n)=10 n=1age(n-1)+2 n1按照公式(gngsh)书写程序第 27 页/共 86 页第二十八页，共87 页。int age(int n)if(n=1)return 10;else return age(n-1)+2;公式(gngsh)左边函数首部公式右边(yu bian)函数体age(n)=10 n=1age(n-1)+2 n1按照(nzho)公式书写程序注意：函数体中有函数自己第 28 页/共 86 页第二十九页，共87 页。练习(linx)例7.7 用递归方法求n！1.验证此问题是否可使用(shyng)递归方法2.推导公式：（1）一般第一次回溯（2）添加结束条件，即n=1 或0 时的值。第 29 页/共 86 页第三十页，共87 页。3 层15 层64 层Hanoi（汉诺）塔问题(wnt)第 30 页/共 86 页第三十一页，共87 页。古典数学问题。古典数学问题。问题描述：古代有个一梵塔，塔内有三个座 问题描述：古代有个一梵塔，塔内有三个座A A、B B、C C，开，开始 始(kish(kish)时 时A A 座上有 座上有64 64 个盘子，盘子大小不等，大的在下，个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这 小的在上。有一个老和尚想把这64 64 个盘子从 个盘子从A A 座移到 座移到C C 座，座，但规定每次只允许移动一个盘子，且在移动过程中，但规定每次只允许移动一个盘子，且在移动过程中，3 3 个座 个座上的盘子始终都是大的在下，小的在上。移动中可以利用 上的盘子始终都是大的在下，小的在上。移动中可以利用B B座。要求写出移动盘子的步骤。座。要求写出移动盘子的步骤。A B CHanoi 问题(wnt)原型64第 31 页/共 86 页第三十二页，共87 页。A B C第 32 页/共 86 页第三十三页，共87 页。A B C（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到C将三个盘子(pn zi)从A 移动到C第 33 页/共 86 页第三十四页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C第 34 页/共 86 页第三十五页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到C第 35 页/共 86 页第三十六页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C第 36 页/共 86 页第三十七页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C第 37 页/共 86 页第三十八页，共87 页。A BC将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C第 38 页/共 86 页第三十九页，共87 页。A BC将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到C第 39 页/共 86 页第四十页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到C第 40 页/共 86 页第四十一页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C第 41 页/共 86 页第四十二页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到C第 42 页/共 86 页第四十三页，共87 页。A B C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C第 43 页/共 86 页第四十四页，共87 页。AB C将三个盘子(pn zi)从A 移动到C（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到C第 44 页/共 86 页第四十五页，共87 页。（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到CA B C将三个盘子(pn zi)从A 移动到C第 45 页/共 86 页第四十六页，共87 页。A B C（1）将两个盘子(pn zi)从A 移动到B第 46 页/共 86 页第四十七页，共87 页。A B C（1）将两个盘子(pn zi)从A 移动到B 先将1 个绿色的从A 移动(ydng)到C 将1 个紫色的从A 移动(ydng)到B 最后将1 个绿色的从C 移动(ydng)到B第 47 页/共 86 页第四十八页，共87 页。A BC（1）将两个(lin)盘子从A 移动到B 先将1 个绿色(l s)的从A 移动到C 将1 个紫色的从A 移动到B 最后将1 个绿色(l s)的从C 移动到B第 48 页/共 86 页第四十九页，共87 页。A B C（1）将两个(lin)盘子从A 移动到B 先将1 个绿色(l s)的从A 移动到C 将1 个紫色的从A 移动到B 最后将1 个绿色(l s)的从C 移动到B第 49 页/共 86 页第五十页，共87 页。A B C（1）将两个盘子(pn zi)从A 移动到B 先将1 个绿色(l s)的从A 移动到C 将1 个紫色的从A 移动到B 最后将1 个绿色(l s)的从C 移动到B第 50 页/共 86 页第五十一页，共87 页。A B C（1）将两个盘子(pn zi)从A 移动到B 先将1 个绿色(l s)的从A 移动到C 将1 个紫色的从A 移动到B 最后将1 个绿色(l s)的从C 移动到B第 51 页/共 86 页第五十二页，共87 页。A B C（1）将两个盘子(pn zi)从A 移动到B 先将1 个绿色(l s)的从A 移动到C 将1 个紫色的从A 移动到B 最后将1 个绿色(l s)的从C 移动到B第 52 页/共 86 页第五十三页，共87 页。AB C（1）将两个盘子(pn zi)从A 移动到B 先将1 个绿色的从A 移动(ydng)到C 将1 个紫色的从A 移动(ydng)到B 最后将1 个绿色的从C 移动(ydng)到B第 53 页/共 86 页第五十四页，共87 页。A B C（1）将两个(lin)盘子从A 移动到B 先将1 个绿色(l s)的从A 移动到C 将1 个紫色的从A 移动到B 最后将1 个绿色(l s)的从C 移动到B第 54 页/共 86 页第五十五页，共87 页。A B C（1）将两个盘子(pn zi)从A 移动到B 先将1 个绿色的从A 移动(ydng)到C 将1 个紫色的从A 移动(ydng)到B 最后将1 个绿色的从C 移动(ydng)到B第 55 页/共 86 页第五十六页，共87 页。A B C（1）将两个(lin)盘子从A 移动到B 先将1 个绿色的从A 移动(ydng)到C 将1 个紫色的从A 移动(ydng)到B 最后将1 个绿色的从C 移动(ydng)到B第 56 页/共 86 页第五十七页，共87 页。（1）先将2 个紫色的从A 移动到B（2）将1 个黄色(hungs)的从A 移动到C（3）最后将2 个紫色的从B 移动到CA B C将三个盘子(pn zi)从A 移动到C第 57 页/共 86 页第五十八页，共87 页。A B C（3）将两个盘子(pn zi)从B 移动到C 先将1 个绿色的从B 移动(ydng)到A 将1 个紫色的从B 移动(ydng)到C 最后将1 个绿色的从A 移动(ydng)到C第 58 页/共 86 页第五十九页，共87 页。A B C（3）将两个(lin)盘子从B 移动到C 先将1 个绿色的从B 移动(ydng)到A 将1 个紫色的从B 移动(ydng)到C 最后将1 个绿色的从A 移动(ydng)到C第 59 页/共 86 页第六十页，共87 页。A B C（3）将两个(lin)盘子从B 移动到C 先将1 个绿色的从B 移动(ydng)到A 将1 个紫色的从B 移动(ydng)到C 最后将1 个绿色的从A 移动(ydng)到C第 60 页/共 86 页第六十一页，共87 页。A B C（3）将两个(lin)盘子从B 移动到C 先将1 个绿色(l s)的从B 移动到A 将1 个紫色的从B 移动到C 最后将1 个绿色(l s)的从A 移动到C第 61 页/共 86 页第六十二页，共87 页。A B C（3）将两个(lin)盘子从B 移动到C 先将1 个绿色的从B 移动(ydng)到A 将1 个紫色的从B 移动(ydng)到C 最后将1 个绿色的从A 移动(ydng)到C第 62 页/共 86 页第六十三页，共87 页。ABC（3）将两个(lin)盘子从B 移动到C 先将1 个绿色的从B 移动(ydng)到A 将1 个紫色的从B 移动(ydng)到C 最后将1 个绿色的从A 移动(ydng)到C第 63 页/共 86 页第六十四页，共87 页。A B C（3）将两个(lin)盘子从B 移动到C 先将1 个绿色(l s)的从B 移动到A 将1 个紫色的从B 移动到C 最后将1 个绿色(l s)的从A 移动到C第 64 页/共 86 页第六十五页，共87 页。AB C（3）将两个盘子(pn zi)从B 移动到C 先将1 个绿色的从B 移动(ydng)到A 将1 个紫色的从B 移动(ydng)到C 最后将1 个绿色的从A 移动(ydng)到C第 65 页/共 86 页第六十六页，共87 页。A B C（3）将两个盘子(pn zi)从B 移动到C 先将1 个绿色(l s)的从B 移动到A 将1 个紫色的从B 移动到C 最后将1 个绿色(l s)的从A 移动到C第 66 页/共 86 页第六十七页，共87 页。AB C（3）将两个盘子(pn zi)从B 移动到C 先将1 个绿色(l s)的从B 移动到A 将1 个紫色的从B 移动到C 最后将1 个绿色(l s)的从A 移动到C第 67 页/共 86 页第六十八页，共87 页。（1）先将2 个紫色的从A 移动(ydng)到B（2）将1 个黄色的从A 移动(ydng)到C（3）最后将2 个紫色的从B 移动(ydng)到C将三个盘子(pn zi)从A 移动到CA B C第 68 页/共 86 页第六十九页，共87 页。A B C思考：1.(3,A,B,C)全程中 第1 个被移动的盘子位于哪个座？此时该座共有几个(j)盘子？这个被移动的盘子是哪个？此位置就是递推的开始。第 69 页/共 86 页第七十页，共87 页。A B C思考：2.递推出(3,A,B,C)的移动序列。并在动画中验证(ynzhng)。3.64 个盘子或n 个盘子如何移动。结论：Hanoi 问题是典型的递归问题，可以使用递归的方法(fngf)解决。第 70 页/共 86 页第七十一页，共87 页。推导公式(gngsh)：1.一般第一次回溯，例如由age(5)=age(4)+2,再抽象成一般形式，就可推导出上述公式(gngsh)。2.添加结束条件，即n=1 或0 时的值。A B C第 71 页/共 86 页第七十二页，共87 页。（3,A,B,C）（2,A,C,B）(2,B,A,C)(A-C)第一次回溯(hu s)AB C推导(tudo)公式：进行(jnxng)抽象，3 变成n，ABC 变成xyz。第 72 页/共 86 页第七十三页，共87 页。（n,x,y,z）（2,A,C,B）(2,B,A,C)(A-C)抽象(chuxing)：A B C推导(tudo)公式：3AB C第 73 页/共 86 页第七十四页，共87 页。（n,x,y,z）（n-1,x,z,y）(2,B,A,C)(A-C)抽象(chuxing)：A B C推导(tudo)公式：3 AB C第 74 页/共 86 页第七十五页，共87 页。（n,x,y,z）（n-1,x,z,y）(2,B,A,C)(x-z)抽象(chuxing)：A B C推导(tudo)公式：3 A B C第 75 页/共 86 页第七十六页，共87 页。（n,x,y,z）（n-1,x,z,y）(n-1,y,x,z)(x-z)抽象(chuxing)：A B C推导(tudo)公式：3 AB C添加结束(jish)条件：即如果n=1，则(x-z)第 76 页/共 86 页第七十七页，共87 页。按公式书写(shxi)程序（n,x,y,z）函数(hnsh)首部（n-1,x,z,y）(n-1,y,x,z)(x-z)n=1，则(x-z)函数(hnsh)体第 77 页/共 86 页第七十八页，共87 页。按公式书写(shxi)程序void hanoi(int n,char x,char y,z)（n,x,y,z）函数(hnsh)首部（n-1,x,z,y）(n-1,y,x,z)(x-z)n=1，则(x-z)函数(hnsh)体第 78 页/共 86 页第七十九页，共87 页。按公式(gngsh)书写程序void hanoi(int n,char x,char y,z)if(n=1)printf(“%c-%c”,x,z);else hanoi(n-1,x,z,y);printf(“%c-%c”,x,z);hanoi(n-1,y,x,z);（n,x,y,z）函数(hnsh)首部（n-1,x,z,y）(n-1,y,x,z)(x-z)n=1，则(x-z)函数(hnsh)体第 79 页/共 86 页第八十页，共87 页。运行64 的源程序，解决(jiju)梵塔问题。第 80 页/共 86 页第八十一页，共87 页。执行过程(guchng)中，函数调用自己本身 递归 定义(dngy)回顾(hug)第 81 页/共 86 页第八十二页，共87 页。执行(zhxng)过程中，函数调用自己本身回溯(hu s)和递推 递归 定义(dngy)递归的两个过程回顾第 82 页/共 86 页第八十三页，共87 页。执行过程(guchng)中，函数调用自己本身回溯(hu s)和递推判断问题是否为递归问题推导出公式按公式书写(shxi)程序。递归 定义递归的两个过程 解决递归关键问题回顾第 83 页/共 86 页第八十四页，共87 页。浪费空间，运行(ynxng)效率较低但为问题提出了解决方法 改进优点优点(yudin(yudin)缺点缺点(qudin)(qudin)递归问题特点程序结构清晰,可读性好第 84 页/共 86 页第八十五页，共87 页。BHJSJ第 85 页/共 86 页第八十六页，共87 页。感谢您的观看(gunkn)。第 86 页/共 86 页第八十七页，共87 页。