书名：算法精粹：经典计算机科学问题的Python实现
ISBN：978-7-115-53512-2
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美] 大卫·科帕克（David Kopec）
译 戴 旭
责任编辑 杨海玲
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
Original English language edition, entitled Classic Computer Science Problems in Python by David Kopec published by Manning Publications Co., 209 Bruce Park Avenue, Greenwich, CT 06830. Copyright © 2019 by Manning Publications Co.
Simplified Chinese-language edition copyright © 2020 by Posts & Telecom Press. All rights reserved.
本书中文简体字版由Manning Publications Co.授权人民邮电出版社独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。
版权所有，侵权必究。
本书是一本面向中高级程序员的算法教程，借助Python语言，用经典的算法、编码技术和原理来求解计算机科学的一些经典问题。全书共9章，不仅介绍了递归、结果缓存和位操作等基本编程组件，还讲述了常见的搜索算法、常见的图算法、神经网络、遗传算法、k均值聚类算法、对抗搜索算法等，运用了类型提示等Python高级特性，并通过各级方案、示例和习题展开具体实践。
本书将计算机科学与应用程序、数据、性能等现实问题深度关联，定位独特，示例经典，适合有一定编程经验的中高级Python程序员提升用Python解决实际问题的技术、编程和应用能力。
谨以本书献给我的祖母Erminia Antos，她执教一生，学习一世。
感谢购买本书。Python是世界上最流行的编程语言之一，成为Python程序员的人具备各种不同的知识背景。有些人接受过正规的计算机科学教育，有些人学习Python只是出于兴趣爱好，还有一些人在专业场景中使用Python但他们的主要工作不是软件开发。本书算是一本中级教程，经验丰富的程序员在学习Python语言的一些高级特性时，本书中的问题将帮助他们在计算机科学方面温故而知新。通过用自己选择的Python语言学习经典的计算机问题，自学成才的程序员将加速他们的计算机科学学习进程。本书涵盖了多种多样的问题解决技术，因此确实能让所有人都有所收获。
本书不是Python的入门书籍。Manning和其他出版社都出版了很多优秀的入门书[1]。本书假定读者已是一名中高级Python程序员。虽然本书需要用到Python 3.7，但并不要求掌握最新版Python的所有特点。其实在构建本书内容时，我就假定本书能作为学习材料来使用，以便帮助读者掌握这些特点。也就是说，本书不适合对Python完全陌生的读者。
Python广泛应用于各种行业中，如数据科学、电影制作、计算机科学教学、IT管理等。还真没有哪个计算领域是Python没有涉及的（或许内核开发除外）。Python因其灵活性、优美而简洁的语法、纯粹的面向对象特性和活跃的社区而备受青睐。强大的社区非常重要，因为这表示Python欢迎新手的加入，也说明有庞大的现成库生态系统可供开发人员利用。
正是出于以上原因，Python有时被认为是一种适合初学者的语言，或许的确如此吧。例如，大多数人都同意Python比C++更容易学习，而且几乎可以肯定，Python的社区对新人更加友善。于是，许多人因为Python平易近人而学习它，他们相当迅速地着手编写所需的程序。但他们可能从未接受过计算机科学方面的教育，而这方面的教育可以教给他们当前所有强大的问题解决技术。如果你是一位了解Python但不熟悉计算机科学的程序员，那么本书正是为你准备的。
还有一部分人长期从事软件开发工作，他们将Python作为第2、3、4、5种语言来学习。对他们而言，在另一种语言中遇到过的老问题将有助于他们提高学习Python的速度，本书也许可作为他们求职面试前不错的复习资料，或者会揭示出一些以前工作中没有想过的问题解决技术。建议这些人先浏览一下目录，看看本书中是否有令他们兴奋的主题。
有人说计算机之于计算机科学，如同望远镜之于天文学一样。假如真是这样，那么编程语言也许就如同望远镜的镜头。不管怎么说，本书所用的“经典计算机科学问题”一词，指的是“通常在本科计算机科学课程中教授的编程问题 ”。
新手程序员总会遇到一些编程问题需要解决，这些问题已非常常见，堪称经典。无论是在攻读计算机科学、软件工程等学士学位的课堂上，还是在中级编程教材中（如人工智能或算法的入门书），均是如此。本书精选了一些这样的问题。
这些问题可以简单到只用几行代码就能解决，也可以复杂到需要通过多个章节的讲解来逐步搭建一个系统。有些问题涉及人工智能，而另一些问题则只需要常识就可以解决。有些问题比较贴近实际，而另一些问题则需要想象力。
第1章介绍多数读者大概都熟悉的问题解决技术，诸如递归、结果缓存（memoization）和位操作之类的后续章节探讨的其他技术所需的基本构件。
第2章的重点是搜索问题。搜索是一个庞大的议题，可以说本书中的大部分问题都能归属于它。这一章介绍了最重要的搜索算法，包括二分搜索、深度优先搜索、广度优先搜索和A*搜索。本书的其余部分都会反复用到这些算法。
第3章将搭建一个用于解决多类问题的框架，这些问题可以由带约束的有限域变量进行抽象化定义，包括八皇后问题、澳大利亚地图着色问题和算式谜题“SEND+MORE=MONEY”等经典问题。
第4章探讨图的算法，外行人将对这些图算法的应用范围之广表示惊叹。本章将构建图的数据结构，然后用它来解决几个经典的优化问题。
第5章探讨遗传算法，它的确定性尚不如本书的其他大部分算法，但有时可以用它解决那些用传统算法在合理时间内无法找到解的问题。
第6章介绍k均值聚类算法，这可能是本书最专注于某一算法的章节了。这种聚类技术易于实现、简单易懂且应用广泛。
第7章旨在解释什么是神经网络，让读者见识一个十分简单的神经网络。这一章的目标并非要全面介绍这一激动人心且不断发展的领域。本章将遵循第一性原理从头开始搭建神经网络，不用任何外部库，因此读者可以真正了解神经网络的工作原理。
第8章介绍双人全信息对奕游戏中的对抗搜索算法。本章将介绍一种极小化极大搜索算法，可用于开发一个会玩国际象棋、跳棋和四子棋等游戏的仿真棋手。
最后是第9章，介绍几个有趣好玩儿的问题，这些问题放在本书的其他地方都不太合适。
本书既适合经验丰富的程序员，也适合中级程序员。想要对Python加深认识的经验丰富的程序员将能从计算机科学或编程课程中轻松发现熟悉的问题。中级程序员则会被引领着用Python语言来解决这些经典问题。准备参加编程面试的开发人员也可能会发现本书是一份有用的准备材料。
除专业的程序员之外，对Python感兴趣的计算机科学专业本科在校生可能也会觉得本书很有用处。本书并没有严肃地讲解数据结构和算法。这不是一本数据结构和算法的教材。这里既没有证明过程，也没有多少大O符号。本书的定位是通俗易懂、便于实践的教程，目标是介绍问题解决技术，这些技术应该是学习数据结构、算法和人工智能课程之后的成果。
再次强调一下，本书假定读者已具备了Python语法和语义的知识。毫无编程经验的读者从本书中得不到什么益处，而没有Python经验的程序员也一定会举步维艰。换句话说，本书适合Python程序员和计算机科学专业的学生。
本书中的源代码遵守Python语言的3.7版的规范。代码运用到了只有Python 3.7才提供的Python特性，因此有些代码无法在低版本的Python中运行。请不必费力让这些示例代码在低版本的Python中运行了，先下载最新版的Python吧。
本书只会用到Python的标准库（第2章略有例外，其中安装了typing_extensions模块），因此本书的所有代码应该在所有支持Python的平台上（macOS、Windows、GNU/Linux等）都能运行。虽然本书的大部分代码在其他兼容版本的Python 3.7解释器中可能也能运行，但它们仅在CPython（Python官方提供的主流Python解释器）中进行了测试。
本书不会介绍Python工具的用法，如编辑器、IDE、调试器和Python REPL。本书中的源代码可在GitHub上搜索“Classic Computer Science Problems in Python”来获取。这些源代码按章放置在相应的文件夹中。在每章内容中代码清单的开头都带有源文件的名称，在代码仓库的对应文件夹中即可找到该源文件，只要输入python3 filename.py或python filename.py就应该能运行该章问题对应的代码，Python 3解释器的名称则取决于当前计算机的环境设置。
本书的所有代码清单全都用到了Python类型提示（type hint）特性，也称为类型注解（type annotation）。类型提示是Python语言相对较新的一种特性，对从未见过它们的Python程序员而言，或许有点儿望而生畏。使用类型提示的原因有以下3点。
（1）明晰了变量、函数参数和函数返回值的类型。
（2）有了第1点，在某种程度上就实现了代码的自文档化（self-document）。再也不必通过搜索注释或文档字符串（docstring）来了解函数的返回类型了，只需查看其签名即可。
（3）允许对代码进行类型检查，以确保正确性。mypy就是一种流行的Python类型检查程序。
并非每个人都会喜欢类型提示，坦率地说本书通篇采用这一特性就是冒险。我希望类型提示能够提供一些帮助，而不是成为一种障碍。编写带有类型提示的Python代码需要花费更多的时间，但是在回过头来阅读代码时会更加清晰。有意思的是，类型提示对在Python解释器中实际运行代码没有丝毫影响。对于本书任何代码，如果把类型提示删掉，代码应该照常运行。如果读者以前从未见过类型提示，并且在深入学习本书之前需要对其进行更全面的了解，请参阅附录C，那里给出了一堂关于类型提示特性的速成课。
本书没有包含产生图形输出或用到图形用户界面（GUI）的示例。因为本书的目标是用尽可能简洁、可读性良好的方案来解决问题。采用图形界面通常会增加负担，或者让阐述技术或算法的解决方案显著增加复杂度。
不仅如此，由于没有用到任何GUI框架，本书所有代码的可移植性都非常好。无论是在Linux的Python内嵌发行版上，还是在运行Windows的桌面端，这些代码都可以轻松运行。而且本书特意没有采用任何外部库，而是决定只采用Python标准库中的程序包，大多数高级Python教程也是如此。因为本书的目标是遵照第一性原理讲授问题解决技术，而不是讲解“用pip安装某个解决方案 ”。只有从头开始解决每个问题，才有可能理解那些广受欢迎的库背后的工作原理。至少，只采用标准库能让本书代码具有更好的可移植性，也更容易运行。
当然图形化解决方案有时会比基于文本的解决方案更能说明算法。只是本书的重点不在于此罢了。它会多一层不必要的复杂性。
这是Manning出版的“Classic Computer Science Problems”（经典计算机科学问题）系列书的第二本，第一本是Classic Computer Science Problems in Swift，已于2018年出版。透过几乎同样的计算机科学问题这一“镜头”，该系列书的目标是要在教学过程中结合具体编程语言给出一定的见解。
如果你喜爱本书并打算学习该系列书涵盖的其他语言，就会发现从一本书转到另一本书是提升该语言掌握程度的一种简单方法。到目前为止，该系列书只涵盖了Swift语言和Python语言。因为我对这两种语言都有丰富的经验，所以这两本书都是我写的，但我们已经在讨论以后的系列书的出版计划了，打算由其他编程语言的专家来进行合著。如果你喜欢这本书，希望能留意该系列书。
[1] 如果是刚开始接触Python，在开始阅读本书之前不妨先看看Naomi Ceder的《Python快速入门（第3版）》。
感谢Manning出版社每一位为出版本书提供过帮助的人：Cheryl Weisman、Deirdre Hiam、Katie Tennant、Dottie Marsico、Janet Vail、Barbara Mirecki、Aleksandar Dragosavljević、Mary Piergies和Marija Tudor。
感谢策划编辑Brian Sawyer，他在我完成Swift写作之后睿智地指引我转攻Python。感谢执行编辑Jennifer Stout，她总是正能量满满的。感谢技术编辑Frances Buontempo，她对每一章的内容都做了细致考量，每次都给出了细致有效的反馈。感谢文字编辑Andy Carroll和技术校对Juan Rufes，他们对我的Swift著作和本书都作了细致入微的检查，发现了我的多处错误。
以下人员也对本书进行了校阅：Al Krinker、Al Pezewski、Alan Bogusiewicz、Brian Canada、Craig Henderson、Daniel Kenney-Jung、Edmond Sesay、EwaBaranowska、Gary Barnhart、Geoff Clark、James Watson、Jeffrey Lim、Jens Christian、Bredahl Madsen、Juan Jimenez、Juan Rufes、Matt Lemke、Mayur Patil、Michael Bright、Roberto Casadei、Sam Zaydel、Thorsten Weber、Tom Jeffries和Will Lopez。感谢所有在本书编写过程中提供了建设性和明确意见的人。大家的反馈意见均已采纳。
感谢我的家人、朋友和同事们，正是他们在我出版了Classic Computer Science Problems in Swift之后鼓励我立即开始本书的撰写。感谢我在Twitter等平台上的所有线上好友，他们留下了很多鼓舞人心的话语，无论多少都对本书有所裨益。感谢我的妻子Rebecca Kopec和我的妈妈Sylvia Kopec，她们始终在支持着我的写作工作。
本书在相当短的时间内就完工了。绝大部分书稿是在2018年夏天基于之前的Swift版本完成的。我很感谢Manning愿意压缩成书的过程（通常时间会长久许多），这能让我按照最适合自己的进度进行工作。我知道这给整个团队带来了压力，因为我们在短短几个月内就邀请了很多人在多个不同层面进行了3轮校阅。大多数读者都会感到惊讶，原来传统出版社会对一本技术书籍进行如此多轮不同种类的校阅，还有这么多人参与评论和修改。技术校对、文字编辑、复核编辑以及所有的官方校阅人员，我感谢你们每一个人！
最后也是最重要的，感谢购买本书的读者。这个世界充斥着制作很不走心的在线教程，我认为支持书籍的编写非常重要，书籍能把同一位作者的话语像“展开画卷”一般释放出来。在线教程或许是一流的资源，但是你的购买行为可以让完整、经过严格审阅和精心编写的书籍仍然在计算机科学教育中占有一席之地。
大卫·科帕克（David Kopec）是香普兰学院（Champlain College）的计算机科学与创新专业助理教授，该学院位于美国佛蒙特州的伯灵顿市。他是一位经验丰富的软件开发人员，也是Classic Computer Science Problems in Swift和Dart for Absolute Beginners的作者。他拥有达特茅斯学院（Dartmouth College）的经济学学士学位和计算机科学硕士学位。
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
本书提供免费的源代码下载。要获得以上配套资源，请在异步社区本书页面中点击
，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
如果您是教师，希望获得教学配套资源，请在社区本书页面中直接联系本书的责任编辑。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，点击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线投稿（直接访问www.epubit.com/selfpublish/ submission即可）。
如果您来自学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
首先来探讨一些简单的小问题，只需用几个相对短小的函数即可解决。这些问题虽然都是些小问题，但仍可以用来探讨一些有趣的问题解决技巧。就把它们当作是一次很好的热身体验吧。
斐波那契序列（Fibonacci sequence）是一系列数字，其中除第1个和第2个数字之外，其他数字都是前两个数字之和：
0, 1, 1, 2, 3, 5, 8, 13, 21, …
在此序列中，第1个斐波那契数是0。第4个斐波那契数是2。后续任一斐波那契数n的值可用以下公式求得：
fib(n) = fib(n − 1) + fib(n − 2)
上述计算斐波那契序列数（如图1-1所示）的公式是一种伪代码形式，可将其简单地转换为一个Python递归函数，如代码清单1-1和代码清单1-2所示。所谓递归函数是一种调用自己的函数。这次机械的转换将作为你编写函数的首次尝试，返回的是斐波那契序列中的给定数。
代码清单1-1 fib1.py
def fib1(n: int) -> int:
return fib1(n - 1) + fib1(n - 2)
图1-1 每个火柴人的身高都是前两个火柴人身高之和
下面试着带上参数值来调用这个函数。
代码清单1-2 fib1.py（续）
if __name__ == "__main__":
print(fib1(5))
若我们运行fib1.py，系统就会生成一条错误消息：
RecursionError: maximum recursion depth exceeded这里有一个问题，fib1()将一直运行下去，而不会返回最终结果。每次调用fib1()都会再多调用两次fib1()，如此反复永无止境。这种情况被称为无限递归（如图1-2所示），类似于无限循环（infinite loop）。
图1-2 递归函数fib(n)带上参数n−2和n−1调用自己
请注意，在运行fib1()之前，Python运行环境不会有任何提示有错误存在。避免无限递归由程序员负责，而不由编译器或解释器负责。出现无限递归的原因是尚未指定基线条件（base case）。在递归函数中，基线条件即函数终止运行的时点。
就斐波那契函数而言，天然存在两个基线条件，其形式就是序列最开始的两个特殊数字0和1。0和1都不是由序列的前两个数求和得来的，而是序列最开始的两个特殊数字。那就试着将其设为基线条件吧，具体代码如代码清单1-3所示。
代码清单1-3 fib2.py
def fib2(n: int) -> int:
if n < 2: # base case
return n
return fib2(n - 2) + fib2(n - 1) # recursive case
注意 斐波那契函数的fib2()版本将返回0作为第0个数（fib2(0)），而不是第一个数，这正符合我们的本意。这在编程时很有意义，因为大家已经习惯了序列从第0个元素开始。
fib2()能被调用成功并将返回正确的结果。可以用几个较小的数试着调用一下，具体代码如代码清单1-4所示。
代码清单1-4 fib2.py（续）
if __name__ == "__main__":
print(fib2(5))
print(fib2(10))
请勿尝试调用fib2(50)，因为它永远不会终止运行！每次调用fib2()都会再调用两次fib2()，方式就是递归调用fib2(n - 1)和fib2(n - 2)（如图1-3所示）。换句话说，这种树状调用结构将呈指数级增长。例如，调用fib2(4)将产生如下一整套调用：
fib2(4) -> fib2(3), fib2(2)
fib2(3) -> fib2(2), fib2(1)
fib2(2) -> fib2(1), fib2(0)
fib2(2) -> fib2(1), fib2(0)
fib2(1) -> 1
fib2(1) -> 1
fib2(1) -> 1
fib2(0) -> 0
fib2(0) -> 0不妨来数一下（如果加入几次打印函数调用即可看明白），仅为了计算第4个元素就需要调用9次fib2()！情况会越来越糟糕，计算第5个元素需要调用15次，计算第10个元素需要调用117次，计算第20个元素需要调用21891次。我们应该能改善这种情况。
图1-3 每次非基线条件下的fib2()调用都会再生成两次fib2()调用
结果缓存（memoization）是一种缓存技术，即在每次计算任务完成后就把结果保存起来，这样在下次需要时即可直接检索出结果，而不需要一而再再而三地重复计算（如图1-4所示）[1]。
图1-4 人类的记忆缓存
下面创建一个新版的斐波那契函数，利用Python的字典对象作为结果缓存，如代码清单1-5所示。
代码清单1-5 fib3.py
from typing import Dict
memo: Dict[int, int] = {0: 0, 1: 1} # our base cases
def fib3(n: int) -> int:
if n not in memo:
memo[n] = fib3(n - 1) + fib3(n - 2) # memoization
return memo[n]
现在就可以放心地调用fib3(50)了，如代码清单1-6所示。
代码清单1-6 fib3.py（续）
if __name__ == "__main__":
print(fib3(5))
print(fib3(50))
现在一次调用fib3(20)只会产生39次fib3()调用，而不会像调用fib2(20)那样产生21891次fib2()调用。memo中预填了之前的基线条件0和1，并加了一条if语句大幅降低了fib3()的计算复杂度。
还可以对fib3()做进一步的简化。Python自带了一个内置的装饰器（decorator），可以自动为任何函数缓存结果。如代码清单1-7所示，在fib4()中，装饰器@functools.lru_cache()所用的代码与fib2()中所用的代码完全相同。每次用新的参数执行fib4()时，该装饰器就会把返回值缓存起来。以后再用相同的参数调用fib4()时，都会从缓存中读取该参数对应的fib4()之前的返回值并返回。
代码清单1-7 fib4.py
from functools import lru_cache
@lru_cache(maxsize=None)
def fib4(n: int) -> int: # same definition as fib2()
if n < 2: # base case
return n
return fib4(n - 2) + fib4(n - 1) # recursive case
if __name__ == "__main__":
print(fib4(5))
print(fib4(50))
注意，虽然以上斐波那契函数体部分与fib2()中的函数体部分相同，但能立刻计算出fib4(50)的结果。@lru_cache的maxsize属性表示对所装饰的函数最多应该缓存多少次最近的调用结果，如果将其设置为None就表示没有限制。
还有一种性能更好的做法，即可以用老式的迭代法来解决斐波那契问题，如代码清单1-8所示。
代码清单1-8 fib5.py
def fib5(n: int) -> int:
if n == 0: return n # special case
last: int = 0 # initially set to fib(0)
next: int = 1 # initially set to fib(1)
for _ in range(1, n):
last, next = next, last + next
return next
if __name__ == "__main__":
print(fib5(5))
print(fib5(50))
警告 fib5()中的for循环体用到了元组（tuple）解包操作，或许这有点儿过于卖弄了。有些人可能会觉得这是为了简洁而牺牲了可读性，还有些人可能会发现简洁本身就更具可读性，这里的要领就是last被设置为next的上一个值，next被设置为last的上一个值加上next的上一个值。这样在last已更新而next未更新时，就不用创建临时变量以存储next的上一个值了。以这种形式使用元组解包来实现某种变量交换的做法在Python中十分常见。
以上方案中，for循环体最多会运行n-1次。换句话说，这是效率最高的版本。为了计算第20个斐波那契数，这里的for循环体只运行了19次，而fib2()则需要21891次递归调用。对现实世界中的应用程序而言，这种强烈的反差将会造成巨大的差异！
递归解决方案是反向求解，而迭代解决方案则是正向求解。有时递归是最直观的问题解决方案。例如，fib1()和fib2()的函数体几乎就是原始斐波那契公式的机械式转换。然而直观的递归解决方案也可能伴随着巨大的性能损耗。请记住，能用递归方式求解的问题也都能用迭代方式来求解。
到目前为止，已完成的这些函数都只能输出斐波那契序列中的单个值。如果要将到某个值之前的整个序列输出，又该怎么做呢？用yield语句很容易就能把fib5()转换为Python生成器。在对生成器进行迭代时，每轮迭代都会用yield语句从斐波那契序列中吐出一个值，如代码清单1-9所示。
代码清单1-9 fib6.py
from typing import Generator
def fib6(n: int) -> Generator[int, None, None]:
yield 0 # special case
if n > 0: yield 1 # special case
last: int = 0 # initially set to fib(0)
next: int = 1 # initially set to fib(1)
for _ in range(1, n):
last, next = next, last + next
yield next # main generation step
if __name__ == "__main__":
for i in fib6(50):
print(i)
运行fib6.py将会打印出斐波那契序列的前51个数。for循环for i in fib6(50):每一次迭代时，fib6()都会一路运行至某条yield语句。如果直到函数的末尾也没遇到yield语句，循环就会结束迭代。
无论是在虚拟环境还是在现实世界，节省空间往往都十分重要。空间占用越少，利用率就越高，也会更省钱。如果租用的公寓大小超过了家中人和物所需的空间，你就可以“缩”到小一点的地方去，租金也会更便宜。如果数据存储在服务器上是按字节付费的，那么或许就该压缩一下数据，以便降低存储成本。压缩就是读取数据并对其进行编码（修改格式）的操作，以便减少数据占用的空间。解压缩则是逆过程，即把数据恢复为原始格式。
既然压缩数据的存储效率更高，那么为什么不把所有数据全部压缩一遍呢？这里就存在一个在时间和空间之间进行权衡的问题。压缩一段数据并将其解压回其原始格式需要耗费一定的时间。因此，只有在数据大小优先于数据传输速度的情况下，数据压缩才有意义。考虑一下通过互联网传输的大文件，对它们进行压缩是有道理的，因为传输文件所花的时间要比收到文件后解压的时间长。此外，为了能在服务器上存储文件而对其进行压缩所花费的时间则只需算一次。
数据类型占用的二进制位数要比其内容实际需要的多，只要意识到这一点，就可以产生最简单的数据压缩方案。例如，从底层考虑一下，如果一个永远不会超过65535的无符号整数在内存中被存储为64位无符号整数，其存储效率就很低。对此的替代方案可以是存储为16位无符号整数，这会让该整数实际占用的空间减少75%（64位换成了16位）。如果有数百万个这样的整数的存储效率都如此低下，那么浪费的空间累计可能会达到数兆字节。
为简单起见（当然这是一个合情合理的目标），有时候开发人员在Python里可以不用以二进制位方式来考虑问题。Python没有64位无符号整数类型，也没有16位无符号整数类型。这里只有一种int类型，可以存储任意精度的数值。用函数sys.getsizeof()可以查出Python对象占用的内存字节数。但由于Python对象系统的固有开销，在Python 3.7中无法创建少于28字节（224位）的int类型。每个int类型对象每次可以扩大1个二进制位（本例就会如此操作），但最少也要占用28字节。
注意 如果对二进制有点生疏，请记得每个二进制位就是一个1或0的值。以2为进制读出的一系列1和0就可以表示一个数。按照本节的讲解目标，不需要以2为进制进行任何数学运算，但需要理解某个数据类型的存储位数决定了它可以表示的不同数值的个数。例如，1个二进制位可以表示2个值（0或1），2个二进制位可以表示4个值（00、01、10、11），3个二进制位则可以表示8个值，以此类推。
如果某个类型需要表示的不同值的数量少于存储二进制位可表示值的数量，或许存储效率就能得以提高。不妨考虑一下DNA中组成基因的核苷酸[2]。每个核苷酸的值只能是这4种之一：A、C、G或T（更多相关信息将会在第2章中介绍）。如果基因用str类型存储（str可被视作Unicode字符的集合），那么每个核苷酸将由1个字符表示，每个字符通常需要8个二进制位的存储空间。如果采用二进制，则有4种可能值的类型只需要用2个二进制位来存储，00、01、10和11就是可由2个二进制位表示的4种不同值。如果A赋值为00、C赋值为01、G赋值为10、T赋值为11，那么一个核苷酸字符串所需的存储空间可以减少75%（每个核苷酸从8个二进制位减少到2个二进制位）。
因此可以不把核苷酸存储为str类型，而存储为位串（bit string）类型（如图1-5所示）。正如其名，位串就是任意长度的一系列1和0。不幸的是，Python标准库中不包含可处理任意长度位串的现成结构体。代码清单1-10中的代码将把一个由A、C、G和T组成的str转换为位串，然后再转换回str。位串存储在int类型中。因为Python中的int类型可以是任意长度，所以它可以当成任意长度的位串来使用。为了将位串类型转换回str类型，就需要实现Python的特殊方法__str__()。
图1-5 将代表基因的str压缩为每个核苷酸占2位的位串
代码清单1-10 trivial_compression.py
class CompressedGene:
def __init__(self, gene: str) -> None:
self._compress(gene)
CompressedGene类需要给定一个代表基因中核苷酸的str字符串，内部则将核苷酸序列存储为位串。__init__()方法的主要职责是用适当的数据初始化位串结构体。_init__()将调用_compress()，将给定核苷酸str转换成位串的苦力活实际由_compress()完成。
注意，_compress()是以下划线开头的。Python没有真正的私有方法或变量的概念。所有变量和方法都可以通过反射访问到，Python对它们没有严格的强制私有策略。前导下划线只是一种约定，表示类的外部不应依赖其方法的实现。这一类方法可能会发生变化，应该被视为私有方法。
提示 如果类的方法或实例变量名用两个下划线开头，Python将会对其进行名称混淆（name mangle），通过加入盐值（salt）来改变其在实现时的名称，使其不易被其他类发现。本书用一条下划线表示“私有”变量或方法，但如果真要强调一些私有内容，或许得用两条下划线才合适。要获取有关Python命名的更多信息，参阅PEP 8中的“描述性命名风格”（Descriptive Naming Styles）部分。
下面介绍如何真正地执行压缩操作，具体代码如代码清单1-11所示。
代码清单1-11 trivial_compression.py（续）
def _compress(self, gene: str) -> None:
self.bit_string: int = 1 # start with sentinel
for nucleotide in gene.upper():
self.bit_string <<= 2 # shift left two bits
if nucleotide == "A": # change last two bits to 00
self.bit_string |= 0b00
elif nucleotide == "C": # change last two bits to 01
self.bit_string |= 0b01
elif nucleotide == "G": # change last two bits to 10
self.bit_string |= 0b10
elif nucleotide == "T": # change last two bits to 11
self.bit_string |= 0b11
else:
raise ValueError("Invalid Nucleotide:{}".format(nucleotide))
_compress()方法将会遍历核苷酸str中的每一个字符。遇到A就把00加入位串，遇到C则加入01，依次类推。请记住，每个核苷酸需要两个二进制位，因此在加入新的核苷酸之前，要把位串向左移两位（self.bit_string<<= 2）。
添加每个核苷酸都是用“或”（|）操作进行的。当左移操作完成后，位串的右侧会加入两个0。在位运算过程中，0与其他任何值执行“或”操作（如self.bit_string | = 0b10）的结果都是把0替换为该值。换句话说，就是在位串的右侧不断加入两个新的二进制位。加入的两个位的值将视核苷酸的类型而定。
下面来实现解压方法和调用它的特殊方法__str__()，如代码清单1-12所示。
代码清单1-12 trivial_compression.py（续）
def decompress(self) -> str:
gene: str = ""
for i in range(0, self.bit_string.bit_length() - 1, 2): # -1 to exclude sentinel
bits: int = self.bit_string >> I & 0b11 # get just 2 relevant bits
if bits == 0b00: # A
gene += "A"
elif bits == 0b01: # C
gene += "C"
elif bits == 0b10: # G
gene += "G"
elif bits == 0b11: # T
gene += "T"
else:
raise ValueError("Invalid bits:{}".format(bits))
return gene[::-1] # [::-1] reverses string by slicing backward
def __str__(self) -> str: # string representation for pretty printing
return self.decompress()
decompress()方法每次将从位串中读取两个位，再用这两个位确定要加入基因的str尾部的字符。与压缩时的读取顺序不同，解压时位的读取是自后向前进行的（从右到左而不是从左到右），因此最终的str要做一次反转（用切片表示法进行反转[::-1]）。最后请留意一下，int类型的bit_length()方法给decompress()的开发带来了很大便利。下面来试试效果吧。具体代码如代码清单1-13所示。
代码清单1-13 trivial_compression.py（续）
if __name__ == "__main__":
from sys import getsizeof
original: str = "TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATA TATATATAGCCATGGATCGATTATA" * 100
print("original is {} bytes".format(getsizeof(original)))
compressed: CompressedGene = CompressedGene(original) # compress
print("compressed is {} bytes".format(getsizeof(compressed.bit_string)))
print(compressed) # decompress
print("original and decompressed are the same: {}".format(original ==
compressed.decompress()))
利用sys.getsizeof()方法，输出结果时就能显示出来，通过该压缩方案确实节省了基因数据大约75%的内存开销。具体代码如代码清单1-14所示。
代码清单1-14 trivial_compression.py的输出结果
original is 8649 bytes
compressed is 2320 bytes
TAGGGATTAACC…
original and decompressed are the same: True注意 在CompressedGene类中，为了判断压缩方法和解压方法中的一系列条件，大量采用了if语句。因为Python没有switch语句，所以这种情况有点儿普遍。在Python中有时还会出现一种情况，就是高度依靠字典对象来代替大量的if语句，以便对一系列的条件做出处理。不妨想象一下，可以用字典对象来找出每个核苷酸对应的二进制位形式。有时字典方案的可读性会更好，但可能会带来一定的性能开销。尽管查找字典在技术上的复杂度为O(1)，但运行哈希函数存在开销，这有时会意味着字典的性能还不如一串if。是否采用字典，取决于具体的if语句做判断时需要进行什么计算。如果在关键代码段中要在多个if和查找字典中做出取舍，或许该分别对这两种方法运行一次性能测试。
一次性密码本（one-time pad）是一种加密数据的方法，它将无意义的随机的假数据（dummy data）混入数据中，这样在无法同时拿到加密结果和假数据的情况下就不能重建原始数据。这实质上是给加密程序配上了密钥对。其中一个密钥是加密结果，另一个密钥则是随机的假数据。单个密钥是没有用的，只有两个密钥的组合才能解密出原始数据。只要运行无误，一次性密码本就是一种无法破解的加密方案。图1-6演示了这一过程。
图1-6 一次性密码本会产生两个密钥，它们可以分开存放，后续可再组合起来以重建原始数据
以下示例将用一次性密码本方案加密一个srt。Python 3的str类型有一种用法可被视为UTF-8字节序列（UTF-8是一种Unicode字符编码）。通过encode()方法可将str转换为UTF-8字节序列（以bytes类型表示）。同理，用bytes类型的decode()方法可将UTF-8字节序列转换回str。
一次性密码本的加密操作中用到的假数据必须符合3条标准，这样最终的结果才不会被破解。假数据必须与原始数据长度相同、真正随机、完全保密。第1条标准和第3条标准是常识。如果假数据因为太短而出现重复，就有可能被觉察到规律。如果其一个密钥不完全保密（可能在其他地方被重复使用或部分泄露），那么攻击者就能获得一条线索。第2条标准给自己出了一道难题：能否生成真正随机的数据？大多数计算机的答案都是否定的。
本例将会用到secrets模块的伪随机数据来生成函数token_ bytes()（自Python 3.6开始包含在于标准库中）。这里的数据并非是真正随机的，因为secrets包在幕后采用的仍然是伪随机数生成器，但它已足够接近目标了。下面就来生成一个用作假数据的随机密钥，具体代码如代码清单1-15所示。
代码清单1-15 unbreakable_encryption.py
from secrets import token_bytes
from typing import Tuple
def random_key(length: int) -> int:
# generate length random bytes
tb: bytes = token_bytes(length)
# convert those bytes into a bit string and return it
return int.from_bytes(tb, "big")
以上函数将创建一个长度为length字节的int，其中填充的数据是随机生成的。int. from_bytes()方法用于将bytes转换为int。如何将多字节数据转换为单个整数呢？答案就在1.2节。在1.2节中已经介绍过int类型可为任意大小，而且还展示了int能被当作通用的位串来使用。本节以同样的方式使用int。例如，from_bytes()方法的参数是7字节（7字节×8位/字节= 56位），该方法会将这个参数转换为56位的整数。为什么这种方式很有用呢？因为与对序列中的多字节进行操作相比，对单个int（读作“长位串”）进行位操作将更加简单高效。下面将会用到XOR位运算。
如何将假数据与待加密的原始数据进行合并呢？这里将用XOR操作来完成。XOR是一种逻辑位操作（二进制位级别的操作），当其中一个操作数为真时返回true，而如果两个操作数都为真或都不为真则返回false。可能大家都已猜到了，XOR代表“异或”。
Python中的XOR操作符是“^”。在二进制位的上下文中，0^1和1^0将返回1，而0^0和1^1则会返回0。如果用XOR合并两个数的二进制位，那么把结果数与其中某个操作数重新合并即可生成另一个操作数，这是一个很有用的特性。
A ^ B = C
C ^ B = A
C ^ A = B上述重要发现构成了一次性密码本加密方案的基础。为了生成结果数据，只要简单地将原始str以字节形式表示的int与一个随机生成且位长相同的int（由random_key()生成）进行异或操作即可。返回的密钥对就是假数据和加密结果。具体代码如代码清单1-16所示。
代码清单1-16 unbreakable_encryption.py（续）
def encrypt(original: str) -> Tuple[int, int]:
original_bytes: bytes = original.encode()
dummy: int = random_key(len(original_bytes))
original_key: int = int.from_bytes(original_bytes, "big")
encrypted: int = original_key ^ dummy # XOR
return dummy, encrypted
注意 int.from_bytes()要传入两个参数。第一个参数是需要转换为int的bytes。第二个参数是这些字节的字节序（endianness）"big"。字节序是指存储数据所用的字节顺序。首先读到的是最高有效字节（most significant byte），还是最低有效字节（least significant byte）？在本示例中，只要加密和解密时采用相同的顺序就无所谓，因为实际只会在单个二进制位级别操作数据。如果是在编码过程的两端不全由自己掌控的其他场合，字节序可能是至关重要的因素，所以请务必小心！
解密过程只是将encrypt()生成的密钥对重新合并而已。只要在两个密钥的每个二进制位之间再次执行一次XOR运算，就可完成解密任务了。最终的输出结果必须转换回str。首先，用int.to_bytes()将int转换为bytes。该方法需要给定int要转换的字节数。只要把总位长除以8（每字节的位数），就能获得该字节数。最后，用bytes类型的decode()方法即可返回一个str。具体代码如代码清单1-17所示。
代码清单1-17 unbreakable_encryption.py（续）
def decrypt(key1: int, key2: int) -> str:
decrypted: int = key1 ^ key2 # XOR
temp: bytes = decrypted.to_bytes((decrypted.bit_length()+ 7) // 8, "big")
return temp.decode()
在用整除操作（//）除以8之前，必须给解密数据的长度加上7，以确保能“向上舍入”，避免出现边界差一（off-by-one）错误。如果上述一次性密码本的加密过程确实有效，那么应该就能毫无问题地加密和解密Unicode字符串了。具体代码如代码清单1-18所示。
代码清单1-18 unbreakable_encryption.py（续）
if __name__ == "__main__":
key1, key2 = encrypt("One Time Pad!")
result: str = decrypt(key1, key2)
print(result)
如果控制台输出了“One Time Pad!”，就万事大吉了。
数学意义重大的π（3.14159…）用很多公式都可以推导出来，其中最简单的公式之一就是莱布尼茨公式。它断定以下无穷级数的收敛值等于π：
π = 4/1 − 4/3 + 4/5 − 4/7 + 4/9 − 4/11…
请注意，以上无穷级数的分子保持为4，而分母则每次递增2，并且对每一项的操作是加法和减法交替出现。
将上述公式的每一项转换为函数中的变量，就能直接对该无穷级数进行建模。分子可以是常数4。分母可以是从1开始并以2递增的变量。至于加法或减法操作，可以表示为−1或1。代码清单1-19中，用变量pi在for循环过程中保存各级数之和。
代码清单1-19 calculating_pi.py
def calculate_pi(n_terms: int) -> float:
numerator: float = 4.0
denominator: float = 1.0
operation: float = 1.0
pi: float = 0.0
for _ in range(n_terms):
pi += operation * (numerator / denominator)
denominator += 2.0
operation *= -1.0
return pi
if __name__ == "__main__":
print(calculate_pi(1000000))
提示 在大多数平台中，Python的float类型是64位的浮点数（或C语言中的double类型）。
在建模或仿真某个有趣的概念时，公式和程序代码之间作生搬硬套式的直接转换是一种简单而高效的方案，以上函数就给出了很好的示例。直接转换是一种有用的工具，但必须时刻牢记它不一定是最有效的解决方案。其实，π的莱布尼茨公式可以用更加高效或紧凑的代码来实现。
注意 无穷级数的项数越多（调用calculate_pi()时给出的n_terms的值越大），π的最终计算结果就会越精确。
本题共涉及3根立柱（以下称为“塔”），不妨将其标为A、B和C。塔A外面套有几个环形的圆盘。最大的圆盘位于底部，不妨将其称为圆盘1。圆盘1上方的其他圆盘标记为不断增大的数字，圆盘尺寸则不断减小。假定要移动3个圆盘，最大也是底部的圆盘就是圆盘1。第二大的圆盘2将放在圆盘1的上方。最小的圆盘3则放在圆盘2的上方。本题的目标是按以下规则把所有圆盘从塔A移动到塔C：
图1-7对本题给出了总体说明。
图1-7 本题的挑战是把3个圆盘从塔A移到塔C，每次移动一个圆盘，不允许把大圆盘压在小圆盘之上
栈是按照后进先出（LIFO）理念建模的数据结构。最后入栈的数据项会最先出栈。栈的两个最基本操作是压入（push）和弹出（pop）。压入操作是把一个新数据项放入栈中，而弹出操作则是移除并返回最后一次放入的数据项。在Python中用list类型作为底层存储，即可轻松对栈进行建模。具体代码如代码清单1-20所示。
代码清单1-20 hanoi.py
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__()方法，这样想要查看某个塔的状况就比较容易了。对Stack类调用print()时，输出的就是__repr__()的结果。
注意 正如本书引言中所述，本书通篇都会使用类型提示。从typing模块导入Generic，就能让Stack在类型提示时泛型化为某种类型。T = TypeVar('T')定义了任意类型T。T可以是任何类型。后续在求解汉诺塔问题时使用的Stack，就用到了类型提示，类型提示为Stack[int]类型，表示T应该填入int类型的数据。换句话说，该栈是一个整数栈。如果对类型提示还存在困惑，不妨阅读一下附录C。
栈是汉诺塔的完美表现。要把圆盘放到塔上，可以进行压入操作。要把圆盘从一个塔移到另一个塔，就可以先从第一个塔弹出再压入第二个塔上。
下面将塔定义为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)
汉诺塔问题该如何求解呢？不妨想象一下只需移动一个圆盘的情况。做法大家都该知道吧！实际上，移动一个圆盘正是汉诺塔递归解决方案的基线条件。需要递归完成的是移动多个圆盘的情况。因此，要点就是有两种情况需要编写代码：移动一个圆盘（基线条件）和移动多个圆盘（递归情况）。
为了理解需要递归完成的情况，不妨看一个具体的例子。假设塔A上套有上、中、下3个圆盘，这3个圆盘最终都要被移到塔C上去。遍历一遍全过程或许有助于把问题讲清楚。首先可以把顶部圆盘移到塔C。再将中间圆盘移到塔B。然后可以将顶部圆盘从塔C移到塔B。现在底部圆盘仍在塔A，上面的两个圆盘则在塔B。现在已大致成功将两个圆盘从一个塔（A）移到了另一个塔（B）。把底部圆盘从A移到C其实就是基线条件（移动单个圆盘）。现在可以按照从A到B的相同步骤把两个上面的圆盘从B移到C。将顶部圆盘移到A，将中间圆盘移到C，最后将顶部圆盘从A移到C。
提示 在讲述计算机科学的课堂上，常常可以见到用木柱和塑料圈制作的塔的小模型。大家可以用3支铅笔和3张纸制作自己的模型。这或许有助于将解决方案直观地呈现出来。
在上述3个圆盘的示例中，包含一种简单的移动单个圆盘的基线条件，以及一种移动其他所有圆盘（这里为两个）的递归情况，这里用到了第3个塔作为暂存塔。递归的情况可以被拆分为以下3步。
（1）将上层n−1个圆盘从塔A移到塔B（暂存塔），用塔C作为中转塔。
（2）将底层的圆盘从塔A移到塔C。
（3）将n−1个圆盘从塔B移到塔C，用塔A作为中转塔。
令人惊奇的是，这种递归算法不仅适用于3个圆盘的情况，还适用于任意数量的圆盘。下面将此算法编码成名为hanoi()的函数，该函数负责将圆盘从一个塔移到另一个塔，参数中给出第3个暂存塔。具体代码如代码清单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_disc变量，多试几个不同的圆盘数。随着圆盘数量的增加，所需移动步数将呈指数级增加，这正是汉诺塔的传奇之处。关于汉诺塔的传说的更详细信息在很多地方都能找到。读者若有兴趣了解有关此递归解法背后的数学原理，可参阅Carl Burch在“关于汉诺塔”（About the Towers of Hanoi）中的解释。
本章介绍的各种技术（递归、结果缓存、压缩和位级操作）在现代软件开发过程中是很常用的，如果没有它们，难以想象计算的世界会是什么样的，虽然没有它们也能解决问题，但用这些技术解决起来往往逻辑性更强、效率更高。
递归尤其如此，它不仅是很多算法的核心，甚至还是整个编程语言的核心。在一些函数式编程语言中，如Scheme和Haskell，递归取代了命令式语言中使用的循环。但是，递归技术可以完成的任务用迭代技术也能实现，这一点值得牢记在心。
结果缓存已成功应用于解析器（解释型语言用到的程序）的加速工作。对于解决有可能再次请求最近计算结果的问题，结果缓存就会很有用。结果缓存的另一个应用就是程序语言的运行时（runtime）。某些程序语言的运行时（如Prolog的多个版本）会把函数调用的结果自动保存下来（自动化结果缓存），这样下次发起相同调用时就不需要再执行这些函数了。这种机制类似于fib6()中的修饰符@lru_cache()。
压缩技术已经让饱受带宽限制的互联网世界变得流畅多了。对于现实世界中取值范围有限的简单数据类型，多一个字节都是浪费，于是在1.2节中检验过的位串技术就十分有用了。不过大多数压缩算法都是通过在数据集中找到某些模式或结构，从而使重复信息得以消除。它们比1.2节中介绍的方案要复杂得多。
一次性密码本对于普通的加密是不大实用的。为了重建原始数据，一次性密码本方案要求加密程序和解密程序同时拥有其中一个密钥（示例中为假数据），这很麻烦并且违背了大多数加密方案的目标（保持密钥的秘密性）。但是大家可以了解一下，“一次性密码本”这个名称来自间谍，在冷战期间，他们使用真正的密码纸和其上的假数据来创建加密通信。
上述这些技术是编程的基本构件，其他算法是构建在其上的。后续章节将会展示关于它们的大量应用。
1．用自己设计的技术编写其他一种求解斐波那契序列元素n的函数。请编写单元测试以评估其正确性，以及相对于本章各版本的性能差异。
2．大家已经了解了用Python中的简单类型int表示位串的做法。请编写一个人机友好的int封装类，以使其能通用地当作位序列来使用（使其可迭代并实现__getitem__()方法）。请利用该int封装类重新实现一遍CompressedGene。
3．编写代码求解塔数任意的汉诺塔问题。
4．用一次性密码本方案加密并解密图像。
[1] 英国知名计算机科学家Donald Michie创造了memoization这个术语。参见 Donald Michie 的 Memo functions: a language feature with “rote-learning” properties（Edinburgh University，Department of Machine Intelligence and Perception，1967）。
[2] 本例受到Robert Sedgewick和Kevin Wayne的《算法（第4版）》（第819页）的启发。
