算法——抓住程序的灵魂

做任何事情都要有一定的步骤，为了解决一个问题而采取的方法和步骤就称为算法。C语言的算法是计算机算法，即计算机能够执行的算法。只有明确了算法后，才能使应用程序实现某些功能。所以，通常人们会将算法称为程序的灵魂。本文将详细介绍C语言算法的基础知识。

我们对算法的理解

一个程序应包括对数据的描述。在程序中要指定数据的类型和数据的组织形式（即数据结构，对操作的描述（即操作步骤），也就是算法（algorithm）。Wirth曾经提出了一个经典的公式：数据结构+算法=程序。而谭浩强的总结为：程序=算法+数据结构+程序设计方法+语言和环境

1.1　算法是程序的灵魂

当重新审视自己走过的路时，我越来越能理解算法的重要性。算法不仅是工具，而且还是程序的灵魂。在初涉这一领域时，就多次看过Wirth教授的《算法+数据结构=程序》一书。后来思想慢慢转移到了方法论上，对OO、GP或者IoC这些知识超乎寻常地关心，却冷落了程序的本质。很多实际问题还是要靠精心设计的算法才能有效解决。

作者曾发现一本比较有趣的书，它是由Udi Manber所写的Introduction to Algorithms——A Creative Approach。此书的最大特点就是数学归纳法贯穿全文，我的理解就是“由一粒沙看世界”。复杂的问题，应如何对其分解？在这本书中，不仅给出了一些具体算法，更重要的是它要培养读者设计算法的能力。而这种能力的核心，在作者看来，就是对归纳的理解和灵活运用。

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法，所以应告诉计算机确切的步骤以执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般，当算法在处理信息时，数据会从输入设备上读取，写入至输出设备，保存起来供以后使用。

著名计算机科学家Wirth提出一个公式。

数据结构+算法=程序

实际上，一个程序还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，它可以这样表示。

程序=算法+数据结构+程序设计方法+语言和环境

以上4个方面是一门程序设计语言所应具备的基本知识。其中，算法是灵魂，数据结构是加工对象，语言是工具。算法解决“做什么”和“怎么做”的问题。

程序中的操作语句实际上就是算法的体现。显然，不了解算法就谈不上程序设计。本书虽然不是专门讲解算法的，但不会算法就达不到我们的目的——用C语言进行程序设计。

数据是操作对象，操作的描述即是操作步骤，操作目的是对数据进行加工处理以得到期望的结果。打个比方，厨师做菜肴，需要有菜谱。菜谱上一般应包括配料（数据）与操作步骤（算法）。

这样，对于同一些原料就可以加工出不同风味的菜肴。

1.2　何谓算法

做任何事情都要有一定的步骤。为解决一个问题而采取的方法和步骤称为算法。计算机能够执行的算法称为计算机算法。计算机算法可分为如下两大类。

• 数值运算算法：求解数值。

• 非数值运算算法：事务管理领域。

看下面的运算。

1×2×3×4×5

为了计算上述运算，通常需要按照如下步骤来操作。

第1步：求1×2，得到结果2。

第2步：将第1步得到的乘积乘以3，得到结果6。

第3步：将6再乘以4，得24。

第4步：将24再乘以5，得120。

上述过程就是一个算法，虽然过程有点复杂。而计算机程序对上述算法进行了改进，它使用如下算法。

第1步：令t=1。

第2步：令i=2。

第3步：计算t×i，乘积仍然放在变量t中，可表示为t×i→t。

第4步：会i的值+1，即i+1→i。

第5步：如果i≤5，则返回重新执行步骤3以及步骤4和步骤5；否则，算法结束。

上述算法就是数学中的“n!”公式。

看下面的数学应用题。

（1）有80个学生，要求将他们中成绩在60分以上的姓名和成绩打印出来。

在此设n表示学生的学号，ni表示第i个学生的学号；cheng表示学生成绩，chengi表示第i个学生成绩。则对应算法表示如下。

第1步：令i=1。

第2步：如果chengi≥60，则输出ni和chengi；否则不输出。

第3步：i+1→i。

第4步：若i≤80，则返回步骤2；否则，结束。

（2）判定在1900～2000年中哪一年是闰年，并输出结果。

闰年需要满足的条件如下所示。

• 能被4整除，但不能被100整除的年份。

• 能被100整除，又能被400整除的年份。

在此可以设y为被检测的年份，则对应算法如下所示。

第1步：令y=1900。

第2步：若y不能被4整除，则输出y“不是闰年”，然后转到第6步。

第3步：若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到第6步。

第4步：若y能被100整除，又能被400整除，则输出y“是闰年”；否则，输出y“不是闰年”，然后转到第6步。

第5步：输出y“不是闰年”。

第6步：y+1→y。

第7步：当y≤2000时，返回第2步继续执行；否则，结束。

19.1.3　算法的特性

对于程序设计人员来说，必须会设计算法，并根据算法写出程序。算法的特性如下所示。

• 有穷性，一个算法应包含有限的操作步骤而不能是无限的。

• 确定性，在算法中每一个步骤都应当是确定的，而不能是含糊的、模棱两可的。

• 有零个或多个输入。

• 有一个或多个输出。

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

1.2　算法表示法——流程图

算法的表示方法为算法的描述和外在表现，上节的算法都是通过语言描述来体现的。除了语言描述外，还可以通过流程图来描述。在日常应用中，流程图的描述格式如图19-1所示。

图1-1　流程图标识说明

例如，有80个学生，要求将他们之中成绩在60分以上的姓名和成绩打印出来。上述问题的算法可使用图19-2所示的流程图来表示。

图1-2　算法流程图

在日常流程设计中，流程图通常包含如下3种结构。

• 顺序结构：顺序结构如图19-3所示，其中A和B两个框是顺序执行的。即在执行完A的操作以后再执行B的操作。顺序结构是一种基本结构。

图1-3　顺序结构

• 选择结构：选择结构也称为分支结构，如图19-4所示。在此结构中必含一个判断框，根据给定条件是否成立而选择是执行 A框还是B框。无论条件是否成立，都只能执行A框或B框之一，也就是说A、B两个框只有一个，也必须有一个被执行。

图1-4　选择结构

• 循环结构：循环结构分为两种，一种是当型循环，另一种是直到型循环。当型循环是先判断条件P是否成立，若成立才执行A操作，而直到型循环则相反，先执行A操作再判断条件P是否成，当条件不满足时执行循环体，满足时则停止，如图19-5所示。

图1-5　循环结构

在上述3种基本结构中，有以下4个共同点。

• 只有一个入口。

• 只有一个出口。

• 结构内的每个部分都有机会执行。

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