1.2.2 计算思维的具体例子

### 1.2.2 计算思维的具体例子 基于计算机的能力和局限，计算机科学家提出了很多关于计算的思想和方法，从而建立 了利用计算机解决问题的一整套思维工具。下面我们简要介绍计算机科学家在计算的不同阶 段所采用的常见思想和方法。 问题表示 用计算机解决问题，首先要建立问题的计算机表示。问题表示与问题求解是紧密相关的， 如果问题的表示合适，那么问题的解法就可能如水到渠成一般容易得到，否则可能如逆水行 舟一般难以得到解法。 抽象（abstraction）是用于问题表示的重要思维工具。例如，小学生经过学习都知道将 应用题“原来有五个苹果，吃掉两个后还剩几个”抽象表示成“5 - 2”，这里显然只抽取了 问题中的数量特性，完全忽略了苹果的颜色或吃法等不相关特性。一般意义上的抽象，就是 指这种忽略研究对象的具体的或无关的特性，而抽取其一般的或相关的特性。计算机科学中 的抽象包括数据抽象和控制抽象，简言之就是将现实世界中的各种数量关系、空间关系、逻 辑关系和处理过程等表示成计算机世界中的数据结构（数值、字符串、列表、堆栈、树等） 和控制结构（基本指令、顺序执行、分支、循环、模块等），或者说建立实际问题的计算模型。 另外，抽象还用于在不改变意义的前提下隐去或减少过多的具体细节，以便每次只关注少数 几个特性，从而有利于理解和处理复杂系统。显然，通过抽象还能发现一些看似不同的问题 的共性，从而建立相同的计算模型。总之，抽象是计算机科学中广泛使用的思维方式，只要 有可能并且合适，程序员就应当使用抽象。 可以在不同层次上对数据和控制进行抽象，不同抽象级对问题进行不同颗粒度或详细程 度的描述。我们经常在较低抽象级之上再建立一个较高的抽象级，以便隐藏低抽象级的复杂 细节，提供更简单的求解方法。例如，对计算本身的理解就可以形成“电子电路®门逻辑® 二进制®机器语言指令®高级语言程序”这样一个由低到高的抽象层次，我们之所以在高级 语言程序这个层次上学习计算，当然是为了隐藏那些低抽象级的繁琐细节。又如，在互联网 上发送一封电子邮件实际上要经过不同抽象级的多层网络协议才得以实现，写邮件的人肯定 不希望先掌握网络低层知识才能发送邮件。再如，我们经常在现有软件系统之上搭建新的软 件层，目的是隐藏低层系统的观点或功能，提供更便于理解或使用的新观点或新功能。 算法设计 问题得到表示之后，接下来的关键是找到问题的解法——算法。算法设计是计算思维大 显身手的领域，计算机科学家采用多种思维方式和方法来发现有效的算法。例如，利用分治 法的思想找到了高效的排序算法，利用递归思想轻松地解决了 Hanoi 塔问题，利用贪心法寻 求复杂路网中的最短路径，利用动态规划方法构造决策树，等等。前面说过，计算机在各个 领域中的成功应用，都有赖于高效算法的发现。而为了找到高效算法，又依赖于各种算法设 计方法的巧妙运用。 对于大型问题和复杂系统，很难得到直接的解法，这时计算机科学家会设法将原问题重 新表述，降低问题难度，常用的方法包括分解、化简、转换、嵌入、模拟等。如果一个问题 过于复杂难以得到精确解法，或者根本就不存在精确解法，计算机科学家不介意退而求其次， 寻求能得到近似解的解法，通过牺牲精确性来换取有效性和可行性，尽管这样做的结果可能 导致问题解是不完全的，或者结果中混有错误。例如搜索引擎，它们一方面不可能搜出与用 户搜索关键词相关的所有网页，另一方面还可能搜出与用户搜索关键词不相关的网页。作为 对比，很难想象数学家在解决数学问题时会寻求什么近似证明或对错参杂的解。 编程技术 找到了解决问题的算法，接下来就要用编程语言来实现算法，这个领域同样是各种思想 和方法的宝库。例如类型化与类型检查方法将待处理的数据划分为不同的数据类型，编译器 或解释器借此可以发现很多编程错误，这和自然科学中的量纲分析的思想是一致的。又如结 构化编程方法使用规范的控制流程来组织程序的处理步骤，形成层次清晰、边界分明的结构 化构造，每个构造具有单一的入口和出口，从而使程序易于理解、排错、维护和验证正确性。 又如模块化编程方法采取从全局到局部的自顶向下设计方法，将复杂程序分解成许多较小的 模块，解决了所有底层模块后，将模块组装起来即构成最终程序。又如面向对象编程方法以 数据和操作融为一体的对象为基本单位来描述复杂系统，通过对象之间的相互协作和交互实 现系统的功能。还有，程序设计不能只关注程序的正确性和执行效率，还要考虑良好的编码 风格（包括变量命名、注释、代码缩进等提高程序易读性的要素）和程序美学问题。 编程范型（programming paradigm）是指计算机编程的总体风格，不同范型对编程要素（如数据、语句、函数等）有不同的概念，计算的流程控制也是不同的。早期的命令式（或 称过程式）语言催生了过程式（procedural）范型，即一步一步地描述解决问题的过程。后来 发明了面向对象语言，数据和操作数据的方法融为一体（对象），对象间进行交互而实现系统 功能，这就形成了面向对象（object-oriented）范型。逻辑式语言、函数式语言的发明催生了 声明式（declarative）范型——只告诉计算机“做什么”，而不告诉计算机“怎么做”。有的语 言只支持一种特定范型，有的语言则支持多种范型。本书采用的 Python 就是支持多种编程范 型的语言，Python 程序可以是纯过程式的，也可以是面向对象的，甚至可以是函数式的。 可计算性与算法复杂性 在用计算机解决问题时，不仅要找出正确的解法，还要考虑解法的复杂度。这和数学思维不同，因为数学家可以满足于找到正确的解法，决不会因为该解法过于复杂而抛弃不用。 但对计算机来说，如果一个解法太复杂，导致计算机要耗费几年几十年乃至更久才能算出结 果，那么这种“解法”只能抛弃，问题等于没有解决。有时即使一个问题已经有了可行的算 法，计算机科学家仍然会去寻求更有效的算法。 有些问题是可解的但算法复杂度太高，而另一些问题则根本不可解，不存在任何算法过 程。计算机科学的根本任务可以说是从本质上研究问题的可计算性。例如，科幻电影里的计 算机似乎都像人类一样拥有智能，从计算的本质来说，这意味着人类智能能够用算法过程描 述出来。虽然现代计算机已经能够从事定理证明、自主学习、自动推理等“智能”活动，但 是人类做这些事情并非采用一步一步的算法过程，像阿基米德大叫“尤里卡”那样的智能活 动至少目前的计算机是没有可能做到的。 虽然很多问题对于计算机来说难度太高甚至是不可能的任务，但计算思维具有灵活、变 通、实用的特点，对这样的问题可以去寻求不那么严格但现实可行的实用解法。例如，计算 机所做的一切都是由确定性的程序决定的，以同样的输入执行程序必然得到同样的结果，因 此不可能实现真正的“随机性”。但这并不妨碍我们利用确定性的“伪随机数”生成函数来模 拟现实世界的不确定性、随机性。 又如，当计算机有限的内存无法容纳复杂问题中的海量数据时，这个问题是否就不可解 了呢？当然不是，计算机科学家设计出了缓冲方法来分批处理数据。当许多用户共享并竞争 某些系统资源时，计算机科学家又利用同步、并发控制等技术来避免竞态和僵局。