本书以通俗易懂的语言向读者描述了各类常用算法。全书包括四个部分，涉及排序与搜索、算术与密码、规划、协同与设计、优化四个领域，每个部分都给出该领域中常用的算法，每一个算法都从一个实际的生活场景引入。通过作者深入浅出的介绍，读者可以轻松了解计算机科学中常用的算法的原理，具备初步的计算思维能力。本书适合作为高校计算机科学入门课程的教材，也适合作为计算机科学的科普书籍。

无

最近几十年来许多技术创新和成果都依赖于算法思想，这些成果广泛应用于科学、医药、生产、物流、交通、通信、娱乐等领域。高效的算法使得你的个人电脑得以运行新一代的游戏，这些复杂的游戏在几年前可能都难以想象。更重要的是这些算法为一些重大科学突破提供了基础。例如，人类基因组图谱解码得以实现与新算法的发明是分不开的，这些算法能将计算速度提高几个数量级。
算法告诉计算机如何处理信息，如何执行任务。算法组织数据，使得我们能有效地搜索。如果没有聪明的算法，我们一定会迷失在互联网这个巨大的数据丛林中。同样，如果没有天才的编码和加密算法，我们也不可能在网络上安全地通信。天气预报与气候变化分析也依靠高效模拟算法。工厂生产线和物流系统有大量复杂的优化问题，只有奇巧的算法能帮助我们解决。甚至当你利用GPS寻找附近的餐厅或咖啡馆时，也要靠有效的最短路计算才能获得满意的结果。
并非像很多人认为的，只有计算机中才需要算法。在工业机器人、汽车、飞机以及几乎所有家用电器中都包含许多微处理器，它们也都依赖算法才能发挥作用。例如，你的音乐播放器中使用聪明的压缩算法，否则小小的播放器会因为存储量不足而无法使用。现在的汽车和飞机中有成百上千的微处理器，算法能帮助控制引擎，减少能耗，降低污染。它们还能控制制动器和方向盘，提高稳定性与安全性。不久的将来，微处理器可能完全替代人，实现汽车的全自动驾驶。目前的飞机已经能做到在从起飞到降落的全过程中无须人工干预。
算法领域最大的进步都来自美好的思想，它指引我们更有效地解决计算问题。我们面对的问题绝不局限于狭义的算术计算，还有很多表面上不是那么“数学化”的问题。例如：
如何走出迷宫？
如何分割一张藏宝图让不同的人分别保存，但只有重新拼合才可能找到宝藏？
如何规划路径，用最小成本访问多个地方？
这些问题极具挑战，需要逻辑推理、几何与组合想象力，还需要创造力才能解决。这些就是设计算法所需要的主要能力。
本书包括不同作者撰写的41篇文章，用非技术化的语言介绍了一些最著名的算法思想。多数文章源自德语大学中发起的科普活动，初衷是让高中生领会算法和计算机科学的奇妙与魅力。阅读本书不需要任何关于算法和计算的预备知识。我们希望不仅学生，而且包括希望了解迷人的算法世界的成年人都能从本书中得到启发与乐趣。

计算机\算法

首届CCF杰出教育奖获得者、南京大学陈道蓄教授翻译并推荐
启蒙学生对计算机科学兴趣、提升计算思维素养的优秀入门读本
最近几十年来，许多技术创新和成果都依赖于算法思想，这些成果广泛应用于科学、医药、生产、物流、交通、通信、娱乐等领域。高效的算法使得你的个人电脑得以运行新一代的复杂游戏。更重要的是这些算法为一些重大科学突破提供了基础。算法告诉计算机如何处理信息，如何执行任务。算法组织数据，使得我们能有效地搜索。并非像很多人认为的，只有计算机中才需要算法。在工业机器人、汽车、飞机以及几乎所有家用电器中都包含许多微处理器，它们也都依赖算法才能发挥作用。
算法领域最大的进步都来自美好的思想，它指引我们更有效地解决计算问题。我们面对的问题绝不局限于狭义的算术计算，还有很多表面上不是那么“数学化”的问题。例如：如何走出迷宫？如何分割一张藏宝图让不同的人分别保存，但只有重新拼合才可能找到宝藏？如何规划路径，用最小成本访问多个地方？这些问题极具挑战，需要逻辑推理、几何与组合想象力，还需要创造力才能解决。这些就是设计算法所需要的主要能力。
本书是在一系列给中学生普及算法和计算思维的讲座基础上整理编写的，选择了计算机科学中一些有重要应用价值的典型问题，用通俗易懂的语言介绍最著名的算法思想。尽管本书初衷是让高中生领会算法和计算机科学的奇妙与魅力，但它同样适合已经进入大学计算机类专业学习的学生阅读，目的是使学生欣赏计算机科学有趣的一面，也能对“我们如何解题”有更深入的理解。对于从事计算机教学尤其是基础教育的广大教师，也可以从本书中得到启发与收获。

译者简介
陈道蓄　南京大学教授、博士生导师；从事计算机软件教学与科研30多年。近年来积极参与计算机专业核心基础课程的改革以及中国工程教育专业认证体系建设。2012年获得中国计算机学会首届杰出教育奖，2014~15年获得江苏省教学成果特等奖以及国家级教学成果二等奖，2016年获得江苏省科技进步一等奖。2014年被授予南京大学教学终身成就奖。目前担任中国工程教育专业认证协会常务理事、学术委员会副主任、结论审议委员会委员、计算机类专业认证委员会副主任、教育部新工科建设与实践专家组成员。

[德]贝特霍尔德·弗金（Berthold Vöcking） 赫尔穆特·阿尔特（Helmut Alt） 马丁·迪茨费尔宾格（Martin Dietzfelbinger） 吕迪格·赖舒科（Rüdiger Reischuk） 克里斯蒂安·沙伊德勒（Christian Scheideler） 黑里贝特·沃尔默（Heribert Vollmer） 多萝西娅·瓦格纳（Dorothea Wagner） 编著：本书共有66位作者，主要来自德国、瑞士。由贝特霍尔德•弗金（Berthold Vöcking）、赫尔穆特•阿尔特（Helmut Alt）、马丁•迪茨费尔宾格（Martin Dietzfelbinger）、吕迪格•赖舒科（Rüdiger Reischuk）、克里斯蒂安•沙伊德勒（Christian Scheideler）、黑里贝特•沃尔默（Heribert Vollmer）、多萝西娅•瓦格纳（Dorothea Wagner）领衔编著。

我问一些刚刚进入大学的新生为什么选择计算机类专业，几乎每个人都提到对“人工智能”感兴趣，但似乎其中多数人对人工智能并没有多少了解。
本书第41章讨论“模拟退火”算法，用来作为例子的是一个几何拼图类的组合游戏，大多数人会将其视为一种“智力游戏”。当实验证明计算机可以得到比绝大多数人更高的分数，这是否就体现了计算机的“智能”呢？
一个有好奇心的中学生不难理解第41章的内容。其实机器并不“知道”自己在做什么，它只是执行几个一点都不复杂的动作。告诉机器以什么样的顺序去执行某些（其实很基本的）动作，这就是我们通常说的“算法”。
当今我们的日常生活已经高度依赖信息技术，似乎计算机什么都能干，但稍稍了解计算机内部结构的人都知道“那个机器”本身其实只能做为数不多的基本动作。能够让计算机系统（不仅仅是你能看见的硬件设备）似乎无所不能的关键是各种各样的算法。
人用“智慧”设计算法，能够让机器表现出“智能”。但是我们还不知道如何在可以预见的时间段内让机器具有智慧（尽管我们相信科学技术会以超出我们所有人的想象更迅速地发展）。
前些年开始流行一个词：计算思维。究竟什么是计算思维，计算机工作者至今并没有能给出一个明确的定义。至少我们可以将计算思维理解成人的一种思维方式，它应该能使得计算机更好地（包括通过表现出“智能“的方式）服务于人类。
从当前计算机应用水平来看，算法是计算思维的一种具体体现。人们已经设计出许多非常“聪明“的算法，极大地提高了我们解决问题的能力，但应用中复杂的问题仍然期待我们给出更有效的算法。这是计算机科学家工作的一个重要方面。
任何学科的发展都依赖于一代一代优秀的年轻人的加入，其他学科的经验表明，科学技术普及是引导青少年走向探索未知、创造未来的科学技术道路的重要举措。
坦率地说，计算机科学普及工作与一些传统学科相比差距巨大。一方面是因为计算机科学历史较短。更深层的一个原因应该是认识层面的。信息技术发展迅速，渗透面极广，但社会公众更多的是从技术与实用的角度，而不是从思维方式的角度看待它。现在有非常多的中小学生，甚至幼儿园小朋友在学“编程”。这是很好的事，但只是学会某种语言（不管是C++、Java还是Python）编程只是“技术”，充其量说是“智能”，却绝不是“智慧”。
我曾经听一位钢琴教师说起一位“琴童”的家长问她：“我的孩子通过钢琴十级了，下面该做什么呢”。这位教师的评论多少反映了她对当前社会公众对待学习急功近利态度的不认同。思维能力的培养是一个过程，目的是培养能应对不可预知的问题的基础能力。而应对“题型”，使用“工具”尽管也是学习中不可忽缺的部分，但却不能替代思维能力的培养。
思维方式不是可以用某种“模式”描述的，如何将计算思维培养融入基础教育中是当前一个重要的问题。本书是在一系列给中学生普及计算思维的讲座的基础上整理编写的。选择了计算机科学中一些有重要应用价值的典型问题，但讲述方式充分体现了趣味性。当我第一次看到此书时就被它吸引。
计算机专业是中国工程类专业中规模最为庞大的。时时听到有教师埋怨现在的学生“不好学”。中国传统的教育相对忽视学生的兴趣，强调学习是“责任”，“学习就应该刻苦”。其实兴趣是最好的学习动力，激发学生的兴趣本身也是教师的责任。
本书提供了一个如何提高学生兴趣的很好例子。讨论的每个话题都能体现作者“深入浅出”的用心。每个话题都用日常有趣的问题引入，介绍算法时注意引导读者考虑算法背后的基本思想。但作者又不局限于简单的“问题–答案”描述。尽管是普及读物，作者仍然会在可以理解的范围内引导读者考虑算法的正确性以及复杂性等可以更深入探讨的方面。在若干章节中，作者还通过实验数据来分析结果，注意到体现计算机算法工程性的一面。这甚至做到了当前我们大多数算法课程都没有做到的事。但我特别要强调一点，这都是在不牺牲普及读物的基本可理解性的要求下做到的。尽管本书是多位作者讲稿的合集，但显然出版前还是注意到风格的统一，避免给读者带来阅读上的不适。
广大青少年读者，特别是那些学习过一点编程的中小学生，一定会通过阅读本书在计算思维素养上得到提升。
但绝不仅限于此。本书同样适合已经进入大学计算机类专业学习的学生阅读。他们能够从中欣赏计算机科学有趣的一面，也能对“我们如何解题”有更深入的理解。
我多年来一直从事计算机算法方面的教学，对本书中涉及的内容都很熟悉。但是整个翻译过程仍然让我觉得受益匪浅。我感到尽管本书是针对中学生的普及读物。但是对于从事计算机教学的广大教师也是很值得阅读的。我甚至将其中部分内容用于中国计算机学会每年举办的“计算机教学改革导教班”。我希望计算机专业教师（特别是基础课教师）更关注这样的普及读物，并能从中得到启发。

陈道蓄
2018年8月于南京

出版者的话
译者序
前言
第一部分　搜索与排序
第1章　二分搜索 3
第2章　插入排序 8
第3章　快速排序 11
第4章　并行排序—追求速度 17
第5章　拓扑排序—合理安排任务执行次序 25
第6章　快速搜索文本—Boyer-Moore-Horspool算法 30
第7章　深度优先搜索 37
第8章　Pledge算法—如何从黑暗的迷宫中逃脱 46
第9章　图中的回路 51
第10章　PageRank—搜索万维网 60
第二部分　算术与密码
第11章　大整数相乘—比长乘更快 69
第12章　欧几里得算法 75
第13章　埃拉托色尼筛法—计算素数表能有多快 79
第14章　单向函数的陷阱—掉下去就出不来了 88
第15章　一次性加密算法—最简单、最安全的保密方式 94
第16章　公钥密码 99
第17章　如何共享机密 108
第18章　通过电子邮件玩扑克 114
第19章　指纹 122
第20章　哈希方法 131
第21章　编码—防止数据出错或丢失 136
第三部分　规划、协同与模拟
第22章　广播—如何迅速发布信息 147
第23章　将数字转换为英语单词 152
第24章　确定多数—谁当选为班级代表 157
第25章　随机数—如何在计算机中创造随机 163
第26章　火柴游戏的取胜策略 170
第27章　体育联赛日程编排 175
第28章　欧拉回路 181
第29章　快速画圆 186
第30章　计算物理问题的高斯–赛德尔迭代 192
第31章　动态规划—计算进化距离 198
第四部分　优化
第32章　最短路 205
第33章　最小生成树—有时贪心也有回报 211
第34章　最大流—在高峰时刻去体育场 216
第35章　婚姻介绍人 225
第36章　圆闭包 232
第37章　在线算法 235
第38章　装箱问题 239
第39章　背包问题 245
第40章　旅行推销商问题 250
第41章　模拟退火 256