C语言程序设计项目教程项目三.pdf

C语言言程序序设计项目教教程 项目三共分为两个任务 项目三 算法——程序设计的灵魂 任务一 了解什么是算法 任务二 掌握算法的表示方法 项目拓展 算法的复杂度 任务一 了解什么是算法 任务说明任务说明 在本任务中我们将了解算法的概念和特性。 预备知识 一、什么是算法 二、算法的特性 为解决一个问题而采取的方法和步骤就称为算法。计算机能够 执行的算法可分为两大类： 数值运算算法 主要用于求解数值主要用于求解数值，如求复杂算式的值如求复杂算式的值、求方求方 程的根等； 非数值运算算法 主要用于事务管理领域主要用于事务管理领域，如图书检索如图书检索、公交汽公交汽 车车辆调度等。 二、算法的特性 （（11））有穷性有穷性 （2）确定性 （3）有效性 （4）存在零个或多个输入 （5）存在若干输出结果 任务实施——汉诺塔问题 汉诺塔汉诺塔 （（TowersTowers ofof HanoiHanoi， 下图为模拟汉诺下图为模拟汉诺 Hanoi为越南首都河内）也称河内之塔。 塔问题的模型玩具 它源于印度源于印度一个古个古老传说传说：大梵天创大梵天创 造世界的时候做了三根金刚石柱子， 在其中一根柱子上从下往上按照大小 顺序摞着64片黄金圆盘。大梵天命令 婆罗门把圆盘从下面开始按大小顺序 重新摆放在另重新摆放在另一根柱子上根柱子上。并且规定并且规定， 在小圆盘上不能放大圆盘，在三根柱 子之间一次只能移动一个圆盘。当盘 子全数搬运完毕之时，也就是世界末 日来临之时。 在本任务中我们就来编写算法解决汉诺塔问题，这里将柱子标为A、 B、、C，，要由要由A搬至搬至C，，假设假设A柱上的盘数为柱上的盘数为n，，n由用户输入由用户输入。 任务分析任务分析 汉诺塔问题是典型的递归调用问题。当n＝1时，直接将盘子从A移 动到动到CC即可即可。将将nn （（nn＞＞11））个盘子从个盘子从AA柱移动到柱移动到CC柱可以分为三个步骤柱可以分为三个步骤： ① 将n－1个盘子从A借助C移到B； ② 将最后一个盘子从A移到C； ③ 将n－1个盘子从B借助A移到C。 实施步骤 步骤步骤11 启动启动VisualVisual C++C++ 6.06.0，，新建一个新建一个C++C++源程序源程序，，在编辑区中输入在编辑区中输入 以下代码： #include#include stdiostdio.hh void hanoi(int n, char A, char B, char C) { if(n == 1) { printf(Move sheet %d from %c to %c\n, n, A, C); } else {{ hanoihanoi(n(n-1,1, A,A, C,C, B);B); printf(Move sheet %d from %c to %c\n, n, A, C); hanoi(n-1, B, A, C); } }} iint maiin()() { int n;; printf(请输入盘数：); scanf(%d, n); hanoihanoi(n(n, AA, BB, CC);); return 0; } 步骤2 编译、连接后执行程序，执行结果如下图所示。 （a）n=2时移动方法 （b）n=4时