清华大学出版社 TSINGHUA UNIVERSITY PRESS 第2章 程序的灵魂— 算法 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5结构化程序设计方法 习题
2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 习题 第2章 程序的灵魂——算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 一个程序应包括以下两方面内容： (1)对数据的描述。在程序中要指定数据的类型和数 据的组织形式，即数据结构(data structure)。 (2)对操作的描述。即操作步骤，也就是算法 (algorithm)。 数据是操作的对象，操作的目的是对数据进行加工 处理，以得到期望的结果。作为程序设计人员， 必须认真考虑和设计数据结构和操作步骤（即算法）。 因此，著名计算机科学家沃思Nikiklaus Wirth)提 出一个公式 数据结构+算法=程序
一个程序应包括以下两方面内容: (1) 对数据的描述。在程序中要指定数据的类型和数 据的组织形式，即数据结构(data structure)。 (2) 对操作的描述。即操作步骤， 也就是算法 (algorithm)。 数据是操作的对象，操作的目的是对数据进行加工 处理，以得到期望的结果。作为程序设计人员， 必须认真考虑和设计数据结构和操作步骤(即算法)。 因此，著名计算机科学家沃思(Nikiklaus Wirth)提 出一个公式 数据结构 + 算法 = 程序
清华大学出版社 TSINGHUA UNIVERSITY PRESS 实际上，一个程序除了以上两个主要要素之外，还 应当采用结构化程序设计方法进行程序设计，并 且用某一种计算机语言表示。因此，可以这样表 示： 程序=算法+数据结构+程序设计方法+语言工具 和环境 也就是说，以上4个方面是一个程序设计人员所应具 备的知识。在设计一个程序时要综合运用这几方 面的知识。在这4个方面中，算法是灵魂，数据结 构是加工对象，语言是工具，编程需要采用合适 的方法。算法是解决“做什么”和“怎么做”的 问题。程序中的操作语句，实际上就是算法的体 现。显然，不了解算法就谈不上程序设计
实际上，一个程序除了以上两个主要要素之外，还 应当采用结构化程序设计方法进行程序设计，并 且用某一种计算机语言表示。因此，可以这样表 示： 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具 和环境 也就是说，以上4个方面是一个程序设计人员所应具 备的知识。在设计一个程序时要综合运用这几方 面的知识。在这4个方面中，算法是灵魂，数据结 构是加工对象，语言是工具，编程需要采用合适 的方法。算法是解决“做什么”和“怎么做”的 问题。程序中的操作语句，实际上就是算法的体 现。显然，不了解算法就谈不上程序设计
清华大学出版社 TSINGHUA UNIVERSITY PRESS 我们的目的是使读者通过学习本书，能够知道怎样 编写一个C程序，并且能够编写出不太复杂的C程 序。书中将通过一些实例把以上4个方面的知识结 合起来，介绍如何编写一个C程序。 由于算法的重要性，在本章中先介绍有关算法的初 步知识，以便为后面各章的学习建立一定的基础
我们的目的是使读者通过学习本书，能够知道怎样 编写一个C程序，并且能够编写出不太复杂的C程 序。书中将通过一些实例把以上4个方面的知识结 合起来，介绍如何编写一个C程序。 由于算法的重要性，在本章中先介绍有关算法的初 步知识，以便为后面各章的学习建立一定的基础
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1算法的概念 从事各种工作和活动，都必须事先想好进行的步骤， 然后按部就班地进行，才能避免产生错乱。 不要认为只有“计算”的问题才有算法。广义地说， 为解决一个问题而采取的方法和步骤，就称为 “算法”。 对同一个问题，可以有不同的解题方法和步骤。方 法有优劣之分。有的方法只需进行很少的步骤， 而有些方法则需要较多的步骤。一般说，希望采 用简单的和运算步骤少的方法。因此，为了有效 地进行解题，不仅需要保证算法正确，还要考虑 算法的质量，选择合适的算法
2.1 算 法 的 概 念 从事各种工作和活动，都必须事先想好进行的步骤， 然后按部就班地进行，才能避免产生错乱。 不要认为只有“计算”的问题才有算法。广义地说， 为解决一个问题而采取的方法和步骤，就称为 “算法”。 对同一个问题，可以有不同的解题方法和步骤。方 法有优劣之分。有的方法只需进行很少的步骤， 而有些方法则需要较多的步骤。一般说，希望采 用简单的和运算步骤少的方法。因此 ，为了有效 地进行解题，不仅需要保证算法正确，还要考虑 算法的质量，选择合适的算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 本书所关心的当然只限于计算机算法，即计算机能 执行的算法。 计算机算法可分为两大类别：数值算法和非数值算 法。数值运算的目的是求数值解。非数值运算包 括的面十分广泛，最常见的是用于事务管理领域。 目前，计算机在非数值运算方面的应用远远超过 了在数值运算方面的应用。由于数值运算有现成 的模型，可以运用数值分析方法，因此对数值运 算的算法研究比较深入，算法比较成熟。对各种 数值运算都有比较成熟的算法可供选用。人们常 常把这些算法汇编成册（写成程序形式），或者将这 些程序存放在磁盘或磁带上，供用户调用
本书所关心的当然只限于计算机算法，即计算机能 执行的算法。 计算机算法可分为两大类别：数值算法和非数值算 法。数值运算的目的是求数值解 。非数值运算包 括的面十分广泛，最常见的是用于事务管理领域。 目前，计算机在非数值运算方面的应用远远超过 了在数值运算方面的应用。由于数值运算有现成 的模型，可以运用数值分析方法，因此对数值运 算的算法研究比较深入，算法比较成熟。对各种 数值运算都有比较成熟的算法可供选用。人们常 常把这些算法汇编成册(写成程序形式)，或者将这 些程序存放在磁盘或磁带上，供用户调用
清华大学出版社 TSINGHUA UNIVERSITY PRESS 而非数值运算的种类繁多，要求各异，难以规范化， 因此只对一些典型的非数值运算算法（例如排序算 法)作比较深入的研究。其他的非数值运算问题， 往往需要使用者参考已有的类似算法重新设计解 决特定问题的专门算法。 本书不可能罗列所有算法，只是想通过一些典型算 法的介绍，帮助读者了解如何设计一个算法，推 动读者举一反三。希望读者通过本章介绍的例子 了解怎样提出问题，怎样思考问题，怎样表示一 个算法
而非数值运算的种类繁多，要求各异，难以规范化， 因此只对一些典型的非数值运算算法(例如排序算 法)作比较深入的研究。其他的非数值运算问题， 往往需要使用者参考已有的类似算法重新设计解 决特定问题的专门算法。 本书不可能罗列所有算法，只是想通过一些典型算 法的介绍，帮助读者了解如何设计一个算法，推 动读者举一反三。希望读者通过本章介绍的例子 了解怎样提出问题，怎样思考问题，怎样表示一 个算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.2简单算法举例 例2.1求1×2×3×4×5。 可以用最原始的方法进行。 步骤1：先求1×2，得到结果2。 步骤2：将步骤1得到的乘积2再乘以3，得到结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。这就是最后的结果。 这样的算法虽然是正确的，但太繁琐。如果要求 1×2×.×1000,则要写999个步骤，显然是不可 取的。而且每次都直接使用上一步骤的数值结果 (如2,6,24等)，也不方便。应当找到一种通用的 表示方法
2.2 简单算法举例 例2.1 求1×2×3×4×5。 可以用最原始的方法进行。 步骤1： 先求1×2，得到结果2。 步骤2： 将步骤1得到的乘积2再乘以3，得到结果6。 步骤3： 将6再乘以4，得24。 步骤4： 将24再乘以5，得120。这就是最后的结果。 这样的算法虽然是正确的，但太繁琐。如果要求 1×2×.×1000，则要写999个步骤，显然是不可 取的。而且每次都直接使用上一步骤的数值结果 (如2，6，24等)，也不方便。应当找到一种通用的 表示方法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 可以设两个变量，一个变量代表被乘数，一个变量 代表乘数。不另设变量存放乘积结果，而直接将 每一步骤的乘积放在被乘数变量中。今设p为被乘 数，为乘数。用循环算法来求结果。可以将算法 改写如下： S1: 使p=1 S2: 使i=2 S3: 使pXi, 乘积仍放在变量p中，可表示为 pXi=>p S4: 使的值加1，即i计1=>i S5:如果不大于5，返回重新执行步骤S3以及其后 的步骤S4和S5;否则，算法结束。最后得到p的值 就是5！的值
可以设两个变量，一个变量代表被乘数，一个变量 代表乘数。不另设变量存放乘积结果，而直接将 每一步骤的乘积放在被乘数变量中。今设p为被乘 数，i为乘数。用循环算法来求结果。可以将算法 改写如下： S1： 使p=1 S2： 使i=2 S3： 使p×i，乘积仍放在变量p中，可表示为 p×i=>p S4： 使i的值加1，即i+1 => i S5： 如果i不大于5，返回重新执行步骤S3以及其后 的步骤S4和S5；否则，算法结束。最后得到p的值 就是5!的值
清华大学出版社 TSINGHUA UNIVERSITY PRESS 上面的S1,S2.代表步骤1，步骤2.S是step(步) 的缩写。这是写算法的习惯用法。 请读者仔细分析这个算法，能否得到预期的结果。 显然这个算法比前面列出的算法简练。 如果题目改为求1×3×5×7×9×11。 算法只需作很少的改动即可： S1:1=>p S2:3=>i S3: pXi=>p S4: i+2=>i S5: 若i≤11，返回S3;否则，结束
上面的S1，S2.代表步骤1，步骤2.S是step(步) 的缩写。这是写算法的习惯用法。 请读者仔细分析这个算法，能否得到预期的结果。 显然这个算法比前面列出的算法简练。 如果题目改为求1×3×5×7×9×11。 算法只需作很少的改动即可： S1： 1=>p S2： 3=>i S3： p×i=>p S4： i+2=>i S5： 若i≤11，返回S3； 否则，结束