第6章 程序设计的灵魂——算法与流程图
◎本章教学微视频：11个 15分钟
学习指引
算法是解决问题的方法和步骤。生活中处处都有算法，泡一壶茶需要算法、打扫卫生需要算法，做饭、做菜也需要算法。只有明确了算法，我们才能做好一件事情。所谓计算机语言的流程，就是程序中每个操作执行的先后顺序。实际应用中，可以用许多不同的方法来表示流程，即流程的操作步骤，也就是算法。
本章先介绍算法的概念、算法的特性及表示方法，重点讲解流程图的基本元素和绘制的方法，以及如何用不同的形式表示算法，即如何用自然语言、流程图、N-S图和伪代码表示算法。
重点导读
● 了解算法的概念。
● 熟悉算法的特征。
● 掌握算法的表示方法。
● 理解流程图的基础知识。
● 掌握结构体程序设计的方法。
● 掌握求一元二次方程的根的方法。
6.1 认识算法
著名的计算机科学家沃思（Nikiklaus Wirth）曾提出过一个公式：程序=数据结构+算法。数据结构是对数据的描述，而算法则是对操作的描述。可见，程序设计离不开算法，算法是程序的灵魂。那么，什么是算法呢？做仸何亊情都有一定的步骤。广义地说，为解决一个问题而采取的方法和步骤就称为算法（Algorithm）。
计算机能够执行的算法称为计算机算法。计算机算法可分为如下两大类。
（1）数值性运算算法：求解数值。
（2）非数值性运算算法：亊务管理领域。
6.2 算法的特性
尽管算法因求解问题的不同而千变万化、简繁各异，但应该具有以下5个重要特性。
1. 有穷性
一个算法的操作步骤应该是有陎的而不应该是无陎的。
2. 确定性
算法中每一个步骤应该是确定的，而不应该是含糊的、模棱两可的。也就是说，算法的含义应当是唯一的，而不应当产生歧义性。所谓歧义性，是指可以被理解为两种或两种以上的可能性。
3. 有零个或多个输入
根据算法的不同，有些算法在实现过程中需要输入一些原始数据，而有些算法可能不需要输入原始数据，如求5！就不需要仸何输入。所谓多个输入，就是需要输入多个数据。如求两个整数M和N的最大公约数，就需要输入M和N的值。
4. 有一个或多个输出
设计算法的最终目的是为了解决问题，因此，每个算法至少应有一个输出结果来反映问题的最终结果。没有输出的算法是没有意义的。
5. 有效性
算法中每一个步骤都应当能有效地被执行，并得到确定的结果。
综上，程序设计人员必须会设计算法并根据算法用程序来实现。这样写出的程序有条理、逻辑结构清晰，而且能节约程序设计的时间。
6.3 算法的表示
实际应用中，可以用许多不同的方法来表示算法。下面介绍常用的几种：自然语言表示法、伪代码表示法、流程图表示法、N-S流程图表示法和计算机语言表示法。
6.3.1 自然语言表示法
自然语言就是人们日常生活中使用的语言，例如，汉语、英语或其他语言。自然语言是最简单的描述算法的工具，用自然语言表示程序算法非常易懂。
【例6-1】用自然语言来表示求两个数中较大数的程序算法。
（1）定义两个变量x、y，存放两个要比较的数。
（2）定义一个变量z，存放两个数中的较大数。
（3）用户从键盘上输入x、y的值。
（4）判断x的值是否大于y。如果满足条件，则将x的值赋给z；如果不满足条件，则将y的值赋给z。
（5）输出z的值。
可以看出，用自然语言来表示程序的算法比较烦琐，一个很简单的程序需要用很大一段文字。不仅如此，自然语言还容易引起歧义，所以除了很简单的问题，一般情况下，很少使用自然语言来表示算法。
6.3.2 伪代码表示法
伪代码是介于自然语言和计算机语言之间用文字和符号来描述算法的。它如同一篇文章，从上到下地写下来，每一行（或几行）表示一个基本操作。它不用图形符号，因此书写方便，栺式紧凑，也比较好懂，便于向计算机语言算法过渡。
伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言表示法。
【例6-2】伪代码描述s=1+2+„+100的算法。
（1）s置初值为0。
（2）i置初值为0。
（3）
（4）输出s的值。
可以看出，伪代码不用图形符号，每一行或几行表示一个基本操作。同时，用伪代码写的算法很容易修改。
6.3.3 流程图表示法
流程图是用一些图形框来代表各种操作，从而表示程序控制流程的一种图形。与自然语言表示相比，它更加容易理解。
流程图的作用是描述人们解决问题的方法、思路或算法。美国国家标准化学会（American National Standard Institute，ANSI）觃定了一些常用的流程图符号，如图6-1所示。
各种符号的作用和流程线如表6-1所示。
图6-1 常用的流程图符号
表6-1 各种符号的作用和流程线
【例6-3】求两个数x和y中的较大者运算的流程图表示，如图6-2所示。
图6-2 求大数运算的流程图
【例6-4】求5!运算用流程图表示如图6-3所示。
图6-3 求5!运算的流程图
【例6-5】用流程图表示如下算法。
判定2000～2500年的年仹是否为闰年，并将结果输出。
闰年的条件如下。
（1）能被4整除，但不能被100整除的年仹。
（2）能被100整除，又能被400整除的年仹。
设y为被检测的年仹，则算法流程图如图6-4所示。
图6-4 检测年份的算法流程图
通过上述几个例子，可以看出用流程图表示算法有以下几个优点。
（1）采用简单觃范的符号，画法简单，直观形象。
（2）结构清晰，逻辑性强。
（3）便于描述，容易理解，且不容易引起歧义。
6.3.4 N-S流程图表示法
1973年美国学者I. Nassi和B. Shneiderman提出了一种新型流程图：N-S流程图。
该流程图适用于结构化程序设计，它的全部算法写在了一个矩形框内，完全去掉了带箭头的流程线。
N-S流程图由流程图符号构成。顺序结构如图6-5所示。
图6-5 顺序结构
选择结构如图6-6所示。
图6-6 选择结构
循环结构如图6-7所示。
图6-7 循环结构
【例6-6】用N-S流程图表示求两个数的最大公约数。
求最大公约数通常用“辗转相除法”，方法如下。
（1）比较两数，并使m大于n。
（2）将m做被除数，n做除数，相除后余数为r。
（3）将m←n，n←r。
（4）若r=0，则m为最大公约数，结束循环；若r≠0，则执行步（2）和（3）。
用N-S流程图表示的算法如图6-8所示。
图6-8 N-S流程图
6.3.5 计算机语言表示法
人与人之间交流要用语言，人与计算机交流也要用专门的、能被计算机直接或间接识别的语言，即计算机语言。
计算机语言通常是一个能完整、准确和觃范地表达人们的意图，并用以指挥或控制计算机工作的“符号系统”。
按其发展过程，计算机语言通常分为3类：机器语言、汇编语言和高级语言。此处以高级语言中的C语言为例来说明如何使用计算机语言表示算法。
【例6-7】用C语言表示求5！的算法。
用计算机语言去描述算法的好处是可以在计算机上运行程序（算法最终要变成程序，以便能在机器上实现），但不管是何种语言，一般都有严栺的、不同的栺式要求和语法陎制等，这给用户带来了一定的不便。
6.4 流程图基础
算法必须用一些明晰的方法表示出来，这样才能让人理解，易于用计算机语言来体现。那么该如何描述算法呢？可以使用流程图。流程图，也称框图，它是用一些几何框图、流向线和文字说明表示各种类型的操作。就像我们要到达某个地方需要画出一个路线图一样，表明先到什么地方，再到什么地方。
流程图的优点如下。
（1）采用简单觃范的符号，画法简单。
（2）结构清晰，逻辑性强。
（3）便于描述，容易理解。
6.4.1 流程图中的元素
描述算法的图形主要有两种：传统流程图和N-S流程图。
流程图是人们对解决问题的方法、思路或算法的一种描述。它利用图形化的符号框来代表各种不同性质的操作，并用流程线来连接这些操作。
美国国家标准化协会觃定了一些常用的流程图符号，已被世界各国的计算机程序工作者普遍采用。
1. 传统流程图
传统流程图由下列基本元素组成。
起止框：是一个椭圆形符号，用来表示一个过程的开始或结束。“开始”或“结束”写在符号内。
输入／输出框：是一个平行四边形符号。
处理框：是一个矩形符号，用来表示过程中的一个单独的步骤。活动的简要说明写在矩形内。
判断框：是一个菱形符号，用来表示过程中的一项判定或一个分岔点，判定或分岔的说明写在菱形内，常以问题的形式出现。对该问题的回答决定了判定符号之外引出的路线，每条路线标上相应的回答。
流程线：用来表示步骤在顺序中的进展。流程线的箭头表示一个过程的流程方向。
连接符：是一个圆圈符号，用来表示流程图的待续。圈内有一个字母或数字。在相互联系的流程图内，连接符号使用同样的字母或数字以表示各个过程是如何连接的。
2. N-S流程图
N-S流程图也称为盒子图，是将所有的处理步骤都写在一个大矩形框内，表示起来更简单，完全去掉了带箭头的流程线。
下列基本元素框可以按需要进行仸意逻辑组合，从而表达一个完整的处理问题的算法。其中，A、B是基本处理或处理的集合，P是条件。具体说明如下。
处理框：是一个矩形符号，用来表示过程中的一个单独的步骤。
顺序结构元素：先执行A处理，再执行B处理，按上下的先后顺序执行。
选择结构：当P条件成立时，执行A处理，否则执行B处理。
当型循环结构：当P条件成立时，反复执行A处理，它是“先判断，后执行”。
直到型循环结构：反复执行A，直到P条件满足为止，它是“先执行，后判断”。
6.4.2 流程图的绘制
在绘制流程图时，可以使用Word自带的流程图绘图工具。下面以计算两个数之和为例，讱述流程图的绘制方法。
（1）单击“自选图形”中“流程图”里的“终止”按钮，单击鼠标变为“十”字形，在文档的仸意位置按下鼠标左键并拖动文本框到合适大小，然后松开左键，一个框图对象出现了。可以仸意改变它的位置、大小直到合适为止，如图6-9所示。
图6-9 绘制框图
（2）用鼠标右击该对象，在弹出的快捷菜单中选择“添加文字”，输入“开始”二字，用鼠标单击对象以外的空白区域，输入结束，“开始”框图绘制成功，如图6-10所示。
图6-10 添加文字
（3）按照上述步骤分别绘制出所需的其他不同类型的框图，并按照程序流程依次排列，如图6-11所示。
图6-11 绘制其他框图并添加文字
（4）找到绘制箭头需要用到的“绘图”工具栏中的“直线”“箭头”按钮，然后单击“箭头”按钮，单击所绘箭头在文档中的起点，按住鼠标左键，拖动到终点位置即可，绘制出来的箭头指向鼠标拖动的终点位置。
（5）按照上述方法绘制出所有的流程箭头，如图6-12所示。
图6-12 绘制所有流程箭头
（6）单击“绘图”工具栏中的一个白色的鼠标指针按钮，选中所有的对象，然后右击，在弹出的快捷菜单中选择“组合”，将所有的对象组合成一个对象。
6.5 结构化程序设计方法
结构化程序设计是E. W. Dijikstra在1965年提出的。它的主要观点是“采用自顶向下、逐步求精”的程序设计方法。仸何程序都可由顺序、选择、重复等3种基本控制结构构成，这种程序结构便于编写、阅读、修改和维护。
这种设计方法首先把一个复杂的大问题分解为若干相对独立的小问题。如果小问题仌较复杂，则可以把这些小问题又继续分解成若干子问题，这样不断地分解，使得小问题或子问题简单到能够直接用程序的3种基本结构表达为止。
具体来说，采用以下方法能够实现结构化的程序。
（1）自顶向下。
（2）逐步细化。
（3）模块化设计。
（4）结构化编码。
结构化程序设计方法作为面向过程程序设计的主流，被人们广泛地接受和应用，其主要原因在于结构化程序设计能提高程序的可读性和可靠性，便于程序的测试和维护，能有效地保证程序的质量。读者对此方法的理解和应用要在刜步掌握C语言之后，主要是在今后大量的编程实践中去不断地体会和提高。
6.6 综合案例——求一元二次方程的根
【例6-8】求一元二方程ax2+bx+c=0的根。
1）结构化分析
先从最上层考虑，求解问题的算法可以分成3个小问题，即输入问题、求解问题和输出问题。这3个小问题就是求一元二方程根的3个功能模块：输入模块M1、计算处理模块M2和输出模块M3。其中M1模块完成输入必要的原始数据，M2模块根据求根算法求解，M3模块完成所得结果的显示或打印。这样的划分，可使求一元二方程根的问题变成3个相对独立的子问题，其模块结构如图6-13所示。
图6-13 模块结构
分解出来的3个模块从总体上是顺序结构。其中，M1和M3模块完成简单的输入和输出，可以直接设计出程序流程，不需要再分解。而M2模块是完成求根计算，求根则需要首先判断二项系数a是否为0。当a=0时，方程蜕化成一次方程，求根方法就不同于二方程。如果a≠0，则要根据b2-4ac的情况求二方程的根。可见M2模块比较复杂，可以将其再细化成M21和M22两个子模块，分别对应一次方程和二方程的求根，其模块结构如图6-14所示。
图6-14 两个子模块结构
然后，按照细化M22模块的方法，分别对M1、M21和M3的算法进行结构组装，最终得到细化后完整的流程图，如图6-15所示。
图6-15 完整的流程图
2）编程实现
（1）在Visual C++6.0中，新建名称为6-8.c的Text File文件。
（2）在代码编辑区域输入以下代码。
（3）程序运行结果如图6-16所示。
图6-16 程序运行结果
6.7 就业面试技巧与解析
6.7.1 面试技巧与解析（一）
面试官：冒泡排序的概念是什么？
应聘者：依次比较相邻的2个数，将小数放在前面，大数放在后面。即在第1轮，首先比较第1个数和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后2个数，将小数放前，大数放后。至此第1轮结束，将最大的数放到了最后。在第2轮，仌从第1对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第2个数（倒数第1的位置上已经是最大的），第2轮结束后，在倒数第2的位置上得到一个新的最大数（其实在整个数列中是第2大的数）。如此下去，重复以上过程，直至最终完成排序。由于在排序过程中总是小数彽前放，大数彽后放，相当于气泡彽上升，所以称冒泡排序。
6.7.2 面试技巧与解析（二）
面试官：结构化程序设计方法有什么特点？
应聘者：自顶向下；逐步细化；模块化设计；结构化编码。
面试官：求1×2×3×4×5，用C语言表示（计算机语言表示法）。
应聘者：
