3.1 我们对算法的理解
知识点讲解：光盘：视频\PPT讲解（知识点）\第3章\我们对算法的理解.mp4
一个程序应包括对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构（data structure）。对操作的描述即操作步骤，也就是算法（algorithm）。Wirth曾经提出了一个经典的公式：数据结构+算法=程序。而根据谭浩强的总结得出：
程序=算法+数据结构+程序设计方法+语言工具和环境
3.1.1 为什么是程序灵魂
当我重新审视自己走过的路时，我越来越能理解算法的重要性。算法不仅是工具，而且是程序的灵魂。在初涉这一领域时，就多次看过Wirth教授的《算法+数据结构=程序》。后来思想慢慢转移到了方法论上，对OO、GP或者IoC这些知识超乎寻常地关心，却冷落了程序的本质。很多实际问题还是要靠精心设计的算法才能有效解决。
笔者曾发现一本比较有趣的书：由Udi Manber所写的 Introduction to Algorithms—A Creative Approach。此书的最大特点就是用数学归纳法贯穿全篇，我的理解就是“由一粒沙看世界”。复杂的问题，如何对其分解？在这本书中，不仅给出了一些具体算法，更重要的是要培养读者的设计算法的能力。而这种能力的核心，在作者看来，就是对归纳的理解和灵活运用。
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，数据会从输入设备读取，写入输出设备，可能保存起来以供以后使用。
著名计算机科学家Wirth提出一个公式：
数据结构+算法=程序
实际上，一个程序还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：
程序=算法+数据结构+程序设计方法+语言和环境
以上4个方面是一门程序设计语言所应具备的基本知识。在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具。算法是解决“做什么”和“怎么做”的问题。
程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。本书虽然不是专门讲算法的，但不会算法就达不到我们的目的——用C语言进行程序设计。
数据是操作对象，对操作的描述即是操作步骤，操作的目的是对数据进行加工处理得到期望的结果。打个比方，厨师做菜肴，需要有菜谱。菜谱上一般应包括：
（1）配料（数据）；
（2）操作步骤（算法）。
这样，面对同一些原料就可以加工出不同风味的菜肴。
3.1.2 何谓算法
做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。计算机能够执行的算法称为计算机算法。计算机算法可分为如下两大类。
❑ 数值运算算法：求解数值。
❑ 非数值运算算法：事务管理领域。
看下面的运算：
1×2×3×4×5
为了计算上述运算，通常需要按照如下步骤来计算。
第1步：先求1×2，得到结果2。
第2步：将步骤1得到的乘积2乘以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步：1→i。
第2步：如果chengi≥60，则打印ni和chengi，否则不打印。
第3步：i+1→i。
第4步：若i≤80，返回步骤2，否则，结束。
（2）判定1900～2000年中的那一年是闰年，将结果输出。
闰年需要满足的条件如下。
① 能被4整除，但不能被100整除的年份。
② 能被100整除，又能被400整除的年份。
在此可以设y为被检测的年份，则对应算法如下。
第1步：1900→y。
第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步继续执行，否则，结束。
3.1.3 算法的特性
对于程序设计人员来说，必须会设计算法，并根据算法写出程序。算法的特性如下所示。
❑ 有穷性，一个算法应包含有限的操作步骤而不能是无限的。
❑ 确定性，算法中每一个步骤应当是确定的，而不能是含糊的、模棱两可的。
❑ 有零个或多个输入。
❑ 有一个或多个输出。
❑ 有效性，算法中每一个步骤应当能有效地执行，并得到确定的结果。