《C程序设计项目教程（第2版）》项目二

C程序设计项目教程主讲教师：宋玉璞目录项目1项目2项目3项目4项目5项目6C程序概述算法C语法基础分支语句循环语句数组

项目7项目9项目8项目10函数指针构造数据类型文件2算法——程序设计的灵魂项目项目2

算法知识目标了解算法的概念和特点。掌握流程图和N-S流程图的表示方法。能力目标素质目标学会绘制流程图和N-S流程图。能利用流程图和N-S流程图表示算法。学会多角度看待问题，转换角度解决问题。养成事前规划、事后总结的习惯。项目2

算法项目导读广义上说，算法是完成某件事情的方法和步骤。在计算机领域，算法即为计算机解决问题的处理步骤。著名的计算机科学家沃思（N.Wirth）曾提出一个经典公式：数据结构＋算法＝程序这一公式说明编写程序的关键就在于合理地组织数据和设计算法，如果说数据结构是程序的躯体，那么算法就是程序的灵魂。项目2

算法任务1解析汉诺塔游戏什么是算法

一任务1

解析汉诺塔游戏算法是为解决某一问题而提出的准确而完整的方案，是解决问题的方法和步骤。例如，乘坐火车通常可分为以下几步：购买车票→进站→刷证件→上车→到达目的地→下车。这些步骤是按一定顺序进行的，缺一不可。在计算机领域，算法是对计算机中执行的运算过程的具体描述，包括数值运算算法和非数值运算算法。数值运算的目的是求数值解，如求三角形面积、方程求解等。非数值运算涉及面比较广，如人事信息管理、成绩管理、图书管理等。什么是算法

一任务1

解析汉诺塔游戏对于同一个问题，不同的人往往会有不同的解题方法和步骤。例如，计算S=1+2+3+…+

99+100的值。有人会采用逐个数相加的方法，即先计算1加2，再加3，再加4，如此反复，一直加到100；而有人会利用巧算公式先计算1+99、2+98、3+97……，再计算有多少个这样的加法；还有人会利用等差数列的求和公式

来进行计算。显然，相比第一种算法，后面两种算法要简单很多。由此可见，对于同一个问题的解题方法也有优劣之分，为了有效地进行解题，不仅需要保证算法的正确性，还需要考虑算法的质量。算法的特点

一任务1

解析汉诺塔游戏一般来讲，一个有效的算法应具有以下5个特点。（1）有穷性。一个算法必须在执行有限个操作步骤后终止，且每一个步骤都须在有限的时间内完成。例如，等差数列求和时，这个数列必须是有限的，如果没有这个限制，计算机将一直累加下去而无法停止。（2）确定性。算法中每步操作的含义都必须是明确的，即为要执行的每步操作做出清晰而严格的规定。例如，在温度控制程序中，不能出现诸如“温差较大时，系统迅速升温或降温”等模糊词语。算法的特点

一任务1

解析汉诺塔游戏一般来讲，一个有效的算法应具有以下5个特点。（3）有效性，也称可行性。即算法中的每步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数除以0就是一个无效操作，应当避免这种操作。（4）有零个或多个输入。这里的输入是指在算法开始之前所需要的初始数据。输入的多少取决于特定的问题。例如，求等差数列1+2+3+…+n的累加时，需要输入n的值；再如，项目一中的任务只有输出而没有输入。（5）有一个或多个输出。在一个完整的算法中至少会有一个输出。编写程序的目的就是要得到一个结果，如果程序运行完没有任何结果输出，那编写程序也就失去了意义。实施案例一.案例分析将汉诺塔游戏抽象为数学问题。如图所示，从左到右有A、B、C三根柱子，其中，A柱有从小叠到大的n个圆盘。现要求将A柱的圆盘移到C柱，期间应遵守一个规则：一次只能移动一个圆盘，且大圆盘只能在小圆盘下面，求移动的步骤和移动的次数。任务1

解析汉诺塔游戏汉诺塔游戏框图

实施案例二.算法分析根据汉诺塔游戏的规则，要想将n个圆盘从A柱移到C柱，须先将上面的n−1个圆盘移到B柱，然后就可以将第n个圆盘直接从A柱移到C柱，最后将移走的n−1个圆盘从B柱移到C柱。因此，该问题转换成了移动n−1个圆盘的问题。要将n−1个圆盘从A柱移到B柱，须先将上面的n−2个圆盘移到C柱，然后将第n−1个圆盘从A柱移到B柱，最后将移走的n−2个圆盘从C柱移到B柱。可见，该问题转换成了移动n−2个圆盘的问题。任务1

解析汉诺塔游戏实施案例二.算法分析依次类推，最终转换成移动最上面1个圆盘的问题。为了便于理解，先来分析将3个圆盘从A柱移到C柱的过程。移动前的情况如图所示。任务1

解析汉诺塔游戏移动前

实施案例二.算法分析移动移动步骤如下：（1）将上面的2个圆盘从A柱移到B柱（借助C柱），如图所示；任务1

解析汉诺塔游戏第一步

实施案例二.算法分析移动移动步骤如下：（2）将第3个圆盘从A柱移到C柱，如图所示；任务1

解析汉诺塔游戏第二步

实施案例二.算法分析移动移动步骤如下：（3）将2个圆盘移到C柱（借助A柱），如图所示。任务1

解析汉诺塔游戏第三步

实施案例二.算法分析其中第（2）步可直接实现，第（1）步和第（3）步又可分解为3步。第（1）步可分解为：①将第1个圆盘从A柱移到C柱；②将第2个圆盘从A柱移到B柱；③将第1个圆盘从C柱移到B柱。第（3）步可分解为：①将B柱上1个圆盘移到A柱；②将B柱上剩下的圆盘移到C柱；③将A柱上圆盘移到C柱。将以上步骤综合起来，将3个圆盘从A柱移到C柱共经历7（即23−1）步，即A→C、A→B、C→B、A→C、B→A、B→C、A→C。将4个圆盘从A柱移到C柱共经历15（即24−1）步，即将上面的3个圆盘从A柱移到B柱（7步），然后移动第4个圆盘（1步），再将上面的3个圆盘从B柱移到C柱（7步）。任务1

解析汉诺塔游戏实施案例二.算法分析由上面的分析可以推断，将n个圆盘从A柱移到C柱需经历2n−1步。这些步骤又可以概括为以下3步。（1）将上面的n−1个圆盘从A柱移到B柱（借助C柱）；（2）将第n个圆盘从A柱移到C柱；（3）将B柱上n−1个圆盘移到C柱（借助A柱）。任务1

解析汉诺塔游戏实施案例三.算法描述从算法分析可以看出，第（1）步和第（3）步都是把n−1个圆盘从一个柱移到另一个柱，采取的方法是一样的，只是柱子的名称不同而已。将3个柱子分别用变量a、b和c表示，设n个圆盘借助b柱从a柱移到c柱的函数为Hanoi（n,a,b,c），则算法可用以下文字描述。S1：如果n=1，输出“a→c”，结束；否则，执行S2。S2：将n−1个圆盘从a移动到b（借助c），即Hanoi（n−1,a,c,b）。S3：将第n个圆盘从a移到c，即“a→c”。S4：将n−1个圆盘从b移动到c（借助a），即Hanoi（n−1,b,a,c）。这种使用S1、S2等序号代表执行顺序对算法进行描述的方法称为自然语言表示。用自然语言表示算法的优点是通俗易懂，缺点是文字冗长，不严谨，表示复杂算法时不方便。任务1

解析汉诺塔游戏任务2判定是否是闰年算法的表示流程图

一任务2

判定是否是闰年算法流程图用一些图框来表示各种操作，用流程线来表示算法的执行方向。用图形表示算法，直观形象，易于理解。1．流程图符号美国国家标准协会（Americannationalstandardsinstitute，ANSI）规定了一些常用的流程图符号，其名称及含义如表所示。流程图

一任务2

判定是否是闰年算法1．流程图符号图形符号名称含义起止框算法的起点和终点，是任何流程图必不可少的输入、输出框数据的输入和输出操作处理框各种形式数据的处理判断框判断条件是否成立，成立时在出口处标注“是”或“Y”，

不成立时标注“否”或“N”预定义过程一个特定过程，如函数流程线连接各个图框，表示执行的顺序连接点将画在不同地方的流程线连接起来流程图

一任务2

判定是否是闰年算法2．基本结构为了提高算法的质量，Bohra和Jacopini在1966年提出了3种基本结构，即顺序结构、选择结构和循环结构。这3种结构之间可以并列，也可以相互包含，但不能交叉。（1）顺序结构是简单的线性结构，各操作按照它们出现的先后顺序执行。如图所示，在执行完A框中指定的操作后执行B框中指定的操作。顺序结构

流程图

一任务2

判定是否是闰年算法2．基本结构【例2-2-1】请用流程图表示算法，根据长方形的长和宽，计算其面积。【问题分析】

要计算长方形的面积，首先需要输入长方形的长a和宽b的值，然后利用公式S=a×b求出S的值，最后输出S的值，其流程图表示如图所示。计算长方形的面积

流程图

一任务2

判定是否是闰年算法2．基本结构（2）选择结构，也称分支结构。在选择结构中必包含一个判断框，根据判断条件P是否成立而选择执行A框或B框，如图所示。选择结构

流程图

一任务2

判定是否是闰年算法2．基本结构【例2-2-2】请用流程图表示算法，输入某同学某门课程成绩，判断该同学是否通过考试，输出判断结果。【问题分析】

判断某同学是否通过考试，首先须输入该同学的成绩score，然后判断score是否大于或等于60，若成立，则表示通过，否则表示未通过，其流程图表示如图所示。判断某同学是否通过考试

流程图

一任务2

判定是否是闰年算法2．基本结构（3）循环结构又称重复结构，即反复执行某一部分的操作，直到条件不成立时终止循环。按照判定条件出现的位置不同，可将循环结构分为当型循环结构和直到型循环结构。当型循环结构，先判断循环条件P是否成立，如果成立就执行A框中指定的操作，执行完A框后再判断循环条件P是否成立，如果成立，再次执行A框。如此反复，直到循环条件P不成立，结束循环。当型循环结构

流程图

一任务2

判定是否是闰年算法2．基本结构直到型循环结构，先执行A框中指定的操作，然后判断循环条件P是否成立，如果成立执行A框，然后再判断循环条件P是否成立，如果成立，再次执行A框。如此反复，直到循环条件P不成立，结束循环。直到型循环结构

流程图

一任务2

判定是否是闰年算法2．基本结构【例2-2-3】

用流程图表示S=1+2+3+…+n的算法。【问题分析】从式中可以看出，这是前n项自然数求和（等差数列求和），每一项和前一项的差为1，其流程图可以用当型循环结构来表示，如图所示。先判断i的值是否小于等于n，如果成立，才执行循环体（S=S+i和i自加1）。接下来再判断i的值，如此循环下去，直到i的值小于等于n不成立。此例也可以用直到型循环结构来表示（见图），先执行循环体，再进行判断，这种情况下无论判断条件是否成立，循环体中的语句至少会被执行一次。当型循环结构求和

流程图

一任务2

判定是否是闰年算法2．基本结构【例2-2-3】

用流程图表示S=1+2+3+…+n的算法。【问题分析】从式中可以看出，这是前n项自然数求和（等差数列求和），每一项和前一项的差为1，其流程图可以用当型循环结构来表示，如图所示。先判断i的值是否小于等于n，如果成立，才执行循环体（S=S+i和i自加1）。接下来再判断i的值，如此循环下去，直到i的值小于等于n不成立。此例也可以用直到型循环结构来表示（见图），先执行循环体，再进行判断，这种情况下无论判断条件是否成立，循环体中的语句至少会被执行一次。直到型循环结构求和

N-S流程图

二任务2

判定是否是闰年算法N-S流程图又称盒图，是由美国学者I.Nassi和B.Shneiderman提出的，故以他们姓氏的首字母命名。他们认为既然任何算法都是由前面介绍的3种基本结构组成的，那么各基本结构之间的流程线就是多余的。因此，在N-S流程图中完全去掉了流程线，全部算法都写在一个大矩形框内，这个大矩形框又由若干个小的基本框图构成。同样，N-S流程图也包括顺序、选择和循环3种基本结构。N-S流程图

二任务2

判定是否是闰年算法1．顺序结构顺序结构的N-S流程图如图1所示，它表示顺序执行A框和B框。【例2-2-4】

将例2-2-1的算法用N-S流程图表示。【问题分析】本例可采用顺序结构的N-S流程图形式实现，如图2所示。图1顺序结构

图2计算长方形的面积

N-S流程图

二任务2

判定是否是闰年算法2．选择结构选择结构的N-S流程图如图1所示，它表示先判断条件P，当条件成立时执行A框，不成立时执行B框。【例2-2-5】

将例2-2-2的算法用N-S流程图表示。【问题分析】本例的N-S流程图可以采用选择结构来实现，如图2所示。图1选择结构

图2判断是否通过考试N-S流程图

二任务2

判定是否是闰年算法3．循环结构当型循环结构的N-S流程图如图1所示，当P成立时，循环执行A框；直到型循环结构的N-S流程图如图2所示，循环执行A框，直到P成立。图1当型循环

图2直到型循环N-S流程图

二任务2

判定是否是闰年算法3．循环结构【例2-2-6】

将例2-2-3的算法用N-S流程图表示。【问题分析】本例的N-S流程图用当型循环结构表示如图1所示，用直到型循环结构表示如图2所示。图1当型循环求和