算法语言与数据结构第5章.pptx

算法算法语言言与数与数据据结构构信息信息与与物流管理系物流管理系王健王健西安财经学院管理学院西安财经学院管理学院西安财经学院管理学院西安财经学院管理学院信息信息与与物流管理系物流管理系第5章 函数信息信息与与物流管理系物流管理系第第5章章 函数函数 IntroductionIntroduction1 1 Main titleMain title2 2 ExamplesExamples3 3 ConclusionConclusion4 4信息信息与与物流管理系物流管理系/*/*程 序：6_3.cpp（验证素数程序）*/*作 者：wuwh */*编制时间：2002年10月20日 */*主要功能：可验证某数是否为素数 */*#include/预编译命令#include /预编译命令int checkprime(int);/子函数声明int main()/主函数int a=0;/定义整型变量，初始化为0cout a;/键盘输入一个整数/用实参a调用子函数，该子函数的/返回值作为if语句的分支条件if(checkprime(a)/checkprime(a)为1cout a 是素数 endl;else/checkprime(a)为0cout a 不是素数 endl;/主函数结束第第5章章 函数函数信息信息与与物流管理系物流管理系/用实参 a 调用子函数，该子函数的/返回值作为 if 语句的分支条件if(checkprime(a)/checkprime(a)为 1cout a 是素数 endl;else /checkprime(a)为 0 cout a 不是素数 endl;/主函数结束第第5章章 函数函数信息信息与与物流管理系物流管理系 T checkprime(a)F cout a cout a 是素数 endl;不是素数 endl 第第5章章 函数函数信息信息与与物流管理系物流管理系bool checkprime(int b)/子函数，子函数，b为形式参数为形式参数int k=0;/定义整型变量，并初始化定义整型变量，并初始化for(k=2;k=sqrt(double)b);k+)/循环循环if(b%k=0)/如果如果b能够被能够被k整除，则返回整除，则返回0/可理解为可理解为“抢先抢先”返回返回0，有了，有了 return 0，/后面的后面的 return 1 不起作用了不起作用了return 0;return 1;/b不能被不能被k整除，则返回整除，则返回1第第5章章 函数函数信息信息与与物流管理系物流管理系bool checkprime(int b)int k=0;for(k=2;k=sqrt(double)b);k+)if(b%k=0)return 0;return 1;第第5章章 函数函数信息信息与与物流管理系物流管理系 bool checkprime(int b)/子函数子函数 int k=0;形式参数形式参数for(k=2;k=sqrt(double)b);k=K+1)if(b%k=0)return 0;return 1;/b不能被不能被k整除，则返回整除，则返回1 /说明说明 b 是质数是质数第第5章章 函数函数信息信息与与物流管理系物流管理系 讲这一程序的目的：讲这一程序的目的：1.如何定义一个函数如何定义一个函数2.主函数怎样调用子函数主函数怎样调用子函数3.实在参数和形式参数实在参数和形式参数4.返回值是什么意思返回值是什么意思信息信息与与物流管理系物流管理系 主函数与子函数的配合:主函数通主函数通过实参去参去调用子函数将用子函数将实参参赋给子函子函数中的形参；数中的形参；子函数运算之后，又将子函数运算之后，又将调用用结果返回果返回给主函主函数一个数一个值，这个个值作作为主函数判断主函数判断该实参是素数与参是素数与否的根据。否的根据。两者配合得天衣无两者配合得天衣无缝。第第5章章 函数函数信息信息与与物流管理系物流管理系 在checkprime(int b)函数中，有return 0 和 return 1 两处不同。如果先有return 0了，后面一条return 1 就不起作用了。不会既执行 return 0 又执行 return 1。第第5章章 函数函数信息信息与与物流管理系物流管理系 函数的说明函数的说明 放在主函数之前，告诉系统有放在主函数之前，告诉系统有 自定义的子函数可以被调用。自定义的子函数可以被调用。例：例：bool checkprime(int);信息信息与与物流管理系物流管理系 函数的定义函数的定义函数返回值的类型函数返回值的类型 函数名函数名(类型名类型名 形式参数形式参数1 1，类型名，类型名 形式参数形式参数2 2，.)/函数体函数体 说明部分说明部分 语句部分语句部分 信息信息与与物流管理系物流管理系 形式参数和实在参数形式参数和实在参数 bool checkprime(int bool checkprime(int afaf););/定义定义定义定义 af af 是形式参数，是形式参数，特点：特点：1.1.未被调用不占内存单元；未被调用不占内存单元；2.2.被调用后系统为其分配内存单元；被调用后系统为其分配内存单元；3.3.调用结束释放内存单元；调用结束释放内存单元；4.4.作用域限定在子函数内，属于局部变量。作用域限定在子函数内，属于局部变量。信息信息与与物流管理系物流管理系 被调用函数嵌套在被调用函数嵌套在 if if 语句中，语句中，a a 是实在参数是实在参数 if(checkPrime(if(checkPrime(a a)主函数主函数 调用调用 checkPrime(checkPrime(afaf)子函数子函数 形式参数形式参数信息信息与与物流管理系物流管理系 实在参数是一个具有确定值的表达式实在参数是一个具有确定值的表达式 一个函数在调用子函数时，要将实在参数赋给形式参数一个函数在调用子函数时，要将实在参数赋给形式参数 调用时调用时 17 1717 17 实在参数实在参数 a a 形式参数形式参数 afaf信息信息与与物流管理系物流管理系 调用调用 输入输入输入输入a a 子函数子函数子函数子函数 if(checkPrime(if(checkPrime(a a)checkPrime(checkPrime(afaf)执行执行执行执行 if if 语句语句语句语句 for:i=2,3 for:i=2,3 =1 =0 =1 =0 af%i=0 !=0 af%i=0 !=0 输出输出输出输出 输出输出输出输出 return 0 return 1 return 0 return 1 a a是质数是质数是质数是质数 a a不是质数不是质数不是质数不是质数 返回返回信息信息与与物流管理系物流管理系 int main()int a=0;cout a;if(checkprime(a)bool checkprime(int b)int k=0;for(k=2;k=sqrt(double)b);k+)if(b%k=0)return 0;return 1;cout a 是素数 endl;elsecout a 不是素数 endl;信息信息与与物流管理系物流管理系 美声唱法歌手大奖赛美声唱法歌手大奖赛 裁判人数裁判人数 n=10,n=10,打分范围打分范围 60=x=100,60=x=100,10 10人中打分的最大值人中打分的最大值 maxmax 10 10人中打分的最小值人中打分的最小值 minmin 10 10人打分总和为人打分总和为 sumsum 选手最后得分为选手最后得分为:(sum Max Min)/(N 2)(sum Max Min)/(N 2)信息信息与与物流管理系物流管理系/*/*程 序：6_2.cpp */*作 者：wuwh */*编制时间：2002年10月20日 */*主要功能：给歌手打分 */*信息信息与与物流管理系物流管理系#include#include#include#include int Max(int,int)int Max(int,int)int Min(int,int)int Min(int,int)int main()int main()int p=0;int p=0;int q=100;int q=100;int sum=0 int sum=0，x=0;x=0;int i=1;int i=1;信息信息与与物流管理系物流管理系 for(i=1;i=10;i=i+1)for(i=1;i=10;i=i+1)cout“cout“请第请第”i“i“位裁判给分位裁判给分”endl;x;cin x;p=Max(x,p);p=Max(x,p);q=Min(x,q);q=Min(x,q);sum=sum+x;sum=sum+x;cout“cout“选手得分选手得分”(sum-p-q)/(10-2);b)if (a b)return areturn a;else return b;else return b;int Min(int c,int d)int Min(int c,int d)if (c d)if (c d)return creturn c;else return d;else return d;信息信息与与物流管理系物流管理系 问题：编程求解问题：编程求解现假定现假定现假定现假定 n=6n=6，k=4k=4思路：思路：思路：思路：1 1、该式可分解为、该式可分解为、该式可分解为、该式可分解为 2 2、定义一个函数、定义一个函数、定义一个函数、定义一个函数 i=1,2,n l=k信息信息与与物流管理系物流管理系 让让 l l=4,i=1,2,.,6=4,i=1,2,.,6这个函数可以表示这个函数可以表示3 3、再定义一个函数、再定义一个函数、再定义一个函数、再定义一个函数 让让让让 m=nm=n，i=1,2,mi=1,2,m，即可得解，即可得解，即可得解，即可得解信息信息与与物流管理系物流管理系/*/*/*/*程程 序：序：6_2.cpp *6_2.cpp */*/*作作 者：者：wuwh *wuwh */*/*编制时间：编制时间：20022002年年1010月月1212日日 */*/*主要功能：求幂函数的和（介绍函数）主要功能：求幂函数的和（介绍函数）*/*/*信息信息与与物流管理系物流管理系#include#include/预编译命令预编译命令constconst int n=6;int n=6;/定义常量定义常量 n n 为为 6 6constconst int k=4;int k=4;/定义常量定义常量 k k 为为 4 4int SOP(int m,int l);/int SOP(int m,int l);/声明函数声明函数SOPSOPint power(int p,int q);/int power(int p,int q);/声明函数声明函数powerpower信息信息与与物流管理系物流管理系/输出结果输出结果,其中其中SOP(n,k)SOP(n,k)为被调用函数为被调用函数int main()int main()/主函数主函数 cout cout Sum ofSum of k/k/提示信息提示信息 from from th powers of integers 1 toth powers of integers 1 to n n is is SOP(n,k)SOP(n,k)endl;endl;信息信息与与物流管理系物流管理系/以下函数是被主程序调用的函数以下函数是被主程序调用的函数/功能：计算功能：计算1,2,.,m1,2,.,m的的l l次幂的和次幂的和int int SOPSOP(int m,int l)/,m,l(int m,int l)/,m,l 为形参为形参 int i,sum;int i,sum;sum=0;/sum=0;/初始化累加器初始化累加器for(i=1;i=m;i+)for(i=1;i=m;i+)sum=sum+sum=sum+powerpower(i,l)(i,l);/;/累加累加return return sumsum;/返回值返回值 信息信息与与物流管理系物流管理系/以下函数是被函数以下函数是被函数sop(n,k)sop(n,k)调用的函数调用的函数/功能：计算功能：计算p p的的q q次幂次幂int int powerpower(int p,int q)(int p,int q)int i,product;int i,product;product=1;product=1;/初始化累乘器初始化累乘器for(i=1;i=q;i+)for(i=1;i=q;i+)product=product*p;/product=product*p;/累乘累乘returnreturn product product;信息信息与与物流管理系物流管理系 int int SOPSOP(int m,int l)m 6 l 4(int m,int l)m 6 l 4 power(1,l)power(1,l)1 1 int power(int p,int q)int power(int p,int q)power(2,l)1 power(2,l)1 1616 int power(int p,int q)int power(int p,int q)16 16 power(m,l)power(m,l)12961296 int power(int p,int q)int power(int p,int q)22752275 1296 1296信息信息与与物流管理系物流管理系数据类型数据类型数据类型数据类型 函数名函数名函数名函数名(形式参数表形式参数表形式参数表形式参数表 )例例:int power(int p,int n)power 为函数名，要以英文字母开头。为函数名，要以英文字母开头。int 是函数值的数据类型，这里是是函数值的数据类型，这里是int（整型）。（整型）。(int p,int n)括号中的括号中的 p,n为函数的形式参数，形式为函数的形式参数，形式参数也要定义其数据类型。参数也要定义其数据类型。信息信息与与物流管理系物流管理系函数定义的一般格式：()信息信息与与物流管理系物流管理系形式参数与实在参数1、形式参数形式参数是在定义函数时放在函数名后括号中的参数。在是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发生未进行函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束后，函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。释放掉行参所占的内存单元。2、因此，形参变量属于局部变量，其作用域在它所在的函数、因此，形参变量属于局部变量，其作用域在它所在的函数体内。体内。3、在定义函数的时候，必须指定形参变量的类型，如下所示、在定义函数的时候，必须指定形参变量的类型，如下所示int power(int p,int n)/函数体函数体 c信息信息与与物流管理系物流管理系4、实在参数是一个具有确定值的表达式。函数在调用时，将实在参数赋给形式参数。比如，主函数调用SOP(n,k)，这时，n,k为实在参数，n的值为6，k的值为4。在被调用函数定义中，int SOP(m,l)中的 m,l 为形式参数，在SOP被调用时，系统给 m,l 这两个形式参数分配了内存单元。之后，n 的值 6 赋给 m;k 的值 4 赋给 l。信息信息与与物流管理系物流管理系power(i,l)处在 SOP(m,l)函数中，表示SOP函数去调用 power 函数。其中 i,l 为实在参数，而 int power(p,q)中的 p,q 为形式参数。比如，执行 SOP(6,4)时，l=4,m=6,当 i=1 时，sum=sum+power(1,4)这里 1，4 为实在参数，调用power(p,q)，两个形式参数 p,q 分别被赋以 1，4。信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处理的特点，现举一例递递 推推信息信息与与物流管理系物流管理系【例例例例5.35.3】A A、B B、C C、D D、E E五人合伙夜间捕鱼，凌晨时五人合伙夜间捕鱼，凌晨时五人合伙夜间捕鱼，凌晨时五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了，都疲惫不堪，各自在河边的树丛中找地方睡着了，日上三竿，日上三竿，日上三竿，日上三竿，A A第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家去了，多余的一条扔回湖中，拿自己的一份回家去了，B B第二个醒来，也将鱼平分为五份，扔掉多余的一条，第二个醒来，也将鱼平分为五份，扔掉多余的一条，第二个醒来，也将鱼平分为五份，扔掉多余的一条，第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份，接着只拿走自己的一份，接着只拿走自己的一份，接着只拿走自己的一份，接着C C、D D、E E依次醒来，也依次醒来，也依次醒来，也依次醒来，也都按同样的办法分鱼。问五人至少合伙捕到多少条都按同样的办法分鱼。问五人至少合伙捕到多少条都按同样的办法分鱼。问五人至少合伙捕到多少条都按同样的办法分鱼。问五人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？鱼？每个人醒来后看到的鱼数是多少条？鱼？每个人醒来后看到的鱼数是多少条？鱼？每个人醒来后看到的鱼数是多少条？信息信息与与物流管理系物流管理系解题思路解题思路:假定假定假定假定A A、B B、C C、D D、E E 五人的编号分别为五人的编号分别为五人的编号分别为五人的编号分别为1 1、2 2、3 3、4 4、5 5，整数数组，整数数组，整数数组，整数数组 fishk fishk 表示第表示第表示第表示第 k k 个人所个人所个人所个人所看到的鱼数。看到的鱼数。看到的鱼数。看到的鱼数。fish1 fish1 表示表示表示表示A A所看到的鱼数，所看到的鱼数，所看到的鱼数，所看到的鱼数，fish2 fish2 表示表示表示表示 B B 所看到的鱼数所看到的鱼数所看到的鱼数所看到的鱼数fish1 fish1 为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数为五人合伙捕鱼的总鱼数fish2=(fish1-1)*4/5fish2=(fish1-1)*4/5fish3=(fish2-1)*4/5fish3=(fish2-1)*4/5fish4=(fish3-1)*4/5fish4=(fish3-1)*4/5fish5=(fish4-1)*4/5fish5=(fish4-1)*4/5信息信息与与物流管理系物流管理系写成一般式fish i =(fish i -1 1)*4/5i=2,3,5这个公式可用于知这个公式可用于知 A A 看到的鱼数去推算看到的鱼数去推算 B B 看到的，再推算看到的，再推算 C C 看到的，看到的，.。现在要求的是。现在要求的是 A A 看到的，能否倒过来，先知看到的，能否倒过来，先知 E E 看到的再反推看到的再反推 D D 看到的，看到的，直到，直到A A看到的。为此将上式改写为：看到的。为此将上式改写为：fish i-1 =fish i *5/4+1fish i-1 =fish i *5/4+1i=5,4,2i=5,4,2信息信息与与物流管理系物流管理系分析上式.当 i=5 时，fish 5 表示 E 醒来所看到的鱼数，该数应满足被整除后余，即fish 5%5 =1 2.当 i=5 时，fish i-1 表示 D 醒来所看到的鱼数，这个数既要满足fish 4 =fish 5 *5/4+1 又要满足fish 4%5=1显然，fish 4 不能不是整数，这个结论同样可以用至 fish 3,fish 2 和 fish 1 信息信息与与物流管理系物流管理系3.按题意要求 5 人合伙捕到的最少鱼数，可以从小往大枚举，可以先让 E 所看到的鱼数最少为 6 条，即 fish 5 初始化为 6 来试，之后每次增加 5 再试，直至递推到 fish 1 得整数且除以 5 之后的余数为 1。根据上述思路，我们可以构思如下的程序框图：信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系该图可分为三部分该图可分为三部分(1)是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始化为 1 和和定义循环控制变量定义循环控制变量 i，并初始化为，并初始化为 0。(2)是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2).1 是枚举过程中的是枚举过程中的 fish5 的初值设置，一开始的初值设置，一开始 fish5=1+5;以后每次增以后每次增 5。(2).2 是一个是一个 for 循环，循环，i 的初值为的初值为 4，终值为，终值为 1，步长，步长为为-1，该循环的循环体是一个分支语句，该循环的循环体是一个分支语句，如果如果 fishi+1不能被不能被 4 整除，则跳出整除，则跳出 for 循环（使用循环（使用 break 语句）语句）;否则，从否则，从 fishi+1 算出算出 fishi。信息信息与与物流管理系物流管理系当由 break 语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish 5 加 5 后再试，即重新进入直到型循环 do while 的循环体。当着正常退出 for 循环时，一定是控制变量 i 从初值 4，一步一步执行到终值 1，每一步的鱼数均为整数，最后 i=0，表示计算完毕，且也达到了退出直到型循环的条件。(3)输出计算结果信息信息与与物流管理系物流管理系/*/*程 序 名：5_3.c（五人合伙捕鱼）*/*作 者：wuwh */*编制时间：2002年10月2日 */*主要功能：递推算法的实现 */*#include /预编译命令void main()/主函数 int fish6=1,1,1,1,1,1;/整型数组，记录每人醒来后看到的鱼数 int i=0;do fish5=fish5+5;/让E看到的鱼数增5。for(i=4;i=1;i-)if(fishi+1%4!=0)break;/跳出for循环elsefishi=fishi+1*5/4+1;/计算第i人看到的鱼数 while(i=1);/当 i=1 继续做do循环 /输出计算结果 for(i=1;i1 时，时，A 的取值即的取值即 C 的值，而的值，而 C 的值即的值即 E 的值，为了求得的值，为了求得 E 的值，需要先求出的值，需要先求出 D 的值。的值。D 值值 fact(n-1)乘以乘以 n 即为即为 E 的值。的值。信息信息与与物流管理系物流管理系与结点可能有多个相关联的点，这时可描述为下图与结点可能有多个相关联的点，这时可描述为下图A 结点的值最终为结点的值最终为 D 的值，但为了求的值，但为了求 D 需先求需先求 B 和和 C。从图上看。从图上看,先求左边的点才能求最右边的点的先求左边的点才能求最右边的点的值，我们约定最右边值，我们约定最右边 D 点的值就是点的值就是 A 结点的值。结点的值。信息信息与与物流管理系物流管理系下面我们以下面我们以3！为例来画与或结点图，目的是体！为例来画与或结点图，目的是体会递归的含义。会递归的含义。C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=6信息信息与与物流管理系物流管理系下面画出了调用和返回的递归示意图下面画出了调用和返回的递归示意图信息信息与与物流管理系物流管理系从图可以想象：从图可以想象：欲求欲求 fact(3)，先要求，先要求 fact(2)；要求；要求 fact(2)先先求求 fact(1)。就象剥一颗圆白菜，从外向里，一层层。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到剥下来，到了菜心，遇到 1 的阶乘，其值为的阶乘，其值为1，到达，到达了递归的边界。然后再用了递归的边界。然后再用 fact(n)=n*fact(n-1)这个这个普遍公式，从里向外倒推回去得到普遍公式，从里向外倒推回去得到 fact(n)的值。的值。为了把这个问题说得再透彻一点。我们画了如下为了把这个问题说得再透彻一点。我们画了如下的流程图：的流程图：信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系为了形象地描述递归过程，将上图改画成下图为了形象地描述递归过程，将上图改画成下图信息信息与与物流管理系物流管理系在这个图中在这个图中“内层内层”与与“外层外层”有着相同的结构。它有着相同的结构。它们之间们之间“你中有我，我中有你你中有我，我中有你”，呈现相互依存的关，呈现相互依存的关系。系。为了进一步讲清递归的概念，将递归与递推做一比较。为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。仍以求阶乘为例。递推是从已知的初始条件出发，逐次去求所需要的阶递推是从已知的初始条件出发，逐次去求所需要的阶乘值。乘值。如求如求 3！初始条件初始条件 fact(1)=1fact(2)=2*fact(1)=2fact(3)=3*fact(2)=6信息信息与与物流管理系物流管理系这相当于从菜心这相当于从菜心“推到推到”外层。而递归算法的出外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。下面我们将会看到，归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子哈诺（人皆知的例子哈诺（Hanoi）塔问题。）塔问题。信息信息与与物流管理系物流管理系故事：故事：相传在古代印度的相传在古代印度的 Bramah 庙中，有位僧人整天把三庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把根柱子上的金盘倒来倒去，原来他是想把64个一个比个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将照上述规则将64只盘子从一个柱子移至另一个柱子上，只盘子从一个柱子移至另一个柱子上，所需时间约为所需时间约为5800亿年。亿年。信息信息与与物流管理系物流管理系怎样编写这种程序？思路上还是先从最简单的情况分析怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为1，这时只，这时只需将该盘从需将该盘从A搬至搬至C，一次完成，记为，一次完成，记为move 1 from A to C (演示演示)ABC1信息信息与与物流管理系物流管理系2、在、在A柱上有二只盘子，柱上有二只盘子，1为小盘，为小盘，2为大盘。为大盘。第（第（1）步将）步将1号盘从号盘从A移至移至B，这是为了让，这是为了让2号盘能移动；号盘能移动；第（第（2）步将）步将2号盘从号盘从A移至移至C；第（第（3）步再将）步再将1号盘从号盘从B移至移至C；这三步记为（演示）：这三步记为（演示）：ABC21move 1 from A to B;move 2 from A to C;move 3 form B to C;信息信息与与物流管理系物流管理系3、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第（第（1）步）步 将将1号盘和号盘和2号盘视为一个整体；先将二者作号盘视为一个整体；先将二者作为整体从为整体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能够一次移至C的机会。的机会。这一步记为这一步记为 move(2,A,C,B)意思是将上面的意思是将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第（第（2）步）步 将将3号盘从号盘从A移至移至C，一次到位。记为，一次到位。记为 move 3 from A to C第（第（3）步）步 处于处于B上的作为一个整体的上的作为一个整体的2只盘子，再移至只盘子，再移至C。这一步记为这一步记为 move(2,B,A,C)意思是将意思是将2只盘子作为整体从只盘子作为整体从B借助借助A移至移至C。所谓借助是什么意思，等这件事做完了不言自明。所谓借助是什么意思，等这件事做完了不言自明。信息信息与与物流管理系物流管理系move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)ABC213演示：移动演示：移动3 3个个盘子盘子的分解的分解信息信息与与物流管理系物流管理系move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,A,B,C)move(2,B,A,C)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)ABC213信息信息与与物流管理系物流管理系4、从题目的约束条件看，大盘上可以随便摞小、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将盘，相反则不允许。在将1号和号和2号盘当整体从号盘当整体从A移至移至B的过程中的过程中 move(2,A,C,B)实际上是分实际上是分解为以下三步解为以下三步第（第（1）.1步：步：move 1 form A to C;第（第（1）.2步：步：move 2 form A to B;第（第（1）.3步：步：move 1 form C to B;信息信息与与物流管理系物流管理系经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造了条创造了条件。同样，件。同样，3号盘一旦到了号盘一旦到了 C，就要考虑如何，就要考虑如何实现将实现将 1 号和号和 2 号盘当整体从号盘当整体从 B 移至移至 C 的过的过程了。实际上程了。实际上 move(2,B,A,C)也要分解为三也要分解为三步：步：第（第（3）.1步：步：move 1 form B to A;第（第（3）.2步：步：move 2 form B to C;第（第（3）.3步：步：move 1 form A to C;信息信息与与物流管理系物流管理系5、看、看 move(2,A,C,B)是说要将是说要将 2 只盘子从只盘子从 A 搬至搬至 B，但没有，但没有 C 是不行的，因为第（是不行的，因为第（1）.1步就要将步就要将 1 盘从盘从 A 移到移到 C，给，给 2 盘创造条件盘创造条件从从 A 移至移至 B，然后再把，然后再把 1 盘从盘从 C 移至移至 B。看。看到这里就能明白借助到这里就能明白借助 C 的含义了。因此，在的含义了。因此，在构思搬移过程的参量时，要把构思搬移过程的参量时，要把 3 个柱子都用上。个柱子都用上。信息信息与与物流管理系物流管理系6、定义搬移函数、定义搬移函数 move(n,A,B,C)，物理意义是，物理意义是将将 n 只盘子从只盘子从 A 经经 B 搬到搬到 C考虑到前面已考虑到前面已经研究过的经研究过的(1)(2)(3)步，可步，可以将搬移过程以将搬移过程用如下的与或用如下的与或结点图表示。结点图表示。信息信息与与物流管理系物流管理系这里用与或结点的含义是分解为这里用与或结点的含义是分解为(1)(2)(3)步。这步。这3步是相关的，相互依存的，而且是有序的，从左至右步是相关的，相互依存的，而且是有序的，从左至右执行。执行。move(n,A,B,C)分解为分解为3步步(1)move(n-1,A,C,B)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从A经经C移至移至B；(2)输出输出n：A to C，理解将，理解将n号盘从号盘从A移至移至C，是直接可，是直接可解结点；解结点；(3)Move(n-1,B,A,C)理解为将上面的理解为将上面的n-1只盘子作为一只盘子作为一个整体从个整体从B经经A移至移至C。信息信息与与物流管理系物流管理系这里显然是一种递归定义，当着解这里显然是一种递归定义，当着解 move(n-1,A,C,B)时又可想到，将其分解为时又可想到，将其分解为 3 步：步：第第1步：将上面的步：将上面的n-2只盘子作为一个整体从只盘子作为一个整体从A经经B到到C，move(n-2,A,B,C)；第第2步：第步：第n-1号盘子从号盘子从A直接移至直接移至B，即，即n-1:A to B；第第3步：再将上面的步：再将上面的n-2只盘子作为一个整体从只盘子作为一个整体从C经经A移至移至B，move(n-2,C,A,B)；下面，我们还是以下面，我们还是以3只盘子为例画出递归的与或图。只盘子为例画出递归的与或图。信息信息与与物流管理系物流管理系这个图很象一颗倒置着的树，结点这个图很象一颗倒置着的树，结点move(3,A,B,C)是树是树根，与结点是树的分枝，叶子都是直接可解结点。根，与结点是树的分枝，叶子都是直接可解结点。信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系信息信息与与物流管理系物流管理系/*/*程程 序：序：6_hanoi2002.cpp */*作作 者：者：wuwh */*编制时间：编制时间：2002年年10月月13日日 */*主要功能：用递归求解主要功能：用递归求解Hanoi问题问题 */*#include/预编译命令预编译命令int step=1;/整型全局变量整型全局变量,预置预置1,步数步数void move(int m,char p,char q,char r);/声明要用到的被调用函数声明要用到的被调用函数void main()/主函数主函数/主程序开始主程序开始int n;/整型变量整型变量,n为盘数为盘数,printf(请输入盘数请输入盘数 n=“);/提示信息提示信息scanf(“/%d”),&n);/输入正整数输入正整数nprintf(在在3根柱子上移根柱子上移%d只盘的步骤为只盘的步骤为:“,n);/输出提示信息输出提示信息 move(n,a,b,c);/调用函数调用函数 move(n,a,b,c)/主函数结束主函数结束信息信息与与物流管理系物流管理系/以下函数是被主程序调用的函数以下函数是被主程序调用的函数/函数名：函数名：move/输输 入：入：m，整型变量，表示盘子数目，整型变量，表示盘子数目/p，q，r为字符型变量，表示柱子标号