书名：计算机科学概论（Python版）
ISBN：978-7-115-53554-2
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [美] 克里斯汀·阿尔瓦拉多（Christine Alvarado）
[美] 扎卡里·道兹（Zachary Dodds）
[美] 吉奥夫·昆宁（Geoff Kuenning）
[美] 兰·列别斯科（Ran Libesk）
译 王海鹏
责任编辑 陈冀康
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
Simplified Chinese translation copyright © 2020 by Posts and Telecommunications Press Co. Ltd ALL RIGHTS RESERVED
CS for All: An Introduction to Computer Science Using Python, by Christine Alvarado, Zachary Dodds, Geoff Kuenning and Ran Libeskind-Hadas.
Copyright © 2020 Franklin, Beedle & Associates Incorporated.
本书中文简体版由Franklin, Beedle & Associates公司授权人民邮电出版社有限公司出版。未经出版者书面许可，对本书的任何部分不得以任何方式或任何手段复制和传播。
版权所有，侵权必究。
本书是美国哈维玛德学院 “计算机科学通识”课程的配套教材，用独特的方法介绍计算机科学，带领读者进入这一充满智慧和活力的知识领域。
全书共7章。第1章介绍计算机科学的概念，引入了用于控制虚拟的“Picobot”机器人的一种简单的编程语言；第2章和第3章介绍Python编程语言，并且结合Python介绍了函数式编程的思想和概念；第4章深入计算机的内部工作原理，从数字逻辑到机器组织，再到用机器语言编程；第5章探讨计算中更复杂的思想，同时探讨诸如引用和可变性等概念，以及包括循环在内的构造、数组和字典；第6章探讨面向对象编程和设计中的一些关键思想；第7章针对问题解决，在计算复杂性和可计算性方面，提供了一些优雅的，但数学上非常合理的处理方法，最终证明了计算机上无法解决的许多计算问题。
本书适合想要通过Python编程来系统学习和了解计算机科学的读者阅读，也可以作为高等院校计算机相关专业的教学参考书。
欢迎你阅读本书！本书采用了独特的方法介绍计算机科学。简而言之，我们的目标是将计算机科学作为一个智慧丰富和充满活力的领域，而不是专注于计算机编程。虽然编程肯定是我们的方法中一个重要且普遍的元素，但我们强调概念和解决问题，而不是语法和编程语言特性。
本书是美国哈维玛德学院“计算机科学通识”课程的配套教材，随后在美国许多学院和大学中被采用。在哈维玛德学院，几乎每个一年级学生都会学习这门课程（不论学生的最终专业是什么），它是学院核心课程的一部分。我们的教材也被克莱蒙特学院联盟的许多学校采用，包括主修人文科学、社会科学和艺术的学生都在使用。因此，这是学生的第一门计算课程，无论他们的专业是什么。
从第1章开始，本书强调解决问题和重要思想的特点就很明确。我们在第1章中描述了一种非常简单的编程语言，用于控制虚拟的“Picobot”机器人。读者花十分钟就可以掌握其语法，但这里提出的计算问题是深刻而有趣的。
本书的其余部分遵循了同样的思路。我们使用Python语言，因为它的语法简单，并且有一套丰富的工具和软件包，让新手程序员能够编写有用的程序。在第2章中，我们对使用Python进行编程的介绍仅限于该语言语法的有限子集，这体现了函数式编程语言的精神。通过这种方式，读者很早就掌握了递归，并意识到他们可以用极少的代码编写有趣的程序。
第3章在函数式编程上更进一步，介绍了高阶函数的概念。第4章关注一个问题：“我的计算机如何做到这一切？”我们研究了计算机的内部工作原理，从数字逻辑到计算机组织，再到用机器语言编程。
既然已经揭开了计算机的“神秘面纱”，读者也看到了“幕后”发生的事情的物理表示，于是我们在第5章中继续探讨了计算中更复杂的思想，同时探讨了诸如引用和可变性等概念，以及包括循环在内的构造、数组和字典。我们利用第4章介绍的计算机物理模型来解释这些概念和结构。根据我们的经验，如果读者建立了底层的物理模型，就更容易理解这些概念。所有这些都是在读者熟悉的场景下完成的，这就是一个推荐程序，就像在线购物中使用的那种。
内容新！有改进！有许多“边缘的”有用注释！
在第6章中，我们探讨了面向对象编程和设计中的一些关键思想。这里的目标不是培养专业级的程序员，而是解释面向对象范式的基本原理，并让读者了解一些关键概念。最后，在第7章中，我们研究了问题的“难度”——在计算复杂性和可计算性方面，提供了一些优雅的，但数学上非常合理的处理方法，最终证明了计算机上无法解决的许多计算问题。我们使用Python作为模型，而不是使用形式化的计算模型（如图灵机）。
本书意在与我们为课程开发的大量资源一起使用，这些资源可从网站https://www.cs. hmc.edu/csforall上获得。这些资源包括完整的授课PPT、丰富的每周作业集、一些附带的软件和文档，以及关于该课程已发表的论文。
我们有意让这本书的篇幅相对较短，并努力让它变得有趣、可读性好。本书准确地反映了课程的内容，而不是一本不可能在一个学期学完的、令人望而生畏的百科全书。我们编写这本书时相信，读者可以随着课程的进行而舒适地阅读所有内容。
祝各位读者阅读愉快、计算愉快！
作者非常感谢美国国家科学基金会，通过CPATH 0939149的资助，为本课程的开发提供了方方面面的支持。多年来，这本书从许多学生和教师的反馈中不断得到改善。巴克内尔大学的Dan Hyde教授提供的详细建议，为本书带来了大量改进。此外，巴克内尔大学的Richard Zaccone教授、史蒂文斯理工学院的David Naumann教授和Dan Duchamp教授、波士顿大学的Dave Sullivan博士、Eran Segev先生以及几位匿名的审稿人提供了许多宝贵的意见和建议。Chris Butler、Nic Dodds、Ciante Jones和Dylan McGarvey帮助完成了许多最终的制作任务。
最后，感谢Franklin Beedle出版社的Jaron Ayres、Brenda Jones和Tom Sumner的团队，他们凭着良好的判断力出版了这本书，热情地、耐心地支持我们完成了这次“探险”。
我们努力做到准确和正确。本文中的所有错误完全由作者负责。
Christine Alvarado (UC San Diego)
Zachary Dodds (Harvey Mudd College)
Geoff Kuenning (Harvey Mudd College)
Ran Libeskind-Hadas (Harvey Mudd 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、测试、前端、网络技术等。
异步社区
微信服务号
计算机科学对于信息革命，就像是机械工程对于工业革命。
——Robert Keller
你可能不确定计算机科学（Computer Science，CS）是什么，但你每天都在使用它。当你使用Google或智能手机，或观看有特效的电影时，其中有很多CS的功劳。当你通过互联网订购产品时，网站也包含了CS，用加密的方式来保证你的信用卡安全，而且联邦快递也利用CS规划其送货车辆，以便尽快将你的订单送达。尽管如此，就算是计算机科学家也很难回答这个问题：“究竟什么是CS？”
许多其他科学试图理解事物的运作方式：物理学试图理解物理世界，化学试图理解物质的组成，生物学试图理解生命。那么计算机科学试图理解什么呢？计算机？可能不是——计算机是由人类设计和建造的，因此它们的内部运作方式是已知的（至少对某些人来说是这样！）。
也许它就是研究编程。编程对于计算机科学家来说确实很重要，正如语法对于作者很重要，或望远镜对于天文学家很重要。但是没有人会认为写作就是研究语法，或者天文学就是研究望远镜。同样，编程是计算机科学的一个重要部分，但它不是计算机科学的全部。
如果我们转向源头，计算机科学起源于不同的领域，其中包括工程、数学和认知科学等。一些计算机科学家设计事物，就像工程师一样。另一些科学家寻求解决计算问题的新方法，分析他们的解决方案，并证明他们是正确的，就像数学家一样。还有一些科学家思考人类如何与计算机和软件进行交互，这与认知科学和心理学密切相关。所有这些都是计算机科学的一部分。
所有计算机科学家（几乎）有一个统一的主题，即他们对从人工智能到动物进化的“任务的自动化”感兴趣。换句话说，计算机科学家有兴趣为各种各样的计算问题寻找解决方案。他们分析这些解决方案，以确定其有效性和效率，并实现良好的解决方案，为人们创造有用的软件。这种多样化的工作方向，也是CS如此有趣的部分原因。
动物进化是指特定动物物种的起源。计算生物学是利用CS来帮助解决动物进化问题的领域。
计算机科学的核心有几个重要的概念，我们选择强调其中6个概念：数据、算法、编程、抽象、解决问题和创造力。
在2018年初，如果你用Google搜索“pie recipe”（派的菜谱），Google会报告大约600万页，并按估计的相关性和实用性排序。Facebook拥有超过20亿活跃用户，每天产生数十亿次评论和点赞。GenBank是生物学家和研究遗传疾病的医学研究人员使用的DNA序列的国家数据库，拥有超过2亿个基因序列，拥有超过2000亿个DNA碱基对。国际数据公司（International Data Corporation）估计，数字世界包含16ZB的数据。按数字电影中使用的超高清视频来算，这相当于大约1600万年的视频。
那是天文数字！
没有计算机科学，所有这些数据都将是“垃圾”。如果没有计算机科学的思想和工具，在Google上搜索菜谱、在Facebook上搜索朋友或在GenBank上搜索基因都是不可能的。
即使我们没有处理数百万或数十亿的事物，使用数据做有意义的事情也很有挑战性。在本书中，我们将利用较小的数据集来做有趣的事情。但我们所做的很多事情也适用于非常大量的数据。
出现计算问题时，我们的第一个目标是找到一个计算解决方案或算法来解决它。算法是执行任务的精确步骤，例如，在Google上对网页进行排名、在Facebook上搜索朋友，或在GenBank上查找密切相关的基因。在某些情况下，一个好的算法足以创建一个成功的公司（例如，谷歌最初的成功归功于它的PageRank算法）。
算法常常被类比为菜谱，对其成分（数据）进行操作。例如，想象一个外星人从一个遥远的星球来到地球，渴望得到某种南瓜派。这个外星人在Google上搜索南瓜派，发现了以下内容。
1．在一个小碗中，混合3/4杯糖、1茶匙肉桂、1/2茶匙盐、1/2茶匙生姜和1/4茶匙丁香。
2．在一个大碗中打2个鸡蛋。
3．将115OZ（1OZ≈28.35g）的罐头装南瓜和步骤1中的混合物放入鸡蛋中搅拌。
我来地球是为了南瓜派！
4．在混合物中逐渐加入112OZ罐头装炼乳并搅拌。
5．将混合物倒入未烘烤的9in（1in=25.4mm）的南瓜派面托中。
6．将烤箱温度调至约218.3℃烘烤15min。
7．将烤箱温度降至约176.6℃。
8．烘烤30～40min，或直到定型。
9．在金属网架上冷却2h。
不！不要舔勺子——有生鸡蛋！
假设我们知道如何执行基本的烹饪步骤（测量成分、打鸡蛋、搅拌、舔勺子等）。通过精确地遵循这些步骤，我们可以制作美味的南瓜派。
出于对美食的尊重，计算机科学家很少编写与食物有关的菜谱（算法）。作为计算机科学家，我们更有可能编写一种算法来计算π，而不是编写算法来制作南瓜派。让我们考虑这样一个算法。
1．画一个2 feet×2feet（1feet=304.8mm）的正方形。
2．在这个正方形内画一个半径为1feet（直径为2feet）的圆。
3．拿一桶（n支）飞镖，远离镖靶，然后戴上眼罩。
4．每次取一支飞镖，对于每支飞镖：
请勿在家尝试！
a．在你的眼睛被蒙住的情况下，随机投掷飞镖（但假设你的投掷技术确保它会落在镖靶的某个地方）；
b．记录飞镖是否落在圆内。
5．当你投掷完所有飞镖时，将落入圆内的次数除以投掷的飞镖总数n，并乘以4。这将给出你对π的估计。
图1.1展示了这种场景。
嗨！小心点！那个飞镖差点打到我！
图1.1 利用镖靶近似求π
这是算法的描述，但为什么它有效？下面就是原因。圆的面积是πr2，在这种情况下是π，因为我们将镖靶的半径设为1。正方形的面积是4。因为我们假设飞镖可能落在正方形的任何地方，所以预期它们落在圆内的次数正比于圆与正方形的面积之比（π/4）。如果我们投掷n支飞镖，并确定落在圆内的次数为某个数字k，那么k/n应该约为π/4。因此，将该比率乘以4可得出π的近似值。
令人高兴的是，计算机不需要投掷实物飞镖。作为替代，我们可以生成描述飞镖落地位置的随机坐标，从而模拟这种投掷飞镖的过程。计算机可以在几分之一秒内投掷数百万支虚拟飞镖，且永远不会投掷在正方形之外——让你的室友更安全！
虽然我们之前曾指出，计算机科学并不仅仅是研究编程，但最终我们通常希望有一个程序（即软件），实现对数据进行操作的算法。
学习编程有点像学习说新语言，或用新语言写作。好消息是编程语言的句法（词汇和语法）并不像自然语言那样复杂。在本书中，我们将使用一种名为Python的语言进行编程，它的语法特别容易学习。但不要误以为它不是真正的编程语言——Python是真正的程序员用来编写真实软件的真正语言。此外，你在这里学到的思想可以迁移到以后对其他语言的学习。
虽然数据、算法和编程可能看起来似乎已经是一个完整的故事，但事实上幕后还有其他重要的思想。软件非常复杂，任何一个人都很难甚至不可能记住所有的交互部分。为了处理这样复杂的系统，计算机科学家利用了“抽象”这一概念：在设计程序的一部分时，我们可以忽略程序其他部分的非必要细节，只要对它们做高层次的理解。
例如，汽车有引擎、传动系统、电气系统和其他组件。这些组件可以被单独设计，然后组装在一起工作。传动系统的设计者不需要了解引擎如何工作的每个细节，只要了解传动系统和引擎的连接方式就足够了。对于传动系统的设计者来说，引擎是一种“抽象”。实际上，引擎本身分为气缸体、分电器等部分。这些部分也可以被视为彼此交互的抽象实体。在设计气缸体时，我们不需要考虑分电器如何工作的每个细节。
软件系统甚至比汽车更复杂。设计软件要求我们考虑抽象，以便确保许多人可以为项目做出贡献而无须每个人都了解所有内容，以便有条不紊地测试软件，以便能够在未来简单地用一个改进的新组件替换一个组件从而更新软件。因此，抽象是设计任何大型系统，特别是软件的关键思想。
本书致力于帮助你编写精心设计的程序，这些程序用数据做一些有趣的事情。在此过程中，我们希望让你明白计算机科学是一项极具创造性的工作，需要创新的问题解决方式、探索甚至实验。通常情况下，解决问题的方法不止一种。在某些情况下，甚至没有明确的“最佳”方法来解决问题。不同解决方案会有不同的优点。虽然Google、Facebook和GenBank非常易于使用，但在设计和不断更新此类系统时出现了许多挑战，并将不断出现。这些挑战经常导致计算机科学家团队共同努力寻找不同的解决方案并评估其相对优点。虽然我们在本书中将面临的挑战范围较小，但我们希望与你分享计算机科学核心的解决问题的感觉和创造力。
要点：简而言之，本书的目的是展示构成计算机科学的广泛活动，同时向你展示一些基本和美好的思想，并为你提供设计、实现和分析自己的程序的技能。
先行动再思考。
——W. H. Auden
了解计算机科学的最佳方法，就是直接进入并开始解决计算机科学问题。所以我们就这么做。在本节中，我们将研究一个重要问题的解决方案：如何确保你永远不必再清扫房间（或至少不必吸尘）。为了解决这个问题，我们将使用一种名为Picobot的简单编程语言来控制一个机器人，这个机器人基本上基于Roomba吸尘清扫机器人。
你可能想知道Python怎么了，我们说过在本书中将会使用这种编程语言。为什么我们忽略了Python，将我们计划用于本书其余部分的这种语言放在一边？答案是：虽然Python是一种简单的编程语言（但功能强大！），易于学习，但Picobot是一种更简单的编程语言，更易于学习。整个语言只需几分钟即可学习，但它允许你进行一些非常强大而有趣的计算。在讨论完整的编程语言之前，我们就能够开始一些严肃的计算机科学。这很新奇和有趣——无论你以前是否编过程，这应该会提供一种“我发现了！”的体验。因此，请打开你的浏览器并进入https://www.cs.hmc.edu/picobot。
该网站提供了一个探索Picobot功能的模拟环境。
你会注意到，我们使用“Picobot”一词来指代Roomba机器人和我们用于对它编程的语言。实际上，Picobot可能根本无法“看见”环境。作为替代，它也许通过许多可能的传感器来感知环境，包括碰撞传感器、红外线、相机、激光等。
这项最简单的任务（清扫），已成为家用机器人的“杀手级”应用。设想你自己是一个名为Picobot的Roomba真空吸尘器：你的目标是吸干净周围自由空间的碎屑——最好是不会错过任何角落或缝隙。机器人社区称之为覆盖问题：这种任务确保所有草都被割掉，所有表面都被喷上油漆，或所有火星土壤都被调查。
或者至少是“突破级”应用，让该行业第一次大规模盈利。
起初这个问题看起来很简单。毕竟，如果你的父母给你一个真空吸尘器，并告诉你给房间吸尘，你可能做得很好，甚至没有想太多。将策略传达给机器人不是应该很简单吗？
不幸的是，有一些障碍物使得Picobot的工作比你的工作难度大得多。第一，Picobot的视觉非常有限。它只能感知到它周围的东西。第二，Picobot完全不熟悉它应该清扫的环境。虽然你可以蒙着眼睛在你的房间四处走动而不会撞到东西，但Picobot没有那么幸运。第三，Picobot的内存非常有限。事实上，它甚至不记得房间的哪些部分它“看到过”，哪些“没看到过”。
虽然这些挑战让Picobot的工作（以及我们编程Picobot的工作）变得更加困难，但它们也让覆盖问题成为一个值得认真研究的、有趣且重要的计算机科学问题。
解决这个问题的首要任务，是以计算机能处理的方式表示它。换句话说，我们要定义解决这个问题所需的数据。例如，如何表示房间中的障碍物在哪里？或Picobot在哪里？我们可以将房间表示为一个平面，然后列出障碍物转角的坐标和Picobot位置的坐标。虽然这种表示是合理的，但我们实际上会使用稍微简单一些的方法。
“离散”是“分成独立的部分”在CS中的说法。
无论是草坪还是沙地，如果将其离散成单元格，环境就更容易被覆盖，如图1.2所示。这是我们的第一个抽象的示例：我们忽略了环境的细节，并将其简化为我们可以轻松使用的东西。Picobot同样被简化了。它占据一个单元格（最暗的灰色单元格），并且可以在4个方向上每次前进一步：东、南、西、北。
在Picobot环境或地图中，有4种类型的单元格：最暗的灰色单元格是Picobot本身，深灰色单元格是障碍物，浅灰色单元格是自由空间。Picobot无法感知是否已访问过空单元格（深灰色或浅灰色的），但它可以感知其4个邻近单元格中的每一个是自由空间还是障碍物。
Picobot无法爬上障碍物（深灰色单元格，我们也称之为墙壁），正如我们上面曾提到的，它不会提前知道这些障碍物的位置。Picobot可以感知的是它的直接环境：紧贴着它的北方、东方、西方或南方的4个单元格。周围的环境总是按“NEWS”（北东西南）的顺序报告为4个字母的串，这意味着我们将首先看到北方的邻近单元格，接下来是东方，然后是西方，最后是南方。如果北方的单元格为空，则第一个位置的字母是x；如果北方的单元格被占用，则第一个位置的字母是N。第二个字母是x或E，表示东方的单元格是空的还是被占用；第三个字母是x或W，表示西方的单元格是空的还是被占用；第四个字母是x或S，表示南方的单元格是空的还是被占用。例如，在图1.2左下角的位置，Picobot的传感器将它的周围环境报告为4个字母xxWS。
图1.2 Picobot环境或地图中4种类型的单元格
Picobot有16种可能的周围环境，带有字符串表示，如图1.3所示。当然，在我们一直在讨论的矩形房间中，许多周围环境模式不会出现。但是，它们可能会在其他情况下发生——例如，如果Picobot正在为建筑物的走廊吸尘。Picobot完全封闭的模式（字符串表示为NEWS），在任何合理的情况下都不应该出现！
图1.3 Picobot的16个可能的周围环境字符串
正如我们所见，Picobot可以感知它的周围环境。这在决策过程中非常重要。例如，如果Picobot正在向北移动并且它感觉到北方的单元格是一面墙，那么它不应该继续向北移动。实际上，模拟器不允许它向北移动。
我现在处于好奇的状态。
但是，Picobot如何“知道”它是在向北移动还是在向其他方向移动？Picobot没有天生的方向感。作为替代，我们使用一种称为“状态”的强大概念。计算机（或一个人，或几乎任何其他东西）的状态只是它的当前状态：开启或关闭，开心或悲伤，水下或外太空等。在计算机科学中，我们经常用状态来指代某种内部信息，描述计算机正在做的事。
Picobot的状态非常简单：它是0～99范围内的单个数字。有点令人惊讶的是，这足以让Picobot具备一些非常复杂的行为。Picobot始终以状态0开始。
任何事物的状态都可以用一组数字来描述。如果可能的话，描述人类状态会占用非常大的数字！这是一个有趣的哲学问题。
尽管Picobot的状态是用数字表示的，但用自然语言术语来思考它是有帮助的。例如，我们可能会认为状态0的意思是“我向北走，直到不能再进一步”。但重要的是要注意，没有一个状态数字具有任何特殊的内置含义。我们应该将意义与数字状态联系起来。而且，Picobot实际上并不知道它朝向的方向。但是我们可以通过定义一组适当的状态来定义我们自己的概念，即Picobot朝向哪个方向。
例如，假设我们希望Picobot执行一个任务：连续向北移动，直到它到达墙壁。我们可能会认为状态3意味着“我向北走，直到不能再往前走（当我到达北方的墙时，会考虑下一步做什么！）”。当Picobot到达一面墙时，我们可能希望它进入一个新的状态，如“我向西走，直到不能再往前走（当我到达西方的墙时，不得不考虑接下来要做什么！）”。我们可能会将该状态称为状态42（或状态4，这完全由我们定）。
图1.4展示了两条Picobot规则的5个部分。解释状态的思想有一种有用方法，即将不同的意图归于每个状态。根据这两条规则，Picobot的初始状态（状态0）代表“尽可能向西移动”。
图1.4 两条Picobot规则的5个部分
正如我们接下来看到的那样，作为Picobot程序员，你的工作就是定义状态及其含义。这样就控制了Picobot并让它做有趣的事情！
要点：状态就是一个数字，代表你希望Picobot承担的任务。
现在我们知道了如何表示Picobot的周围环境，以及如何表示它的状态。但是我们如何让Picobot做事呢？
Picobot通过遵循一组规则来移动，这些规则指定了动作和可能的状态改变。Picobot选择遵循的规则取决于其当前状态和当前环境。因此，Picobot完整的“思考过程”如下。
1．我评估目前的状态和周围环境。
2．根据这些信息，我找到一条规则，这条规则告诉我：（1）移动的方向；（2）我接下来希望处于的状态。
Picobot使用包含5个部分的规则来表达这个思考过程。上面的图1.4展示了这种规则的两个例子。第一条规则，
0 xxWx -> E 1用自然语言来说就是：“如果我处于状态0，只有西方相邻单元格有障碍物，那么向东走一步，进入状态1。”第二条规则，
0 xxxx -> W 0向西走，年轻的Picobot！
是说：“如果我处于状态0，周围没有障碍物，那么向西移动一步并保持在状态0。”总之，这两条规则利用了局部信息，指示Picobot向西移动穿过一个开放区域，直到它到达西方的边界，此时Picobot进入状态1。我们还没有说明当处于状态1时该做什么。我们稍后会回过头来看看！
以下是Picobot的工作原理。Picobot从状态0开始。在每一步，Picobot都会检查你一次编写的规则列表，查找适用的规则。Picobot会从你指定的第一条规则向下查看。如果规则的状态部分与Picobot的当前状态匹配，并且规则的周围环境部分与当前环境匹配，那么这条规则适用。这时，Picobot执行该规则并重复这个过程。
请记住，Picobot始终从状态0开始其任务。
如果没有匹配Picobot当前状态和当前环境的规则，会怎样？Picobot模拟器会在它的“消息”框中通知你，机器人将停止运行。同样，如果有多条规则适用，Picobot也会“抱怨”。
让我们回过头来讨论在状态1中做什么。没有规则指定Picobot在状态1中的行为——暂时还没有！就像状态0代表“向西”的任务一样，我们可以指定两条规则，使状态1代表“向东”的任务：
1 xxxx -> E 1
1 xExx -> W 0Picobot无法检测是否已经访问过某个单元格。这种限制是非常现实的。例如，Picobot不知道某个区域是否已经清扫过。
这些规则会回到状态0，从而创建一个无限循环，在空旷的一行中来来回回。试试看！请注意，Picobot网站在随机选择的单元格中启动Picobot。另外请注意，如果Picobot沿顶部或底部墙开始，那么没有规则匹配，不会移动。我们将在下一部分解决这个缺陷。
所以，下面是我们目前的4行“向西走向东走”Picobot程序的总体情况：
0 xxWx -> E 1
0 xxxx -> W 0
1 xxxx -> E 1
1 xExx -> W 0顺便说一句，这些规则的顺序无关紧要，因为我们编写了程序（正如Picobot所期望的那样），使得在给定时间只能应用一条规则。因此，我们可以按照希望的方式重新排列这些规则。例如，我们可以这样写：
0 xxxx -> W 0
0 xxWx -> E 1
1 xxxx -> E 1
1 xExx -> W 0图1.5展示了从几个不同的起始单元格开始运行该程序的结果。
图1.5 在4行程序上运行Picobot的结果
我们注意到，“向西走向东走”Picobot程序有一个问题：如果它从某些位置开始，那么它不会在东西方向上横穿，因为我们提供的规则太具体了。例如，在图1.5中，单元格#2的南方有一面墙，因此我们指定的规则都不适用，而Picobot只会保持不变。
Picobot需要克服其“不关心”的态度！
向西走的时候，我们真的不在乎北方、南方或东方是否有墙。同样，当向东走时，我们并不关心北方、南方或西方的邻近单元格。通配符*表示我们不关心给定位置（N、E、W或S）的周围环境。下面更新的Picobot程序利用了通配符，指示Picobot永远从它开始的位置向东西行走（吸尘）：
0 **x* -> W 0
0 **W* -> E 1
1 *x** -> E 1
1 *E** -> W 0最后，这里还有一个Picobot“小技巧”：除了指定移动方向N、E、W或S外，你可以用大写字母X来表示“留在原地”。例如，规则
0 Nxxx -> X 1是说：“如果我处于状态0并且北方有一面墙，请不要移动，而是进入状态1。”
到目前为止，我们已经研究了如何编写让Picobot移动的规则。但是在尝试解决Picobot的问题时，更全面地了解Picobot如何完成其任务，然后将该方法转换为规则，这样通常很有帮助。换句话说，我们希望开发一种算法，让Picobot完成期望的任务，这通常是覆盖整个房间。在上一节中，Picobot有一个较小的目标，即在一个空荡荡的房间里来回移动。完成此任务的算法步骤如下。
1．向西移动，直到Picobot撞上西方的一面墙。
2．然后向东移动，直到Picobot撞上东方的一面墙。
3．然后返回步骤1。
现在问题变成“如何将这个算法转化为上一节的规则？”
0 **x* -> W 0
0 **W* -> E 1
1 *x** -> E 1
1 *E** -> W 0如上所述，很难看到算法步骤与Picobot规则之间的联系。我们可以看到，Picobot需要两个状态来跟踪它正在移动的方向（即它是在步骤1还是步骤2中），但是仍然不清楚算法如何转换成精确的规则。从本质上讲，每条Picobot规则都以“如果-那么”的方式应用。换句话说，如果Picobot处于特定状态并且看到特定环境，那么它将采取某种行动，并可能进入新状态。通过一些小修改，我们可以重写上面的算法，更直接地采用Picobot的“如果-那么”规则结构。
永远重复以下步骤。
① 如果Picobot向西移动并且西方没有墙，那么继续向西移动。
② 如果Picobot向西移动并且西方有一面墙，那么就开始向东移动。
③ 如果Picobot向东移动并且东方没有墙，那么继续向东移动。
④ 如果Picobot向东移动并且东方有一面墙，那么就开始向西移动。
现在我们可以更清楚地看到，这个算法步骤与Picobot规则之间的直接转换：算法中的每个步骤直接转换为Picobot中的规则，其中状态0表示“Picobot向西移动”，状态1表示“Picobot向东移动”。以这种方式制定算法，是在Picobot中编写成功程序的关键。
虽然“向西走向东走”的程序指示Picobot完全覆盖它开始的那一行，但本节的挑战是制定一套规则，指示Picobot覆盖整个矩形空房间，例如在图1.2和图1.5中的房间。无论房间有多大，无论Picobot最初从哪里开始，这套规则（即你的程序）都应该有效。
因为Picobot不能区分已访问的和未访问的单元格，所以它可能不知道何时已经覆盖了每个单元格。但是，在线模拟器将检测环境已经成功完整遍历并报告。
试试看。你可能会发现，简单地修改我们在这里给出的规则是很有帮助的。例如，你可以从更改图1.1中的规则开始，以便在清扫当前行后，它们会进入相邻行。但是，一旦你对如何解决问题有了思路，我们建议你规划你的算法，然后以某种方式表达该算法，以便轻松地转换为Picobot规则。
在你开发了一个完全遍历空房间的Picobot程序之后，请试着针对更复杂的环境编写另外的程序。你会在Picobot网页上看到“MAP”选项，可以在其中前后滚动查看我们创建的地图集合。你也可以使用鼠标单击一个单元格来编辑这些地图：单击一个空单元格将它转换为墙，然后单击墙将它转换为空单元格。请记住，无论Picobot从哪里开始，你的程序都应该有效。
一个特别有趣的环境是图1.6所示的迷宫。请注意，此迷宫具有特殊属性，即所有墙都连接到外边界，所有空单元格都与墙相邻。
图1.6 Picobot的迷宫
具有这种属性的较小的迷宫如图1.7a所示。任何具有这种属性的迷宫都可以利用一种简单算法进行完全探索，即所谓的“右手规则”（如果你愿意，也可以用“左手规则”）。
谢谢你没让我们听老掉牙的玉米地迷宫笑话。
设想是你在迷宫中，而不是Picobot。与Picobot相比，你可以清楚地了解你朝向的方向，并且你有两只手。你开始朝北走，右手触摸墙壁。现在，只需确保右手始终接触墙壁，走过迷宫，就可以访问每个空单元格。暂停一下，让你自己相信这是真的。另外请注意，如果某些墙未连接到外边界，这个算法将不会访问每个单元格，如图1.7b中的迷宫所示；或者如果某些空单元格不与墙相邻，如图1.7c所示。
图1.7 （a）所有墙都连接到外边界，且所有空单元格都与墙相邻的迷宫。
（b）一些墙未连接到外边界的迷宫。（c）一些空单元格不与墙相邻的迷宫
将右手规则转换为一组Picobot规则是一项有趣的计算挑战。毕竟，你有方向感，且有右手引导你围绕墙壁走，而Picobot没有手也没有方向感。为了“教会”Picobot右手规则，我们再次需要利用状态来表示Picobot朝向的方向。似乎必须考虑极其大量的情况，但事实上，情况的数量是有限的，并且实际上非常小，这使得可以针对这项任务对Picobot编程。
首先，使用4个状态0、1、2和3来表示朝向北、南、东和西的Picobot似乎很自然。现在，我们需要引入一些规则，让Picobot表现得好像右手触摸墙壁一样。
当然，所有空单元格都必须是可达的。如果某些单元格与其他单元格隔离，则问题实际上是不可能的。
假设我们处于状态0，我们（任意）选择它代表Picobot朝向北方。那么Picobot想象中的右手朝向东方。如果东方有一面墙而北方没有墙，那么右手规则就会告诉我们向北前进一步并保持向北。向北前进一步没问题。“保持向北”意味着“保持在状态0”。另一方面，如果我们处于状态0并且东方没有墙，那么Picobot应该向东走一步，并认为自己朝向东方。“朝向东方”将意味着转换到另一个状态，用于对这种信息进行编码。这是一个有趣的挑战，我们建议你在这里停下来尝试一下。（请记住，无论Picobot启动的位置如何，对于任意迷宫，只要所有墙连接到外边界并且所有空单元格都与墙相邻，你的程序都应该有效。）
能否编写一个Picobot程序，可以充分探索我们提供的任意房间？令人惊讶的是，答案是“不能”，并且可以用数学方法证明这一事实。Picobot的计算能力不足以保证所有环境的覆盖率。但是，通过为Picobot添加一个简单的功能，可以对它编程，实现完全探索任意房间。这个功能就是沿途放置、感知和拾取“标记”。
像Picobot一样的基本的计算挑战将我们引向一些“可以证明无法解决的问题”。这一事实表明，计算和计算机远非无所不能。当你读完这本书的时候，将学会如何证明某些问题超出了计算机可以解决的范围。
abstraction：抽象 software：软件
algorithm：算法 state：状态
data：数据 syntax：语法
Python wildcard：通配符
1．任何可以用右手规则完全探索的迷宫（也就是迷宫内的每个空单元格），也可以用左手规则完全探索，并且在左手规则中，Picobot保持它想象的左手接触墙。
2．右手规则可用于充分探索任何迷宫。
3．可以编写一个Picobot程序，充分探索我们提供的任意房间。
1．计算机科学中最有力的思想之一是自动重复：在任务完成之前反复执行相同的步骤。请描述一个真实世界的例子，其中你多次执行相同的事情来完成任务。
2．用你自己的话定义一个“Picobot状态”的含义。
1．外星人想寻找一个Picobot程序，用于完全探索迷宫，其中所有墙都连接到外部边界，所有空单元格都与墙相邻。令人惊讶的是，有可能只用4个状态，每个状态只有2条规则，来编写这样的程序！请尝试编写这样的程序。
2．为Picobot模拟器中的其他一些“房间”编写Picobot程序。你会发现有些房间需要一个专门针对那个房间的程序。
