1.3　C语言程序与算法

1.3.1　程序与算法的概念

1.程序

计算机帮助人类处理数据和文件的能力并不是天生的，而是人类赋予它们的，人类要想指挥计算机就要和计算机交流，交流的工具就是计算机程序。计算机程序（Program）是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合，是用汇编语言、高级语言等开发编制出来的可以运行的文件，在计算机中称为可执行文件（扩展名一般为.exe）。如果没有程序，计算机什么也不会做。

2.算法和算法的基本性质

算法，广义地说是为解决一个问题而采取的方法和步骤。例如，要把篮球投进篮框里，首先要拿起篮球，然后按照一定角度和力度把球投出去；喷气式飞机要飞上天，首先要在跑道上加速，当速度足够高时，才能够飞起来；三三刷牙法，也可以称为一种算法，因为它指定了刷牙的步骤和方法。对于同一个问题，可以有不同的解决方法和步骤，也就产生了不同的算法。比如说投篮，可以用一只手，也可以用两只手；可以先跳起来再投，也可以不跳直接投。

对于计算机程序应包含的内容，1976年，瑞士著名计算机科学家沃思（Nikiklaus Wirth）提出过一个著名公式：

程序=数据结构+算法

他认为，程序就是在数据的某些特定表示方法和结构基础上对抽象算法的具体表述。一个程序应包括以下两部分内容：

（1）对数据的描述，在程序中要指定数据的类型和数据的组织形式，即数据结构。

（2）对操作的描述，即操作步骤，也就是算法。

根据算法，依据某种规则编写计算机可以执行的命令序列就是编制程序，而编写程序时所应遵守的规则就是某种语言的语法。

由此可见，程序设计的关键之一是解题的步骤，即算法。学习高级语言的重点，就是要掌握分析问题、解决问题的方法，锻炼分析、分解、最终归纳整理出算法的能力。与之相对应，具体语言（如C语言）是算法的一种具体实现工具。所以高级语言的学习中，一方面应熟练掌握该语言的语法，因为它是算法实现的基础；另一方面必须认识到算法的重要性，加强思维训练，以写出高质量的程序。

计算机算法可分为两大类：①数值运算算法，用于求解数值；②非数值运算算法，用于事务管理领域。

算法具有以下特性：

（1）有穷性。一个算法应包含有限的操作步骤，每一步必须在允许的时间内完成。如果—个算法完成的时间过长，就失去了有穷性。

（2）确定性。算法中的每一个步骤应当是确定的，而不能是含糊的、模棱两可的。例如，“如果x大于或等于0，输出YES；x小于或等于0，输出NO”在执行时就会出现歧义，若x=0时，既要输出NO又要输出YES，不符合确定性要求。

（3）有零个或多个输入。有些算法不需要从外界输入数据就可以执行，如计算11+22+33+…+1010；而有些算法则需要输入数据，如计算11+22+33+…+nn，n的数值未知，因此需要从键盘上输入数据。

（4）有一个或多个输出。算法的实现是以得到计算结果为目的的，没有任何输出的算法是没有意义的。

（5）有效性。算法中的每一个步骤应当能有效地执行，并得到确定的结果。

程序设计人员必须会设计算法，并能根据算法写出程序。

3.算法的表示形式

算法可以使用多种工具描述，常用的有自然语言、流程图、N-S图、伪代码等。

1）用自然语言表示算法

算法可以用自然语言描述。自然语言就是人们日常使用的语言，可以是汉语、英语或其他语言。用自然语言表示的算法通俗易懂，但文字冗长，容易出现歧义。自然语言的含义往往不太严格，要根据上下文才能准确判断其含义。此外，用自然语言描述分支和循环的算法，不是很直观。因此，除了简单问题，一般不采用自然语言描述算法。

【例1-2】输入一个年份，判定其是否为闰年。

说明：能被4整除但不能被100整除的年份，或者能被400整除的年份是闰年。

算法描述如下。

S1：输入一个年份y；

S2：若y不能被4整除，则输出“y不是闰年”；

S3：若y能被4整除，但不能被100整除，则输出“y是闰年”；

S4：若y能被400整除，则输出“y是闰年”；否则输出“y不是闰年”。

2）用流程图表示算法

流程图表示算法：用一些图框表示各种操作，用箭头表示算法流程。用图形表示算法直观形象，易于理解。

美国国家标准学会（ANSI）规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用，具体如表1-1所示。

（1）起止框：表示算法的开始和结束，一般内部只写“开始”或“结束”。

（2）处理框：表示算法的某个处理步骤，一般内部常常填写赋值操作。

（3）输入/输出框：表示算法请求输入需要的数据或算法将某些结果输出。一般内部常常填写“输入……”或“打印/显示……”。

（4）判断框：对一个给定条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。它有1个入口和2个出口。

流程图是表示算法较好的工具，包括以下几个部分：表示相应操作的框，带箭头的流程线，框内、框外必要的文字说明。

注意：流程线一定需要箭头来指明方向，因其反映流程的先后次序。

传统流程图采用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无规律。

人们对这种流程图进行改进，规定几种基本的结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构由上而下地将各个基本结构顺序排列起来。这样可以在一定程度上提高算法的质量。

1966年，Bohra和Jacopini提出了3种基本结构，即顺序结构、选择结构和循环结构。

（1）顺序结构：顺序结构是一种最简单、最基本的结构，在这种结构中，各程序块按照出现的顺序依次执行。如图1-4所示，表示A框执行完后立即执行B框，它只有一个入口a和一个出口b。

（2）选择结构：选择结构也称为分支结构，是根据给定的条件判断在两条可能的路径中选择哪一条。如图1-5所示，条件P为真时执行A框处理，为假时执行B框处理。当然，A、B框可为空，但不能同时为空，并且，它只有一个入口a和一个出口b。在执行时，只可能执行A框或者执行B框，不可能既执行A框又执行B框，但是无论走哪一条路径，都在b口结束。

（3）循环结构：循环结构也称为重复处理结构，包括当型循环结构和直到型循环结构。当型循环结构是在满足给定条件时反复执行某一程序块A，否则不执行。如图l-6（a）所示，先判断条件P，当P为真时执行A框，A框处理完后再判断条件P，当P为真时再执行A框，如此循环往复，直到判断条件P为假时为止。直到型循环结构是先执行程序块A，直到满足给定条件时不再执行。如图l-6（b）所示，先执行A框，A框处理完后再判断条件P，当P为假时再执行A框，如此循环往复，直到判断条件P为真时为止。从图1-6中可以看出，循环结构也只有一个入口a和一个出口b。

在这3种基本结构中，有以下4个共同特征：

·只有一个入口。

·只有一个出口。

·结构中的每一个部分都有机会被执行到。

·结构内不存在“死循环”。

【例1-3】把例1-2用流程图表示，如图1-7所示。

3）用N-S图表示算法

既然基本结构的顺序组合可以表示任何复杂的算法结构，那么，基本结构之间的流程线就属于多余的。美国学者I.Nassi和B.Shneiderman提出了一种新的流程图——N-S图，也称盒图。在N-S图中，取消了带箭头的流程线。每种结构用一个矩形框表示。N-S图的符号比较简单，如图1-8所示。

（1）顺序结构：如图1-8（a）所示，表示A框执行完后立即执行B框。

（2）选择结构：如图l-8（b）所示，表示条件P为真时执行A框处理，为假时执行B框处理，即给出两出口分支结构，A、B框可为空，但不能同时为空。

（3）循环结构：循环结构有两种图形符号。当型循环结构的图形符号如图l-8（c）所示，表示先判断条件P，当P为真时执行A框，A框处理完后再判断条件P，当P为真时再执行A框，如此循环往复，直到判断条件P为假时为止。直到型循环结构的图形符号如图l-8（d）所示，表示先执行A框，A框处理完后再判断条件P，当P为假时再执行A框，如此循环往复，直到判断条件P为真时为止。

N-S图中的矩形框A和B为处理框，框中给出处理说明，可以是文字描述、一组操作、一个子例行程序名、一个模块名或其他N-S图图形符号。框间的水平隔线表示上、下两框间的入、出口关系，没有其他入口、出口途径。图形符号可以相互嵌套，用于描述比较复杂的算法。

用N-S图描述的算法一定是结构化的，不会出现非结构化的现象，所以用N-S图描述算法特别适用于结构化的算法描述。

4）用伪代码表示算法（常用于算法设计）

【例1-4】将例1-2用N-S图表示，如图1-9所示。

用传统流程图、N-S图表示算法，直观易懂，但绘制比较麻烦。在设计一个算法时，可能要反复修改，而修改流程图也是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码。

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡。

【例1-5】把例1-2用伪代码表示。