乍看之下，计算机科学领域的许多任务实际上是新的或独特的，实际上植根于经典算法，编码方法和开发原理。 而成熟的技术仍然是解决此类问题的最佳方法！
这本书将为您提供深入学习Python语言，通过久经考验的任务，练习和算法进行自我测试的机会。 您必须解决许多编程任务：从最简单的任务（例如，使用二进制排序查找列表项）到复杂的任务（使用k-means方法聚类数据）。 通过致力于搜索，聚类，图等的示例，您将记住自己忘记的内容，并掌握解决日常问题的经典技术。
这本书是给谁的？
本书适用于中高级程序员。 想要加深对Python的了解的经验丰富的专业人员会在这里找到从教授计算机科学或编程时就熟悉的任务。 中级程序员将以他们选择的语言-Python熟悉这些经典任务。 对于准备进行编程采访的开发人员，该出版物可能会成为有价值的准备材料。
除了专业的程序员外，对于计算机科学专业的本科生且对Python感兴趣的学生，也可以认为这本书很有用。 它并不声称是对数据结构和算法的严格介绍。 这不是有关数据结构和算法的教程。 您不会在其页面上找到定理的证明或O大符号的大量使用。 相反，本书的定位是解决问题的方法的实用指南，这些问题应成为研究数据结构，算法和人工智能类别的最终产品。
我再次强调：假定读者熟悉Python的语法和语义。 零编程经验的读者不太可能从本书中受益，而对Python零经验的程序员可能会很难。 换句话说，“ Python中的经典计算机科学任务”是一本面向Python程序员和计算机科学专业学生的书。
摘录。 1.5。 河内塔
有三根高大的垂直柱（以下称为塔）。 我们将它们命名为A，B和C。在中心的孔上悬挂着位于塔A上的磁盘。最宽的磁盘-我们称为磁盘1-位于下方。 位于其上方的其余磁盘将以递增的数字表示，并逐渐减小。 例如，如果我们有三个磁盘，则其中最宽的磁盘（下面的磁盘）将具有编号1。下一个最宽的磁盘（位于编号2）将位于磁盘1上方。最后，最窄的磁盘（位于编号3）。将位于磁盘2上。
我们的目标是考虑以下限制，将所有驱动器从A塔移动到C塔。
- 一次只能移动一个磁盘。
- 唯一可移动的驱动器是任何塔架顶部的驱动器。
- 切勿将较宽的驱动器放在较窄的驱动器上。
示意性地，该任务如图2所示。 1.7。
1.5.1。 塔建模
堆栈是一种基于后进先出（LIFO）原理建模的数据结构。 到达堆栈的最后一件事成为从那里获取的第一个东西。 堆栈的两个主要操作是推入（put）和弹出（extract）。 推送操作将新项目推送到堆栈上，然后pop将其从堆栈中删除，并返回最后插入的项目。 您可以使用列表作为备份存储轻松地在Python中为堆栈建模（清单1.20）。
清单1.20 河内
from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container)
提出的Stack类实现了__repr __（）方法，使检查塔的内容变得容易。 __repr __（）是将print（）函数应用于堆栈时将输出的内容。
如导言所述，本书中使用了类型注释。 从输入模块导入Generic可使Stack成为类型注释中特定类型的参数类。 在T = TypeVar（'T'）中定义了任意类型T。 T可以是任何类型。 当类型注释随后用于Stack解决河内塔楼问题时，提示将为Stack [int]，即，将使用int类型代替T。 换句话说，这里的堆栈是整数的堆栈。 如果您在使用类型注释时遇到困难，请查看附录B。
堆栈非常适合河内塔挑战。 为了将磁盘移至塔架，我们可以使用推入操作。 为了将磁盘从一个塔架移动到另一个塔架，我们可以将其从第一个塔架（弹出式）推入，然后将其放在第二个塔架（推式）上。
将塔定义为Stack对象，并用磁盘填充第一个塔（清单1.21）。
清单1.21 hanoi.py（续）
num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i)
1.5.2。 解决河内塔楼问题
我该如何解决河内塔的问题？ 假设我们仅尝试移动一个驱动器。 那我们知道怎么做吧？ 实际上，移动一个磁盘是递归解决此问题的基本情况。 移动多个驱动器是递归的情况。 关键在于，实际上，我们有两种情况需要编码：移动一个磁盘（基本情况）和移动多个磁盘（递归情况）。
要了解递归情况，请考虑一个具体示例。 假设我们有三个磁盘-上，中和下三个磁盘，位于塔A上，并且我们希望将它们移动到C磁盘塔。将中间磁盘移至塔B，然后将上部磁盘从塔C移至塔B。现在我们将下部磁盘移至塔A，将两个上部磁盘移至塔B。从本质上讲，我们已经成功移动了两个磁盘从一个塔（A）行驶到另一座（B）。 基本情况是将下部磁盘从A移到C（移动一个磁盘）。 现在，可以使用与从A到B相同的过程将两个上部磁盘从B移到C。我们将上部磁盘移到A，将中间磁盘移到C，最后将上部磁盘从A移到C。
在计算机科学课程中，通常会发现这些塔的小模型是用销钉和塑料盘建造的。 您可以用三支铅笔和三张纸制作自己的模型。 也许这将帮助您可视化解决方案。
在具有三个磁盘的示例中，有一个简单的基本情况是移动一个磁盘，而递归的情况是使用临时的第三个塔来移动其余磁盘（在本例中为两个）。 我们可以将递归情况分为以下步骤。
- 使用C作为中间塔，将顶部n-1个驱动器从塔A移至塔B（临时）。
- 将下部驱动器从A移至C。
- 将n-1个磁盘从塔B移到塔C，塔A在中间。
令人惊讶的是，此递归算法不仅适用于三个磁盘，而且适用于任意数量的磁盘。 将其编码为hanoi（）函数，该函数负责使用第三个临时塔（清单1.22）将磁盘从一个塔移动到另一个塔。
清单1.22 hanoi.py（续）
def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1)
调用hanoi（）之后，您需要检查A，B和C塔，以确保磁盘已成功移动（清单1.23）。
代码清单1.23 hanoi.py（续）
if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c)
您会发现驱动器确实已移动。 在为河内塔架问题编码解决方案时，不必了解将几个磁盘从A座移动到C座的必要步骤。我们开始了解了将任意数量的磁盘移动并将其系统化的通用递归算法，使计算机可以完成其余工作。 这就是制定问题递归解决方案的能力：我们经常可以抽象地想象解决方案，而不会在每个动作的心理表示上浪费精力。
顺便说一句，hanoi（）函数将根据磁盘数量以指数方式执行，这使得即使对于64个磁盘也不适合该问题的解决方案。 您可以尝试通过更改变量num_discs在不同数量的磁盘上执行它。 随着磁盘数量的增加，完成河内塔式任务的步骤数呈指数增长；更多细节可在许多资源中找到。 如果您有兴趣了解有关此问题的递归解决方案背后的数学知识的更多信息，请参见Karl Birch在
“河内塔楼”一文中的解释。
1.6。 实际应用
本章介绍的各种方法（在位级别上的递归，内存，压缩和操作）在现代软件的开发中非常普遍，没有它们，就无法想象计算世界。 尽管没有任务也可以解决任务，但使用这些方法解决任务通常更合乎逻辑或更方便。
特别是，递归不仅是许多算法的基础，而且甚至是整个编程语言的基础。 在某些功能编程语言（例如Scheme和Haskell）中，递归替换了命令式语言中使用的循环。 但是，应该记住，使用递归方法可以实现的所有操作也可以迭代执行。
记忆化已成功用于加速解析器（解释语言的程序）的工作。 这在所有可能再次要求最近计算结果的任务中很有用。 记忆的另一项作用是编程语言运行时。 例如，对于Prolog版本，其中的某些运行时会自动保存函数调用的结果（自动混搭），因此下次不必通过同一调用执行该函数。 这类似于fib6（）中的@lru_cache（）装饰器。
压缩使带宽有限的Internet世界变得更加可承受。 第1.2节中讨论的位串方法适用于现实世界中具有有限数量可能值的简单数据类型，对于这些数据类型甚至1个字节都是冗余的。 但是，大多数压缩算法的工作原理是在数据集中寻找消除重复信息的模式或结构。 它们比1.2节中描述的要复杂得多。
一次性密码不适用于一般加密情况。 他们要求编码器和解码器都具有密钥之一（在我们的示例中为虚拟数据）以还原原始数据，这太麻烦了，并且在大多数加密方案中都无法实现这一目标-将密钥保密。 但是您可能想知道“一次性密码”这个名称是由间谍发明的，他们在冷战期间使用记录了虚拟数据的真实纸质笔记本来创建加密消息。
这些方法是程序的构建块；其他算法基于它们。 在以下各章中，您将看到它们的应用范围。
关于作者
David Kopec是位于佛蒙特州伯灵顿的尚普兰学院的计算机科学与创新高级讲师。 他是一位经验丰富的软件开发人员，着有《 Swift中的经典计算机科学问题》（Manning，2018年）和《 Dart for Absolute Beginners》（Apress，2014年）的作者。 David拥有达特茅斯学院（Dartmouth College）的经济学学士学位和计算机科学硕士学位。 您可以通过@davekopec在Twitter上与他联系。
»这本书的更多信息可以
在出版商的网站上找到»
目录»
摘录小贩优惠券25％优惠-Python
支付纸质版本的书后，就会通过电子邮件发送电子书。