算法漫步 乐在其中的计算思维

（1）2020年7月，我国火星探测器“天问一号”发射升空，历经7个月的太空遨游，终于在2021年2月成功进入火星轨道。随后，“天问一号”所搭载的火星车“祝融号”于2021年5月着陆火星，开启了奇妙的探索之旅。火星与地球相隔甚远，“祝融号”与地球控制中心之间利用信号进行一次单向“交流”，就要花费十多分钟的时间，所以无法完成实时控制。因此，在大部分时间里，甚至包括2021年9月由太阳阻碍导致的完全“失联”的一个月，“祝融号”需要靠自己完成工作，比如避障、拍照、取样分析等，这一系列工作内容乃至整个庞大的“天问一号”探测工程，背后都离不开算法的支持。
（2）随着计算机技术、人工智能技术的快速发展与应用，我们的生活方式迎来革新。在享受人工智能带来的益处的同时，很多人也不免会担忧它产生的威胁。算法，作为前沿技术的基础与核心，就是拉近人们与前沿技术的关系的关键点。南京大学计算机科学与技术系教授陈道蓄与北京大学计算机科学技术系教授李晓明通过多年教学与科研，积累了大量经验，本书就是他们在算法思维普及方面的成果。从有趣的故事、游戏或经典的案例出发，用伪代码和Python代码降低理解门槛，避开枯燥与复杂的描述，让读者仿佛在进行一个个解谜游戏，轻松地学习算法，体会算法精髓，感受算法魅力。了解算法，也能帮助读者以更积极的态度迎接智能技术革命。

本书是一本面向问题求解的计算机算法普及读物。笔者挑选了24个问题，有些属于计算机科学中的经典，有些则来自游戏等其他领域的场景，旨在提供一个不同于普通算法教科书的视野。在相关求解算法的介绍上大体遵循问题导入、算法思路、算法描述和算法分析的思路，从而使得对每一个问题和算法的讨论相对独立。全书可以任意顺序选读。
本书适合受过高中及其以上教育的读者，适合作为中学信息技术课程改革和大学计算机基础课的教学参考书，也有助于曾经学过计算机相关课程的读者加深关于算法的认识。

陈道蓄，南京大学计算机科学与技术系教授。从事计算机软件教学与科研工作四十年，承担算法类基础课教学任务多年。因计算机核心基础课程教学改革成果获教学成果奖二等奖；因泛在计算平台技术研究成果获江苏省科技奖一等奖。曾获中国计算机学会杰出教育奖、南京大学教学终身成就奖，三次被学生推选为“南京大学我*喜爱的教师”。

李晓明，北京大学瑞声慕课讲席教授，中国计算机学会会士。曾因主持研发中国高校影响力*大的搜索引擎“天网搜索”获中国计算机学会王选奖；因创设与推广交叉学科课程“社会科学中的计算思维方法”获北京市教学成果一等奖；因倡导与推动慕课在中国的兴起与发展获中国计算机学会杰出教育奖、中国教师发展基金会杰出教学奖。

前言
章节内容难度标记说明
第 1 篇　游戏与算法 ………………………….1
1　量水问题 …………………………………2
2　一笔画问题 ……………………………….9
3　迷宫问题 ………………………………..17
4　拼块游戏 ………………………………..27
5　对弈游戏 ………………………………..38
第 2 篇　计算机基础算法 ……………………..45
6　查找 ……………………………………46
7　排序 ……………………………………55
8　连通 ……………………………………64
9　连通的代价 ………………………………75
10　数据压缩 ……………………………….84
11　短路径 ……………………………….94
12　流量 ………………………………106
13　凸包计算 ………………………………117
第 3 篇　生活中的算法 ………………………127
14　选举 ………………………………….128
15　分类 ………………………………….137
16　聚类 ………………………………….147
17　投资 ………………………………….157
18　匹配 ………………………………….167
19　调度 ………………………………….176
20　密码 ………………………………….188
21　社会网络 ………………………………197
第 4 篇　算术和代数问题 …………………….207
22　斐波那契数列 …………………………..208
23　大数乘法三解 …………………………..215
24　高次方程求解 …………………………..223
参考文献 ………………………………….232
后记 ……………………………………..234

在短短几十年的时间里，数字技术已然改变了人们的生活。如今走到哪里都能看到人们手中抓着手机，真是“抓着”，而不仅是随身携带。有人甚至觉得只要有手机，多再加上一台笔记本电脑，就能应付工作、生活和休闲的全部需要。
大到从火星探测器发回图片，小到在网上点餐，多样化的计算机应用背后都有一个共同的概念：算法。如果把迅速发展的信息化社会看作“三驾马车”在奔跑，那“三匹马”就是芯片、系统和算法。而这其中，让人们觉得“雾里看花”的就是算法。“App”这个词几乎人人都能脱口而出，且能对应到一个个明确的对象，而“算法”却总有点“拗口”，似乎看不见、摸不着。
这是因为许多基础算法尽管每天都会被用到，但它们只是整个应用解决方案中的某些环节，默默地在背后发挥作用。例如，人们在12306网站订车票时无意识地就在用排序算法。另外，即使算法直接与应用相关，用户也未必注意到“隐身”于系统之中的一小段代码，例如，看视频时必然会用到的压缩算法。
通常介绍算法的书会把算法与菜谱进行类比：菜谱列出将食材和调料（输入）加工成菜品（输出）的步骤；计算机算法则是将输入数据转化为输出数据的过程。在讨论计算机算法时，数据指的是将物理世界的问题抽象为模型后的数据表示。
尽管大家都能理解讲算法时提到菜谱只是类比，也能体会到计算机算法对逻辑严谨性的要求与菜谱显然不同，但这样的类比仍然会产生误导，影响我们对于计算思维的认识。
人的一生甚至整个人类的历史就是不断“解题”的过程。解题过程与人类自身解题能力的提高是互相促进的演化过程，包括对人类进化的影响。人类当前的解题能力基于世世代代的知识积累以及在这个基础上凝练出的智慧，前者常体现为有形的记录，后者常表现为无形的洞悉和参悟。这些知识与智慧和人作为生物物种之一的生理特质是密切相关的，也适合由人运用它们去解决问题。正如工业革命促成动力装置大发展，极大地延伸了人的体力极限，计算机的出现理应延伸人的智力极限。
不过，目前甚至可见的未来，计算机解题的能力并不来源于类人的智慧，尽管某些应用表面上看似乎是这样。计算机表现出来的能力主要还是依赖极高的算力、极大的数据量，以及过去几十年来积累的丰富算法。中国计算机学会前理事长李国杰院士曾说过：“脑科学等领域的成果还不能为现在的智能计算提供任何直接的支撑。”计算思维的核心就是将人的智慧和计算机的优势限度地结合起来，实现这一目标的途径就是算法，目前的人工智能也是依赖算法进步的。一些因效率太低或风险太高而不被看好的人工解题方法，如穷尽搜索、试错等，却可能引导人们提出非常好的计算机算法。
随着智能技术的进步，人工智能对人类的威胁逐渐成为热门话题之一。一个经常被提及的论点是：人类的学习过程很慢，机器学习效率则提高得很快，因此不久后机器智能将超过人类。机器在棋类比赛中战胜世界冠军已足够让世人震惊，在以自然语言为媒介的电视问答大赛中机器也战胜了人类高手，这更让人觉得“通用、自主”的“强人工智能”带来的威胁就在眼前。
但这里似乎忽略了一个问题：人的“学习曲线”是否能改进？更具体地说，能不能利用机器智能改进人的学习效率？其实我们现在的教学模式是在计算机出现之前历经千百年形成的，即在知识总结的基础上构建体系，开发课程，然后按照课程进行教学，通常也能在学习者的大脑中重构相同的体系。这个过程侧重于知识的梳理和传递。至于将人类智慧融入教学，似乎更依赖于学习者的“悟道”。中国流行的古话“修行在个人”显然表明老师对怎么能让学生真正“悟出道”考虑得并不多。
人们对于机器智能发展的顾虑显然是因为机器已经从数据处理进化到了知识处理的阶段。与机器比赛知识处理，人类似乎不是对手。人类的学习过程必须从重知识传递转向重知识驾驭能力，可是学习模式进化迟缓。虽然计算机已广泛应用于教学，且近两年线上教学得到广泛采用，但坦率地说，教学模式并没有根本变化，多数还只是将传统课程迁移到了网上。
几十年前，管理信息化兴起之时，人们首先是将各种管理数据和表格电子化。但很快，人们就认识到，不改变管理模式不可能真正实现管理信息化。今天，对于教育人类面临同样的问题：什么样的教育模式才真正面向未来？如何使现在培养的人才不会很快被机器所替代？对计算机领域而言，积极发展智能技术，同时让学生主动探索如何利用机器智能更好地提升人类智慧，努力探索如何改进人类的学习曲线，方为面对技术发展的积极态度。当前具体着眼点应该包括充分理解计算环境的变化，以及培养学生与时俱进的算法设计能力。
科学普及往往没有正规科学技术教育那么明确的领域针对性，它一直是科技教育中不显眼但却具有持续意义的环节，对激发人特别是青少年的创造潜力有不可替代的作用。早在1826年，法拉第在英国皇家学会倡导了面向社会公众的“圣诞科学演说”，该活动一直延续至今，成为科学家服务于科学普及的典范。与自然科学、数学等学科相比，计算机科学技术的历史还非常短，其科普则更加滞后。但计算机技术的应用从深度、广度和渗透速度而言都是其他学科无法比拟的。2008年的“圣诞科学演说”邀请了曾任英国皇家学会副主席的计算机科学家Chris Bishop进行演讲，他强调了计算机算法普及的意义和迫切性。
本书是我们在算法思维普及方面尝试的成果。目标是让广大读者理解无处不在的计算机和网络应用背后的核心思想，体会当谈及算法的时候应该关心哪些问题。我们通过一些例子的铺陈，希望读者能够意识到人所主导的计算机解题关键在于用人的智慧充分发挥计算机的长处，延伸人类的智力极限。这不同于传统的解题思想，它应能支持我们以更积极的态度迎接智能技术革命。
本书适合受过高中及其以上教育，对数学和计算机有兴趣的读者，适合作为大学计算机基础课和中学信息技术课程改革的教学参考书，也有助于曾经学过计算机相关课程的读者刷新关于算法的认识。
俗话说：多一个数学公式就会少一半读者。本书的内容决定了不可能完全回避数学公式和代码。我们将本书定位于“中级科普”，既让一般读者领略计算机解题带来的乐趣，又能为有志于将来在计算机科学领域继续探索的青少年读者提供前进的跳板。在讨论问题及其解法时，我们回避严格的数学推导，但不回避对正确性和复杂性的分析。算法描述原则上采用伪代码，部分代码涉及细节，可能形式上更像Python语言。不过初学者应该记住：“算法，代码第二。”我们在合适的地方也会提供一些可进一步探讨或与程序实现相关的问题与建议，希望有助于启发读者的思考。
本书名为《算法漫步》，虽然内容分为四篇，但不具有学术或技术上的分类含义，只是按照内容粗略划分，以方便阅读。读者可以按照兴趣任意选择阅读顺序和方式，当然我们希望读者对每部分都有兴趣。考虑到本书读者的背景不同，我们也从算法逻辑、程序与数据结构，以及数学知识三方面，提供了关于本书24个问题的难度标记，供选读时参考。
我们在计算机教育领域工作多年，尽管在计算机教学与科研方面略有积累，但深知写出好的科普作品实非易事，既要易于读者理解，又不能在核心的科学技术内容上产生误导。本书一定存在瑕疵，希望得到广大读者的批评指正。我们在这本书上的努力算是抛砖引玉，期望今后能看到更多在计算机领域有所建树的学者、教师关注计算思维的科普，产生更多优秀作品，为创建适合智能时代的新教学模式提供启发。