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

本书是在一系列给中学生普及算法和计算思维的讲座基础上整理编写的，选择了计算机科学中一些有重要应用价值的典型问题，用通俗易懂的语言介绍著名的算法思想。尽管本书的初衷是让高中生领会算法和计算机科学的奇妙与魅力，但它同样适合已经进入大学计算机类专业学习的学生阅读，目的是使学生欣赏计算机科学有趣的一面，也能对“我们如何解题”有更深入的理解。对于从事计算机教学尤其是基础教育的广大教师，也可以从本书中得到启发与收获。

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

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

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