详情
这是一本介绍通过解决复杂算法谜题来学习编程的书，书中的代码用Python语言编写。本书将对代码功能的理解与编程语言语法和语义的理解分离开来，从解每个谜题开始，先给出解谜题的算法，随后用Python语法和语义实现对应的算法，并适当做出解释。本书包含了21个谜题，其中很多谜题都广为流传，如多皇后、汉诺塔、验证六度分隔猜想等，每个谜题后面都配有不同难度的编程习题，帮读者加深对相关算法的理解
书名：编程的乐趣：用Python解算法谜题
ISBN：978-7-115-50943-7
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美] 斯里尼•德瓦达斯（Srini Devadas）
译 戴 旭 李亚舟 许亚运
责任编辑 杨海玲
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
这是一本介绍通过解决复杂谜题来学习编程的书，书中的代码用Python语言编写。与以往的编程书不同，本书将对代码功能的理解与编程语言语法和语义的理解分离开来，从解每个谜题开始，先给出解谜题的算法，随后用Python语法和语义实现对应的算法，并适当做出解释。本书包含了21个谜题，其中很多谜题都广为流传，如多皇后、汉诺塔、在几秒钟内解决数独问题、验证六度分隔猜想等，每个谜题后面都配有不同难度的编程习题，帮读者加深对相关算法的理解。
本书在算法谜题的趣味性和计算机编程的实用性之间搭建了一座桥梁，内容饶有趣味，讲述易于理解，适合已掌握初级编程概念并对算法感兴趣的学习者阅读和参考。
Programming for the Puzzled: Learn to Program While Solving Puzzles by Srini Devadas
©2017 Massachusetts Institute of Technology
Simplified Chinese translation copyright © 2019 by Posts & Telecom Press.
This edition published by arrangement with MIT Press through Bardon-Chinese Media Agency. All rights reserved.
本书简体中文版由Bardon-Chinese Media Agency 代理MIT Press授权人民邮电出版社独家出版发行。未经出版者书面许可，不得以任何方式复制或节录本书中的任何内容。
版权所有，侵权必究。
谜题趣味非凡。顶级谜题的解可没那么浅显易得，需要灵光一闪才能发现。算法谜题是指谜题的解法就是算法，解题的步骤可以被机器自动执行。算法可以用英文或者其他任何自然语言来描述，但是为了更加精确，往往会用伪代码进行描述。之所以称为“伪代码”，是因为它尚未细化到足以在计算机上运行的程度，与用编程语言编写的代码不大一样。
当今世界有越来越多的人以计算机编程为业。为了学习编程，我们首先要通过简单的例子学习基本的编程结构，例如赋值语句和控制循环之类，而编程习题往往涉及将算法的伪代码转译为用所学编程语言编写的代码。程序员同样能从求解谜题所需的分析技能中获益。无论是将规格说明转换为编程结构，还是定位早期代码中的错误（也就是调试过程），这些分析技能都不可或缺。
我在MIT教大一和大二学生编程有几十年了，我越来越清楚学生对实际应用的兴趣十分强烈。很少有人愿意为了编程而编程。谜题（puzzle）就是一种最棒的实际应用，它的优势在于易于描述和引人注目。后者如今尤为重要，因为讲课者必须和Snapchat、Facebook和Instagram争夺注意力。正如我的前辈们一样，我也发现让学生犯困的最佳方法就是介绍讨厌的编程语法或语义，只要几分钟就够了。
本书是我对编程教学的一次尝试，在算法谜题的趣味性与计算机编程的实用性之间架起一座桥梁。这里假定读者对编程的基本概念已有起码的了解，这些概念可以通过学习高中阶段的计算机科学入门课或大学预修（Advanced Placement，AP）课获得，也可以通过学习MITx/edX 6.0001x之类的课程获得。
本书中每个谜题的开始都会介绍一道谜题，其中不少谜题都脍炙人口，以各种变体形式在一些出版物和网站上出现过。在经历一两次失败的解谜尝试之后，突然灵光一闪，一种搜索策略、一个数据结构、一个数学公式跃然而出，答案就这么自行现身了。有时候会对谜题给出明显“暴力”的解法，本书会先解释相关的算法与代码，再将其解释为“失败”，然后再“捧出真经”，引出更加优雅和高效的解法。
谜题的解法就是需要编写的代码的规格说明书。读者要先了解代码要做的事情，然后再看代码。我坚信这是一种很强大的教学理念，因为这把对代码功能的理解与编程语言语法和语义的理解分离开来。对于理解代码所需的语法和语义，将本着“现学现用”的原则进行介绍。
由谜题的物理世界到程序的计算机世界虽然很有趣，但并不总是一帆风顺。在某些情况下，必须假定某些操作在计算机世界中效率低下，因为其在物理世界中就是如此。本书会尽量减少这种情况的出现，但是仍无法完全避免。相信这不会对学习造成困扰，而且在极少出现的几处地方，书中都会明确指出。
读者可以采取多种方式来阅读和使用本书。如果仅对谜题本身及其答案感兴趣，完全可以在想出自己的解法或阅读本书给出的解法后即刻停止。但我不希望读者就此止步，因为讲解如何得出解法并转成可执行代码是写作本书的主要目的。读完整个谜题将对编写实用的程序所需的要素有很好的感知，实用的程序能供任何人自行运行和使用。我尽力确保对Python语法和语义的介绍能满足解谜代码的需要，但如果读者对Python语法、语义和库等有任何疑问，则Python的官方网站上有极佳的学习资源，edX/MITx 6.0001x课程也有对Python编程的很好介绍。
如果读者能在自己的计算机上安装和运行Python，就会从本书收获更多东西。这可以通过访问Python的官方网站来实现。书中所有谜题解法的代码都可以从MIT出版社网站下载。这些代码已在Python 2.7及以上版本（包括3.x版本）中测试过。当然，欢迎读者忽略这些可下载的代码，而编写自己的解题代码。强烈建议读者采用与书中示例不同的输入运行一下从网站下载或自行编写的程序。尽管我确实已尽力去除程序中的bug，但仍不能保证代码没有错误。注意，加入对输入的检查会让代码显得零乱，因此，书中给出的代码假定输入符合谜题的描述，如果使用出乎意料的输入就不一定会有预期的表现了。为了加深对编程的理解，有一种最好的方式就是不断改进每一个谜题的代码，严格地检查格式错误的输入。
在每个谜题的结尾都会有几道编程的习题。这些习题的难度与所需编写的代码量各有不同。做完每个谜题的习题，将有助于充分掌握本书的内容。读者必须对谜题相关的代码有足够的理解，然后才有能力对其做出修改或改进其功能。书中的一部分习题包含了对错误输入的检查。标为“难题”的习题需要相当大的代码量，或要对已给出的谜题代码进行重构。其中的一部分难题可视为已介绍谜题的高级版本。本书没有提供习题和谜题的答案，教学人员可到MIT出版社网站的本书页面去获取。
我始终坚信应通过实践来学习，如果你能成功地自行完成所有习题，你将顺利成为一名计算机科学家！祝你好运。
我在我的母校加州大学伯克利分校休假期间写了这本书。感谢Robert Brayton教授让我借用他在Cory Hall的办公室，在那里我完成了本书的大部分内容。感谢我在伯克利的房东Sanjit Seshia、Kurt Keutzer和Dawn Song让我享受了一个愉快且富有成果的假期。
我第一次教软件工程是与Daniel Jackson一起，这门课程使用Java作为编程语言。Daniel对编程语言和软件工程的看法对我影响深远。我们在JavaScript加速器研讨会的合作中，为了更好地讲解基本的编程概念，出了一些谜题，例如通过不同的方式计算邮费。
我第一次教授计算机科学与编程导论是与John Guttag一起，这门课程主要面向非计算机科学专业的学生。John的教学富有热情、非常有感染力，让我也喜欢上了使用Python教授编程导论。在本书中，我借鉴了不止一道他在教学中使用过的例题，例如通过二分搜索求平方根。
本书使用的一些谜题源于我与Adam Chlipala和Ilia Lebedev在2015年到2016年间合作开发的一门课程—— 编程基础（Fundamentals of Programming）。在课程的课件与作业中，大家贡献了从作为草稿的演示代码到“生产级别”的可用代码。尤其感谢Zhang Yuqing、Rotem Hemo和Jenny Ramseyer，他们分别编写了谜题11“请铺满庭院”、谜题15“统计零钱的组合方式”和谜题21“问题有价”的代码。大约有400名学生选修了2017年春季的编程基础课程，与Duane Boning、Adam Hartz和Chris Terman一起教这门课是一段非常愉快的经历。
谜题3“拥有（需要一点校准的）读心术”曾是计算机科学的数学（Mathematics for Computer Science）这门课的经典题目，我并不清楚它来自谁的发明，但感谢Nancy Lynch向我推荐了这道题目，并且感谢她在我为15年前的第一堂课伤神不已时扮演了“魔术助手”。这道谜题的描述来自三位讲师Eric Lehman、Tom Leighton和Albert Meyer的课堂笔记。
Kaveri Nadhamuni也在谜题6“寻找假币”、谜题8“猜猜谁不来吃晚餐”、谜题9“美国达人秀”和谜题16“贪心是好事”上给了我帮助。Eleanor Boyd在“代码女孩计划”中测试了“寻找假币”这道谜题，并给出了很有价值的反馈。
Ron Rivest对本书中的许多谜题提出了优化和总结，这些谜题包括谜题1“保持一致”、谜题2“参加派对的最佳时间”、谜题5“请打碎水晶”、谜题8“猜猜谁不来吃晚餐”、谜题17“字母也疯狂”和谜题18“充分利用记忆”。
Billy Moses仔细阅读了本书，并给出了许多建议。
与同事Costis Daskalakis、Erik Demaine、Manolis Kellis、Charles Leiserson、Nancy Lynch、Vinod Vai kuntanathan、Piotr Indyk、Ron Rivest和Ronitt Rubinfeld一起教授算法导论（Introduction to Algorithms）、算法设计与分析（Design and Analysis of Algorithms）这两门课程的经历，使我的算法能力得到了提高。与同事Saman Amarasinghe、Adam Chlipala、Daniel Jackson、John Guttag和Martin Rinard一起教授软件课程的经历，增强了我对软件工程和编程语言的了解。感谢能与这些优秀的同事共事。
感谢Victor Costan和Staphany Park为编程基础（Fundamentals of Programming）与算法导论（Introduction to Algorithms）这两门课开发的课程打分系统，这套系统非常美妙，使我能将更多时间投入课程的内容本身。
MIT出版社将本书的早期版本寄给了3位匿名的审校者。感谢他们仔细阅读书稿，并为改进本书提出了大量绝佳的建议。当然，也感谢他们的出版提议。希望他们读到本书时，能为我对他们有价值反馈的重视而感到高兴。
MIT一直都鼓励教师在学科建设之外，也要重视实验室管理和领导力。我要感谢Duane Boning、Anantha Chandrakasan、Agnes Chow、Bill Freeman、Denny Freeman、Eric Grimson、John Guttag、Harry Lee、Barbara Liskov、Silvio Micali、Rob Miller、Daniela Rus、Chris Terman、George Verghese和Victor Zue在这些年里对我的支持。
Marie Lufkin Lee、Christine Savage、Brian Buckley和Mikala Guyton为本书的审校、编辑、出版劳力颇多，感谢他们的工作。
我的太太Lochan给本书起了名字，我的女儿Sheela和Lalita是本书的首批“买家”，也帮助了本书的塑造。谨以本书献给她们3个人。
本书由异步社区出品，社区（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、测试、前端、网络技术等。
异步社区
微信服务号
本谜题涵盖的编程结构和算法范型：列表、元组、函数、控制流程（包含if语句和for循环）和print语句。
假设有一大群人排队等待观看棒球比赛。他们都是主场球迷，每个人都戴着队帽。但不是所有人都用同一种戴法，有些人正着戴，有些人反着戴。
人们对正戴和反戴的定义各不相同，但你认为图1-1中左边的帽子是正戴的，右边的帽子是反戴的。
图1-1
假定你是门卫，只能在全组球迷帽子戴法一致时才能让他们进入球场，要么全部正着戴，要么全部反着戴。因为每个人对帽子正反的理解不同，所以不能对他们说把帽子正着戴或反着戴。只能告诉他们转一下帽子。好消息是，球迷每个人都知道自己在队伍中的位置，第一个人的位置是0，最后一个人的位置是n − 1。这可以像下面这样表述。
位置i的人请转一下帽子。
位置i到j（包含j）的人请转一下帽子。
不过你想要尽量减少喊出要求的次数。举个例子，如图1-2所示。
图1-2
这是一个有13个人的队伍，位置从0到12。因为有6个人的帽子是正戴的，应该喊出6次命令。例如：
位置0的人请转一下帽子。
并对位置1、5、9、10和12的人重复相同的命令。采用第二种方式的命令可以减少说话次数，只需要喊出下面4次命令，就会让所有人的帽子都反戴。
位置0到1的人请转一下帽子。
位置5的人请转一下帽子。
位置9到10的人请转一下帽子。
位置12的人请转一下帽子。
但对这个例子而言，还能做得更好一些。如果喊出以下命令，会让所有人的帽子都变成正戴。
位置2到4的人请转一下帽子。
位置6到8的人请转一下帽子。
位置11的人请转一下帽子。
怎样才能让生成的命令数最少呢？难度更大的问题是，能否第一次沿着队伍走一遍就想出生成命令的方案？
在继续往下阅读以前，请思考一下上述问题。
假定有了对应于一组排队等待人员的帽子方向列表。可以计算出一个“区间”（interval）的列表，对应于各段戴帽方式相同的连续人群。区间可以用开始和结束位置来表示，如[a, b]（a ≤ b），这表示a和b之间所有位置的区间，包括a和b在内。
每个区间都标上是正戴区间还是反戴区间。所以一个区间有3个属性，即开始位置值、结束位置值、标明正戴或反戴的标记。
如何计算出区间的列表呢？有一个关键点就是，当看到帽子方向发生变化时，就是一个区间的结束和另一个区间的开始。当然，第一个区间的起始位置是0。下面再给出一次例子，如图1-3所示。
图1-3
这里位置0是正戴的。沿着列表遍历下去，位置1同样也是正戴的。但是位置2是反戴的，此时方向发生了反转。这意味着第一个区间已在前一个帽子处结束了。第一个区间是[0, 1]，方向是正戴的。不仅如此，这里还已确定第二个区间的开始位置为2。现在的状态与刚开始时完全相同，即已知当前区间的开始位置，需要找出其结束位置。
按这种方式继续下去，将会得到[0, 1]正戴，[2, 4]反戴，[5, 5]正戴，[6, 8]反戴，[9, 10]正戴，[11, 11]反戴，[12, 12]正戴。最后一个区间不是因为方向发生变化才结束的，而是因为后面没有人了。在代码中正确处理这种情况将是很重要的，这一点请留意！
本谜题的第一个算法会统计正戴区间和反戴区间的数量，然后根据哪一组区间数更少而选出其方向来反转帽子。上述例子中有4组正戴区间和3组反戴区间，所以应该要求3个反戴区间的人反转帽子。
在最坏的情况下，人们的帽子方向是正反交替的。假定有n个人，若n是偶数，则会有n/2个正戴区间和n/2个反戴区间。最坏情况下必须喊出n/2次命令。如果n是奇数，则正戴区间会比反戴区间多一个，或者反之。
通过将帽子方向相同的相邻人员归入一个区间中，该算法将他们归并在一起。区间确定之后，情况就与以上人员交替排列时完全相同了，将会有m个正戴区间散布在m、m − 1或m + 1个反戴区间之中。这里最多也就是选出生成命令较少的帽子方向。这个算法只能如此了。
在本书中，我们可以看到字符串、列表、元组、集合和字典，这些都是Python提供的数据结构。下面简单介绍这些数据结构可以用来做哪些操作。
字符表示单个符号，如'a'和'A'。字符串是字符的序列，如'Alice'，也可以是'B'这种单个字符。字符串可以表示为单引号形式或者双引号形式，如"A"和"Alice"。你可以访问字符串中的单个字符，例如s = "Alice"，s[0]可得'A'，且s[len(s)- 1] = 'e'。内置函数len能够返回参数字符串（或者列表）的长度，如len(s)返回5。字符串不能修改，如赋值语句s[0] = 'B'会导致错误。但是可以通过操作旧的字符串创建新的字符串。例如，给定s = 'Alice'，可以通过s = s + 'A'创建出一个由s引用的新字符串'AliceA'。
Python中的列表（list）可以理解为元素的序列或数组，它们可以包含数字、字符串或者其他列表。例如，设L = [1, 2, 'A', [3, 4]]，则L[0]得1，L[len(L) - 1]得[3，4]，L[3][0]返回3。列表可以修改，若执行L[3][1] = 5会将L变为 [1, 2, 'A', [3, 5]]。
元组和列表类似，但是不可修改。给定T = (1, 2, 'A', [3, 4])，则T[3] = [3, 5]会导致崩溃，但执行T[3][0] = 4能改变T中列表的元素而使T = (1, 2, 'A', [4, 4])。如果写成T = (1, 2, 'A', (3, 4))，则T[3][0] = 4会导致崩溃。
在后面的代码示例中，可以看到更多对字符串、列表和元组操作的应用。关于集合与字典，本书会在后面需要用到这类更高级的数据结构时再予以描述。
现在我们已准备就绪，可以展示第一种策略的代码。我们将代码分为两部分，在每段代码片段之后立刻解释这段代码的含义。在本书中显示的所有代码中，Python关键字或保留字都会以粗体显示，不要在编写的代码中使用这些单词作为变量或函数名称。
1. cap1 = ['F','F','B','B','B','F','B',
'B','B','F','F','B','F' ]
2. cap2 = ['F','F','B','B','B','F','B',
'B','B','F','F','F','F' ]第1～2行简单地列出输入列表。列表cap1对应前面漂亮的帽子图片中的示例。该列表是一个字符串的列表，其中每个字符串代表戴帽子的方向：正戴为'F'，反戴为'B'。Python允许跨行声明一个列表，通过闭合的[]表示列表的开始和结束位置。
3. def pleaseConform(caps):
4. start = forward = backward = 0
5. intervals = []
6. for i in range(1, len(caps)):
7. if caps[start] != caps[i]:
8. intervals.append((start, i - 1, caps[start]))
9. if caps[start] == 'F':
10． forward += 1
11． else:
12． backward += 1
13． start = i
14． intervals.append((start, len(caps) - 1, caps[start]))
15． if caps[start] == 'F':
16． forward += 1
17． else:
18． backward += 1
19． if forward < backward:
20． flip = 'F'
21． else:
22． flip = 'B'
23． for t in intervals:
24． if t[2] == flip:
25． print ('People in positions', t[0],
'through', t[1], 'flip your caps!')第3行代码为函数命名并列出函数的参数。def关键字用于定义函数，括在括号中的多个量是函数参数。该函数只取输入的列表作为函数参数，可以使用包括cap1和 cap2在内的任何列表来调用它。作为示例，我们稍后将展示执行pleaseConform (cap1)的结果。该函数假定输入参数是由字符串'F'和'B'组成的列表，列表的长度任意，但是不能为空。
第4～5行初始化算法中用到的变量。每个区间皆表示为一个三元组，其中前两个元素是数字，第三个元素是字符串标签'F'或者'B'。前两个数字给定了区间的端点，区间的两端都是闭合的，即区间包含两个端点。如前所述，元组和列表类似，但是与列表不同：元组一旦创建就不能修改。我们可以很容易在第8行换用：
intervals.append([start, i - 1, caps[start]])即用[]而非()括起3个变量，程序的执行不受影响。变量intervals表示区间元组的列表，初始化为空列表[]。变量forward和backward分别记录正戴区间和反戴区间的个数，都初始化为0。
第6～13行代码从for循环开始计算区间。len(cap1)会返回13。注意caps列表中的元素编号从0到12，如caps[0] = 'F'、caps[12] = 'F'（而访问caps[13]将会产生错误）。range关键字可以取1个、2个或者3个参数。如果使用range(len(caps))，那么变量i将会从0持续递增到len(caps) - 1为止。在第6行可见range(1, len(caps))，意思是变量i会从1迭代到len(caps) - 1，每次递增1，这种写法和range(1, len(caps), 1)效果相同。如果写成range(1, len(caps), 2)，那么每次迭代将使i递增2。
变量start对于区间的确定至关重要。最初start值为0，我们遍历所有的caps[i]，直至发现与caps[start]不同的caps[i]为止。这项检查由第7行中的if语句完成。如果if语句判断caps[start] != caps[i]为True，那么将在i处结束区间，并开启另一个新区间。这个区间以start开始，以i-1结束。一旦区间确定，这个区间就会以三元组的形式附加到intervals列表中，其中第一个元素是区间的起始位置，第二个元素是区间的结束位置，第三个元素是区间的类型（'F'或者'B'）。第9～12行递增相应正戴或者反戴区间的数量。第13行将start设置为i，因为我们要开启一段以i开始的新区间。
注意，缩进表明，第14行位于for循环之外。一旦for循环执行结束，你可能认为已经计算出了所有的区间。然而这是不正确的！最后一段区间尚未添加到intervals列表中。这是因为，只有我们意识到区间结束才会进行添加。当发现caps列表中的元素与caps[start]不同时就会添加。但是，这一点对最后一段区间不成立！例如，将cap1作为输入，当i = 12时，我们会看到'F'且start = 11，然后退出循环。类似地，对于cap2，当i = 12时，我们会看到'F'且start = 9，然后退出循环。因此必须在循环外添加最后的区间，我们在第14～18行中按与之前一样的方式进行这一操作。
第19～22行用于确定翻转正戴区间还是翻转反戴区间，按其中较小的集合为准。然后在第23～25行中循环区间列表。该for循环迭代intervals列表中的每个区间t，打印出所选区间类型对应的命令，区间类型为正戴或者反戴。每个t是一个描述每段区间信息的三元组，可用于有选择地打印并为每条命令生成开始位置和结束位置。对于元组t，t[0]指代开始，t[1]指代结束，t[2]指代类型。如果为t[0]、t[1]或t[2]设置任何值，会使程序崩溃，因为元组不可写入。若不希望无意中修改列表中元素的值，最好使用元组而不是列表。
第25行的print语句打印出指令。print语句能够打印出穿插着变量值的字符串。要打印的字符串和变量必须包含在()中[1]。请注意，为了良好的可读性，我们将print语句拆分为了两行，Python仍能够正确地解析print语句，因为它的参数都包含在()内。
每一个大型程序中，都有一个试图逃离掌控的小程序。
—— Tony Hoare
25行代码并非大型程序，但是编程算法谜题的美妙之处就在于，优化代码通常能够起到缩短代码的作用。较短的程序通常更高效且错误更少，当然，这并非一条严格的定律。
我们已有一种与列表末尾相关的特殊情况，在第14～18行中添加了最后一个区间。这是因为只有遇到与caps[start]不同的元素时才添加区间。为了避免这种特殊情况，我们要做的只是在第5行和第6行之间引入一句声明，也就是：
5a. caps = caps + ['END']并简单地删除第14～18行代码。上面的语句在caps列表中添加了一项与其他元素都不相同的元素。运算符 + 可以用于连接两个列表，生成连接后的新列表。这就是为什么我们需要在'END'两边括上[]：因为运算符 + 只能操作两个列表、两个字符串或者两个数字，不能操作一个列表和一个字符串，或者一个字符串和一个数字。添加一个元素意味着我们的循环会增加一轮迭代，在最后一轮迭代中，无论caps[start]是'F'还是'B'，caps[start]!= caps[i]的结果都为真，这样最后一段区间就会被添加到列表中去。
最后，这一优化还有一个很好的副产品，即优化后的程序不再像原始程序那样在输入空列表时发生崩溃。
我们可以在第5a行通过caps.append('END')将新的字符串元素添加到列表caps中。但是这样做会修改参数列表caps，有时候这是我们应当避免的做法。假设运行下面两段不同的程序：
1． def listConcatenate(caps)：
2． caps = caps + ['END']
3． print(caps)
4． capA = ['F','F','B']
5． listConcatenate(capA)
6． print(capA)
和
1． def listAppend(caps):
2． caps.append('END')
3． print(caps)
4． capA = ['F','F','B']
5． listAppend(capA)
6． print(capA)第一段程序会先打印['F','F','B','END']，然后打印['F','F','B']。第二段程序会打印 ['F','F','B','END']两次。在第一段程序中，通过列表连接运算符 +创建了一个新的列表，但是第二段程序中的append修改了现有列表。因此，在使用append的情况下，过程调用外的capA变量已经被修改。
如果将capA替换为caps，两段程序的行为将完全一样。我们看一下第一段程序中将capA替换为caps的情况。
1． def listConcatenate(caps):
2． caps = caps + ['END']
3． print(caps)
4． caps = ['F','F','B']
5． listConcatenate(caps)
6． print(caps)这个程序会先打印['F','F','B','END']，然后打印['F','F','B']。在过程listConcatenate之外的变量caps和函数内的参数caps的作用域不同。参数caps会指向一个新的列表，执行列表连接之后['F','F','B','END']会位于不同的内存，因为列表连接创建了这段新的内存，并将列表的元素复制到其中。过程执行完毕后，参数caps和新的列表消失，不能再被访问。过程之外的变量caps仍然指向原始内存位置的列表['F','F','B']，此位置的列表未被修改。
现在看一下使用append的情况。
1． def listAppend(caps):
2． caps.append('END')
3． print(caps)
4． caps = ['F','F','B']
5． listAppend(caps)
6． print(caps)作用域的规则也同样适用于这里。参数caps最初指向单个列表['F', 'F', 'B']，append将此列表修改为['F', 'F', 'B', 'END']。因此，即使在过程执行完毕且参数变量caps消失之后，内存位置也已经使用附加的元素'END'进行了修改。我们即使在过程之外也能看到这种效果，因为过程之外的变量caps和过程内的变量caps指向相同的内存地址。
如果这段描述令你感到头疼，请为参数变量和外部传递给过程调用的变量采用不同的命名。
现在看一个更难的问题：怎样在沿队伍走第一遍时，便能确认出最小数量的命令集。
这里有一个提示：正戴区间与反戴区间的数量最多相差1。观察第一个人的具体方向，若正戴，则正戴区间的数量将永远不会小于反戴区间的数量。类似地，如果第一个人是反戴的，那么反戴区间的数量将永远不会小于正戴区间的数量。
我们第一个算法为两次遍历，因为它首先通过遍历列表来确定正戴区间和反戴区间（第一遍），然后遍历区间以打印出适当的命令（第二遍）。
你能想到一个算法，可以单次遍历列表来生成最小数量的命令集吗？你的算法应使用单个循环实现。
通过列表中第一只帽子的方向，可以得出是正戴区间还是反戴区间对应最小数量的命令集。我们基于这一观察，能够实现一个单遍（one-pass）算法，代码如下：
1． def pleaseConformOnepass(caps):
2． caps = caps + [caps[0]]
3． for i in range(1, len(caps)):
4． if caps[i] != caps[i - 1]:
5． if caps[i] != caps[0]：
6． print('People in positions', i, end = '')
7． else:
8． print(' through', i - 1, ' flip your caps!')代码第2行向列表追加了一个元素，但它添加的并非最后一个元素，而与第一个元素相同。在循环迭代期间，当第一次遇到和第一个元素不同的元素时（第4行），我们开启一段新区间。这意味着我们实际上会跳过第一段区间。这样做是可行的，因为根据观察，第一段区间对应的方向并非唯一最适于作为生成命令的方向——它至多可用于根据所需要的指令数确定相反方向。当遇到与第一个元素相同的元素时（第7行），结束该区间。代码在构造区间的同时打印出指令。在列表的尾部添加额外的元素，使之与首个元素相等（第2行），能确保当原始列表的最后一个元素与caps[0]不同时，打印出最后一个区间。
这段代码的缺点是它不像原始代码那样易于修改，较难在此基础上修改用于解决本谜题末尾的习题。这段代码也还需要改进，以避免在输入空列表时崩溃。
这道谜题背后的出发点是压缩。向同一方向的人发出的命令信息是相同的，可以被压缩为一组较少的命令，其中每条命令指挥一组连续的人。
数据压缩是非常重要的应用程序，并且伴随着因特网上产生的大量数据而变得更加重要。无损的数据压缩有多种实现方式，在思路上接近这道谜题的一种算法叫作游程编码（run-length encoding）。举一个简单的例子最容易描述，假设有一个字母构成的字符串，包含32个字符：
WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB使用一种简单的算法，我们可以将其压缩为一个由字母和数字构成的字符串，包含10个字符：
13W2B12W5B在上面的字符串中，每个字母字符前缀有一个数字，用于表示该字符在原始字符串中连续出现的次数。原始字符串中首先有13个W，然后是2个B，然后是12个W，最后是5个B，我们在压缩后的字符串中直接展示了这部分信息。
游程解码是指将13W2B12W5B解压为原始字符串的过程。
虽然在第一个例子中压缩效果显著，但是假设有像下面这样的一个字符串：
WBWBWBWBWB我们的游程编码方案将天真地产生一个更长的字符串，如下：
1W1B1W1B1W1B1W1B1W1B而更智能的算法可能会生成像下面这样的内容：
5(WB)()可以理解为将重复序列括起。现代计算机中可用的压缩工具，便是利用了与这种思路相关的算法。
习题1 执行pleaseConform(cap1)所打印的结果有点儿令人烦恼：
People in positions 2 through 4 flip your caps!
People in positions 6 through 8 flip your caps!
People in positions 11 through 11 flip your caps!最后一条命令应该打印如下：
Person at position 11 flip your cap!修改代码使命令听起来更自然一些。
习题2 修改pleaseConformOnepass，如习题1那样打印更自然一些的命令，并确保程序在输入是空列表时不会崩溃。
提示：你需要记住区间的起始位置（而不是在第6行打印）。
难题 3 假设在队伍中存在没戴帽子的人。我们用字符'H'代表他们。例如，有这样一组数据：
cap3 = ['F','F','B','H','B','F','B',
'B','B','F','H','F','F']我们不想指示没戴帽子的人去转动不存在的帽子，这令人困惑，可能会导致有人试图从队伍前面的人那里偷帽子。因此我们希望跳过所有'H'位置。修改pleaseConform，使它生成正确并且最小数量的命令集合。对于上面的例子，它应当生成：
Person in position 2 flip your cap!
Person in position 4 flip your cap!
People in positions 6 through 8 flip your caps!习题4 写一段程序实现简单的游程编码，将给定字符串（如BWWWWWBWWWW）转换为较短的字符串（1B5W1B4W），并且执行游程解码，将压缩过的字符串转换回原始字符串。你只能通过一次字符串遍历来执行压缩和解压缩过程。
str函数能将数字转换成字符串，例如 str(12) = '12'。它在编码步骤中会很有用。
int函数能将字符串转换成数字，例如：int('12') = 12。对于任意字符串s，如果字符s[i]是字母字符，则s[i].isalpha()将返回True，否则返回False。如果s中所有的字符都是字母字符，则s.isalpha()返回True，否则返回False。函数int和isalpha在解码步骤中会很有用。
[1] 在Python 3.x中，无论`print`语句是否分跨两行，`()`都是必需的；而在Python 2.x中，`()`只在`print`语句分跨两行或多行时才是必需的。
本谜题涵盖的程序结构和算法范型：元组、元组列表、嵌套for循环和浮点数、列表切片、排序。
你在办公室抽奖中赢得了一张名人派对的门票。因为参加的人很多，所以每个人只能待一个小时。但是因为你拥有一张特等票，所以你可以选择出席的时间。你有一张时间表，上面准确地列有每位名人出席派对的时间，你希望与尽可能多的名人合影来提高你的社会地位。这意味着你需要在特定的某个时段出席派对，这样你可以和最多的名人交谈，并获得与他们每个人的自拍。
我们得到一组区间的列表，对应于每位名人出席、离开的时间。假设区间是[i, j]，其中i和j对应小时，区间为左闭右开区间。这意味着名人会在i点出席派对，但在j点开始时离开。因此即使你第j点准点到达，也会错过这位名人。
表2-1给出的是一个例子。
表2-1
| 名 人 |
出 席 时 间 |
离 开 时 间 |
|---|---|---|
| Beyoncé |
6点 |
7点 |
| Taylor |
7点 |
9点 |
| Brad |
10点 |
11点 |
| Katy |
10点 |
12点 |
| Tom |
8点 |
10点 |
| Drake |
9点 |
11点 |
| Alicia |
6点 |
8点 |
参加派对的最佳时间是几点？或者说，你应在哪个时间参加派对？
通过查看每个小时并计算名人的数量，你可能发现如果在10点到11点之间参加，将得到与Brad、Katy和Drake的自拍。没有比得到3张自拍更好的了。
这段简单的算法查看每一小时，检查每一小时内有几位名人在场。一位在区间
[i, j)内在场的名人，会在i, i + 1, …, j − 1点内在场。算法简单计算每个小时内名人的数量，并选出最大值。
下面是算法的代码：
1. sched = [(6, 8), (6, 12), (6, 7), (7, 8),
(7, 10), (8, 9), (8, 10), (9, 12),
(9, 10), (10, 11), (10, 12), (11, 12)]
2. def bestTimeToParty(schedule):
3. start = schedule[0][0]
4. end = schedule[0][1]
5. for c in schedule:
6. start = min(c[0], start)
7. end = max(c[1], end)
8. count = celebrityDensity(schedule, start, end)
9. maxcount = 0
10． for i in range(start, end + 1):
11． if count[i] > maxcount:
12． maxcount = count[i]
13． time = i
14． print ('Best time to attend the party is at',
time, 'o\'clock', ':', maxcount,
'celebrities will be attending!')算法的输入是一个时间表，也就是一组区间的列表。每段区间是一个二元组，其中的两个元素都是数字。第一个元素是开始时间，第二个元素是结束时间。该算法不能修改这些区间，因此用元组来表示。
第3～7行代码确定名人出席派对的最早时间与最晚时间。代码第3行和第4行假定schedule中至少有一个元组，用该元组初始化变量start和end。我们希望变量start表示每位名人最早开始时间，变量end表示每位名人的最晚结束时间。schedule[0]给出schedule的第一个元组。访问这个元组的两个元素的方式和访问列表中的元素完全相同。由于schedule[0]为元组，我们需要另外一个[0]用于访问元组的第一个元素（第3行代码），[1]用于访问元组的第二个元素（第4行代码）。
在for循环中会遍历列表中的所有元组，将其中的每个元组命名为c。注意，如果我们将c[0]修改为10（例如），程序会抛出错误，因为c是元组。另一方面，如果声明sched = [[6, 8], [6, 12], ...]，我们便可以将6改为10（例如），因为sched中的每个元素都是列表。
第8行代码调用一个函数，填充列表count，用于表示start和end时间范围内每一小时内在场的名人数量。
第9～13行代码用于找出最大的名人数量出席的时段，循环start到end时间范围内的各个小时，通过变量maxcount跟踪最大的名人数量。这些代码可以替换为：
9a. maxcount = max(count[start:end + 1])
10a. time = count.index(maxcount)Python提供了一个函数max可用于查找列表中的最大元素。此外，我们可以使用切片（slice）来选取列表中一段特定连续范围内的元素。在第9a行中，我们找到索引start和end之间（包含end）的最大元素。如果有b = a[0:3]，意思是将a的前3个元素（即a[0]、a[1]、a[2]）复制到列表b中，其长度为3。第10a行确定最大元素的索引。
下面是算法的核心内容，实现在函数celebrityDensity中：
1． def celebrityDensity(sched, start, end):
2． count = [0] * (end + 1)
3． for i in range(start, end + 1):
4． count[i] = 0
5． for c in sched:
6． if c[0] <= i and c[1] > i:
7． count[i] += 1
8． return count这一函数包含一个嵌套循环。外层循环从range的第一个参数start指定的时间开始，遍历不同的时间，每次迭代后将时间i递增1。内层循环（第5～7行）遍历所有的名人，第6行代码检查当前名人当前时间是否在场。如前所述，时间必须要大于等于名人的开始时间且小于结束时间。
如果运行语句
bestTimeToParty(sched)代码将打印
Best time to attend the party is at 9 o'clock : 5 celebrities
will be attending!这一算法看起来似乎很合理，但是有一点不能令人满意。时间单位是什么？在我们的例子中，可以假设6代表下午6点，11代表下午11点，12代表上午12点，这意味着时间的单位是1小时。但是如果名人像他们习惯的那样，在任意时间来去将会怎么样呢？例如，假设Beyoncé在6:31到场并在6:42离开，Taylor在6:55到场并在7:14离开。我们可以将时间单位设为1分钟而非1小时。这意味着在第6行循环中要执行60次检查。如果碧昂丝（Beyoncé）选择在6:31:15到场，我们就该要检查每一秒。名人到达和离开的时间单位也可能在毫秒级（好吧，即使是Beyoncé，这也很难做到）！时间单位不得不做出选择，很烦人。
你能想出一个不需要依赖时间精度的算法吗？这一算法应该利用大量只与名人的数量相关而与他们的日程安排无关的操作。
我们绘图表示所有名人的区间，以时间为横轴。图2-1是一种可能的名人日程表。
图2-1
这张图片耐人回味—— 它告诉我们，如果在特定时间拿一把“标尺”（如图2-1中的虚线所示），就可以计量与标尺相交的名人时间区间个数，从而得知这时可以见面的名人数量。在前面的简单算法中，我们早已得知名人数量，也编写了相关代码。但是可以从图中额外观察到以下两点。
（1）我们只需要关心名人时间区间的起点和终点，因为只有这些时刻在场名人数量才会发生变化。没有必要计算第二条虚线时间在场的名人数量——它和第一条虚线完全相同，因为在第一条和第二条虚线或时间范围内，没有新的名人到达或者离开（回忆一下，第4位名人——从上往下数第4条线——在第一条虚线对应的时间便已到达派对现场了）。
（2）我们可以将标尺从左侧向右侧移动，通过增量计算找出名人数量最多的时间，这一点将在下面详述。
我们保存名人的计数，初始为零。每当看到名人时间区间的开始时间，便递增这个计数，每当看到名人时间区间的结束时间，便递减这个计数。我们同时也跟踪最大的名人数量。名人数量在名人时间区间的开始和结束时发生变化，而最大的名人数仅在名人时间区间的开始时间发生变化。
这里有一个关键点，我们必须随着时间的增加来执行这一计算，从而模拟标尺从左往右移动。这意味着必须对名人日程表的开始时间和结束时间进行排序。我们在上面的图片中，想首先看出第二位名人的开始时间，然后是第三位名人的开始时间，再是第一位名人的开始时间，依此类推。我们稍后会操心怎样对这些时间进行排序，但现在先来看看如下代码，这段代码会以更高效和优雅的方式来发现参加派对的最佳时间。
1． sched2 = [(6.0, 8.0), (6.5, 12.0), (6.5, 7.0),
(7.0, 8.0), (7.5, 10.0), (8.0, 9.0),
(8.0, 10.0), (9.0, 12.0), (9.5, 10.0),
(10.0, 11.0), (10.0, 12.0), (11.0, 12.0)]
2． def bestTimeToPartySmart(schedule):
3． times = []
4． for c in schedule:
5． times.append((c[0], 'start'))
6． times.append((c[1], 'end'))
7． sortList(times)
8． maxcount, time = chooseTime(times)
9． print ('Best time to attend the party is at',
time, 'o\'clock', ':', maxcount,
'celebrities will be attending!')注意，schedule和sched2是二元组的列表，如前所述，每个元组的第一个元素是开始时间，第二个元素是结束时间。但是在sched2中用浮点数而非在schedule中用整数来表示时间。6.0、8.0等数字都是浮点数。在这道谜题中，我们仅比较这些数字，没有必要对它们执行其他算术操作。
另一方面，在第3行被初始化为空的列表times是二元组的列表，每个元组的第一个元素是时间，第二个元素是用来指示时间是开始时间还是结束时间的字符串标记。
第3～6行代码收集所有名人的开始时间和结束时间，每次都做这样的标记。列表未经排序，因为我们不能假定参数schedule曾按任何方式排过序。
第7行代码通过调用一个排序过程对列表进行排序，稍后我们会介绍这个排序过程。一旦列表经过排序，第8行代码会调用关键的过程chooseTime，用以执行增量计算来确定各个时间段内名人的数量（密度）。
这段代码将会按与打印原始时间表sched相同的方式，打印出sched2：
Best time to attend the party is at 9.5 o'clock : 5 celebrities
will be attending!按时间进行排序怎么样？我们有一组区间列表，需要将其转换为按'start'和'end'进行标记的时间列表。接着按时间升序进行排序，并保留这些与时间关联的标签。下面是执行相关操作的代码：
1． def sortList(tlist):
2． for ind in range(len(tlist) - 1):
3． iSm = ind
4． for i in range(ind, len(tlist)):
5． if tlist[iSm][0] > tlist[i][0]:
6． iSm = i
7． tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind]这段代码是如何工作的？它对应于可能是最简单的排序算法——选择排序[1]。该算法找到最小的时间，并在外层for循环的第一次迭代之后（第2～7行），将其放在列表的起始位置。对最小值的搜索需要len(tlist) - 1次计算而非len(tlist)次计算，因为我们在仅剩一个元素时不需要仍找寻最小值。
寻找最小元素需要遍历列表的所有元素，执行于内层for循环（第4～6行）。因为列表起始位置已经有元素存在，该元素需要保留在列表中的其他某位置，所以算法在第7行代码将两个元素交换。可将第7行代码理解为并行发生的两次赋值：tlist[ind]获取tlist[iSm]的旧值，tlist[iSm]获取tlist[ind]的旧值。
在外层for循环的第二轮迭代中，算法查看列表中的其余条目（不包含第一个条目），找出最小值，通过在迭代中将最小值与当前第二位的元素交换，将最小值作为第一个条目后的第二个条目放置。注意，第4行代码range有两个参数，确保在外层循环的每次迭代中，内层循环都以ind开始，这样可以确保索引小于ind的元素都保持在正确的位置。这一过程持续到列表中所有的元素完成排序为止。因为参数列表中每个元素都是一个二元组，我们必须在第5行的比较中使用二元组第一项的时间值，这便是我们在第5行中使用额外的[0]的原因。当然，我们是在对二元组进行排序，第7行代码交换的是二元组，'start'和'end'标签依然附着在原来的时间上。
一旦列表完成排序，过程chooseTime（如下所示）会通过单次遍历列表确定最佳时间和该时间的名人数量。
1. def chooseTime(times):
2. rcount = 0
3. maxcount = time = 0
4. for t in times:
5. if t[1] == 'start':
6. rcount = rcount + 1
7. elif t[1] == 'end':
8. rcount = rcount - 1
9. if rcount > maxcount:
10． maxcount = rcount
11． time = t[0]
12． return maxcount, time迭代次数是名人数量的两倍，因为列表times中有两个条目（每个都是二元组），分别对应每位名人的开始时间和结束时间。将该算法和前面双层嵌套循环的简单算法进行比较，简单的算法的迭代次数等于名人的数量乘以小时数（或者根据具体情况为分钟数或秒数）。
注意，参加派对的最佳时间往往和某些名人到达派对的开始时间相对应，这是由于rcount仅在这些开始时间递增，因而在这些时间之一达到峰值。我们将在习题2中利用这一观察结果。
为更有效地处理列表而对其进行排序，是一种基本的技巧。假设我们有两个单词列表，想要检查它们是否相等。假设每个列表都没有重复的单词，并且他们的长度相同，都有n个单词。明显的方法是获取列表1中的每个单词，检查是否存在于列表2中。最坏的情况下需要n2次比较，因为每个单词在检查成功或者失败之前都需要比较n次。
更好的方法是按照字母顺序将两个列表中的单词排序。一旦它们经过排序，我们便可以简单地检查有序列表1中的第一个单词是否等于有序列表2中的第一个单词，有序列表1中的第二个单词是否等于有序列表2中的第二个单词，依次类推。这种方式只需要比较n次。
那么，你说，排序所需的操作次数是多少呢？选择排序过程在最坏的情况下不是需要n2次比较吗？这里正在对两个列表做排序。请关注更好的排序算法，我们将在本书后面介绍在最坏情况下只需要n log n次比较的排序算法。对于较大的n值，n log n会比n2小得多，这使在比较相等性之前进行排序是非常值得的。
习题1 假设你是一位非常忙碌的名人，并不能自由选择参加派对的时间。对过程增加参数并修改，使它能够在给定的时间范围ystart和yend内，确定能见到最多多少位名人。与名人一样，你的时间区间为 [ystart,yend)，表示你会在任意满足ystart≤t＜yend 的时间t时在场。
习题2 有另一种方法，可以不依赖时间精度来计算参加派对的最佳时间。我们依次选择每位名人的时间区间，并确定有多少其他名人的时间区间包含所选名人的开始时间。我们选择出某位名人，使他的开始时间被最大数量的其他名人时间区间所包含，并将他的开始时间作为参加派对的时间。编写代码实现该算法，并验证它的结果与基于排序算法的结果是否相同。
难题3 假设每位名人都有一个权重，取决于你对这位名人的喜爱程度。可以在时间表中将其表示为一个三元组，如(6.0, 8.0, 3)。开始时间是6.0，结束时间是8.0，权重是3。修改代码，找出最大化名人总权重的时间。例如，给定图2-2，我们想要返回与右侧虚线对应的时间，即使当时只有两位名人。
图2-2
因为这两位名人对应的权重为4，大于第一条虚线时在场的3位名人对应的权重3。
下面是一个更复杂的例子：
sched3 = [(6.0, 8.0, 2), (6.5, 12.0, 1), (6.5, 7.0, 2),
(7.0, 8.0, 2), (7.5, 10.0, 3), (8.0, 9.0, 2),
(8.0, 10.0, 1), (9.0, 12.0, 2),
(9.5, 10.0, 4), (10.0, 11.0, 2),
(10.0, 12.0, 3), (11.0, 12.0, 7)]根据名人的日程安排，你想要在11点参加派对，此时参加派对名人权重之和是13，为最大值。
[1] 不一定是最高效的算法，但最容易编写与理解。在谜题11与谜题13中，我们将会见到更好的排序算法。
