使用算法和数据结构解决问题-1

说明：后来发现了已经有不少对这本书的翻译，例如北大课程，因此就不再继续翻译了。

第一章 前言

1.1 目标

1. 回顾计算机科学、编程和解决问题的想法。

2. 理解“抽象”及其在解决问题的过程中发挥的作用。

3. 理解和实现抽象数据类型的概念。

4. 复习 Python 编程语言。

1.2 开始

自从第一台通过贴片电缆和开关来传达人与机器之间指令的电子计算机问世以来，我们对编程的思考方式已经发生了许多变化。与社会的许多方面一样，计算机技术的变化为计算机科学家提供了越来越多的工具和平台来练习他们的技术，更快的处理器、高速网络和大型内存容量等进步也为计算机科学家带来必须面对的复杂性。在这飞速发展的过程中，仍然有一些基本原则保持不变。计算科学关注于使用计算机来解决问题。

无疑，你花了相当长的时间（真的吗？）学习解决问题的基础知识，并且对读懂问题并开发解决方案充满信心。你还了解到编程通常很难（并不），大规模问题的复杂性和求解方案的复杂性往往会掩盖与求解过程相关的基本思想。

本章强调了其余部分内容的两个重要方面。首先，它回顾了计算机科学以及算法和数据结构研究必须符合的框架，特别是我们需要研究这些主题的原因，以及理解这些主题如何帮助我们更好地解决问题。其次，我们复习一下Python编程语言。虽然我们无法提供详细、详尽的参考，但我们将为将在其余各章中出现的基本构造和想法提供实例和解释。

1.3 什么是计算科学

可能是由于名称中包含了”计算机“一词，计算科学通常很难定义。如你所知，计算科学并不仅仅是对计算机的研究。尽管计算机作为学科中的工具发挥了重要的支持作用，但它们仅仅是工具。

计算科学是对求解问题过程中的问题、求解过程以及解决方案的研究，针对给定问题，计算科学家的目标是设计算法——这是解决任何可能出现的问题的指令所对应的分布说明列表。算法帮助我们解决问题的有限过程，是解决方案。

我们可以认为计算科学就是研究算法，然而，我们必须注意，一些可能无解的问题也会被包含进来。虽然证明这种说法超出了本文的范围，但一些无解问题对于研究计算科学的人而言很重要。通过包含两种类型的问题，我们可以通过以下方式来定义计算科学：计算科学对问题解决方案的研究，以及对无解问题的研究。

”可计算“一词再描述问题和解决方案时也很常见。我们说，如果存在一个算法来解决问题，则该问题是可计算的。计算科学的另一种定义是：对可计算和不可计算的问题的研究、对算法存在性与不存在性的研究。在任何情况下，你都会注意到”计算机“一词没有出现，解决方案与机器是独立的。

因为它涉及到问题求解过程，所以计算科学也是抽象的研究。抽象使我们能够以分离逻辑和物理的方式来看代问题和解决方案。我们使用一个常见的例子来熟悉这一基本思想。

想象你今天可能开到学校或公司的汽车（我没车）。作为一个司机、汽车的用户，为了用车实现目的，你与汽车之间发生了一些交互，你进车、插钥匙、启动、换档、刹车、加速和转向以便驾驶。从抽象的角度来看，我们可以说你看到了汽车的逻辑视角。为了将你从一个地方送到另一个地方，你使用了汽车设计者所提供的函数，这些函数有时被称为接口。

另一方面，修理汽车的机械师则持有不同的观点。她不仅需要知道如何开车，还需要知道执行所有我们认为理所当然的函数的全部细节。她需要理解发动机的工作原理、变速箱如何换档、如何控制温度等等。这被称为物理视角——”引擎盖下的细节“。

在我们使用计算机时也发生了同样的事情。大多数人在不了解原理的情况下使用计算机来编写文档、发送和接收电子邮件、浏览网页、播放音乐、存储图像和玩游戏，他们从逻辑或者用户的视角来看计算机。而计算科学家、程序员、技术支持人员和系统管理员对计算机的看法则有很大不同，他们必须知道操作系统如何工作、如何配置网络协议以及如何编写控制功能的各种脚本，他们必须能够控制底层细节，而用户则只是简单想象这些。

这两个例子的共同点在于，抽象的用户（有时也被称为客户端）并不需要了解详细信息，而只需要知道接口的工作方式。接口是用户与底层复杂系统的通信方式。我们可以来看另一个抽象的例子：Python中的math模块。当我们导入该模块后，就可以实现如下计算：

>>> import math
>>> math.sqrt(16)
4.0
>>>

这是过程抽象(procedural abstraction)的示例。我们不一定知道平方根是如何计算的，但我们知道函数的调用以及如何使用它。如果我们正确执行导入，我们可以假定函数将为我们提供正确的结果。我们知道有人实现了平方根问题的解决方案，但我们并不关心是如何实现的，只需要知道如何使用它。这有时称为进程的”黑盒”视图。我们简单地将接口描述为：函数的名称、需要什么（参数）以及将返回什么，而具体内容则隐藏在接口中，如图1.1。

图1.1 过程抽象

1.3.1 什么是编程

编程是将算法编码为符号（编程语言）从而使其可以在计算机上执行的过程。尽管存在许多编程语言和许多不同类型的计算机，但重要的第一步是提出解决方案，没有算法就没有程序。

计算机科学不是编程的研究，然而编程是计算机科学家工作的一个重要部分。编程通常是我们为解决方案创建的表示。因此，这种语言表示和创建过程成为学科的基本部分。

算法根据表示问题实例所需的数据和产生预期结果所需的步骤集来描述问题的解决方案。编程语言必须提供一种符号方式来表示进程和数据。为此，语言提供了控件构造和数据类型。

控件构造允许以方便而明确的方式表示算法步骤。算法至少需要执行顺序处理、决策选择和重复控制迭代的构造（注：简单来说就是顺序、选择、循环）。只要编程语言提供这些基本语句，它就可以用于算法表示。

计算机中的所有数据项都表示为二进制数字字符串。为了给这些字符串赋予意义，我们需要有数据类型。数据类型为此二进制数据提供解释，以便我们可以从与所解决的问题有意义的术语中分析数据。这些低级的内置数据类型（有时称为基元数据类型）为算法开发提供了构建基块。

例如，大多数编程语言为整数提供了数据类型，计算机内存中的二进制数字字符串可以解释为整数，并给出我们通常与整数关联的典型含义（例如 23、654 和 -19）。此外，数据类型还提供数据项可以参与的操作的说明，对于整数，加法、减法和乘法等操作是通用的。我们期望该数字类型的数据可以参与这些算术运算。

我们经常遇到的困难是，问题及其解决方法非常复杂。这些简单的语言所提供的构造和数据类型虽然肯定足以表示复杂的解决方案，但往往会使我们再处理问题的过程中处于不利地位。我们需要控制这种复杂性和协助创建解决方案的方法。

1.3.2 为什么要学习数据结构和抽象数据类型

为了管理问题的复杂性和解决问题的过程，计算机科学家们使用抽象，使他们能够专注于”大局”，而不会迷失在细节中。通过创建问题域的模型，我们能够利用更好、更高效的问题求解过程。这些模型允许我们以与问题本身更加一致的方式来描述我们的算法将处理的数据。

在前文中，我们提到过程抽象是一个隐藏特定函数的详细信息的过程，以允许用户或客户端在非常高的级别上查看它。现在，我们把注意力转向一个类似的想法，即数据抽象。抽象数据类型（有时称为ADT）是对我们如何查看数据及其允许操作的逻辑描述，我们并不关心如何实现该数据类型。这意味着我们只关心数据所代表的是什么，而不关心数据是如何构造的。通过提供这种抽象级别，我们围绕数据创建封装，其理念是，在用户视图中，通过封装将实现过程的详细信息隐藏起来，这被称为信息隐藏。

图 1.2 显示了抽象数据类型及其操作方式的图片。用户使用抽象数据类型指定的操作与接互。抽象数据类型是用户与之交互的 shell。实现过程被隐藏在更深的一层，而用户并不关心实现过程的详细信息。

图1.2 抽象数据类型

抽象数据类型的实现（通常称为数据结构）要求我们使用一些编程构造和基元数据类型的集合提供数据的物理视图。正如我们前面所讨论的，这两个视图的分离将使我们能够在无需说明模型实际构建的细节的情况下，定义我们问题的复杂数据模型，它提供了实现独立性的数据视图。由于实现抽象数据类型通常有很多不同的方法，因此这种实现独立性允许程序员切换实现过程的详细信息，而无需更改数据用户与其交互的方式，用户可以继续专注于解决问题的过程。

1.3.3 为什么要学习算法

计算机科学家通过经验学习，通过看到别人解决问题和自己解决问题来学习。接触不同的问题解决技术，并了解不同的算法是如何设计的，这有助于我们面对下一个具有挑战性的问题。通过思考许多不同的算法，我们可以开始开发模式识别，以便下次出现类似的问题时，可以更好地解决它。

算法通常彼此大不相同，例如前文中的sqrt示例，完全有可能有许多不同的方法来具体实现计算平方根的函数。某种算法使用的资源可能比另一种算法少很多，而某种算法可能需要10倍的时间才能返回结果。我们希望有一些办法来比较这两种解决方案，即使它们都是有效方案，一种也许会比另一种更好。我们可能会认为一种方法更高效，或者运行得更快或使用更少的内存。当我们研究算法时，我们可以学习分析技术，这些分析技术使我们能够仅根据解决方案自身的特点进行比较和对比，而不是基于用于实现它们的程序或计算机的特性。

在最坏的情况下，我们可能有一个难以解决的棘手问题，这意味着没有算法可以在实际的时间内解决问题。能够区分那些有解决办法的问题、没有解决办法的问题和存在解决方案但需要太多时间或其他资源才能合理工作的问题是很重要的。

我们往往需要确定和决定解决方案之间的权衡，作为计算机科学家，除了解决问题的能力外，我们还需要了解和理解解决方案的评估技术。最后，往往有很多方法可以解决问题。找到一个解决方案，然后决定它是否是好的，是我们将不断重复完成的任务。

1.4 基础Python复习

在本节中，我们将回顾编程语言 Python，并提供上一节中想法的一些更详细的示例。如果你是 Python 的初学者，或者发现需要有关任何内容的更多信息，我们建议你参考诸如Python Language Reference或Python Tutorial这样的资源。在这里我们的目标是重新认识Python语言，并加强一些后几章中的核心概念。

Python 是一种现代、易于学习、面向对象的编程语言。它有一组强大的内置数据类型和易于使用的控件构造。由于 Python 是一种解释性语言，因此只需查看和描述交互式会话，就可以了解它。你应该记得，解释器在提示>>>时显示操作，然后评估您提供的 Python 构造。例如下面这段代码展示了提示、打印功能、结果和下一个提示。

>>> print("Algorithms and Data Structures")
Algorithms and Data Structures
>>>

1.4.1 从数据开始