研究算法给实际编程的法式员带来许多利益。先进的算法工具有时候对软件系统影响很大——淘汰开发时间，同时使执行速度更快。算法与其他那些深奥的思想一样重要，但在更一般的编程层面上具有更重要的影响。

在《啊哈!灵机一动》一书中（本文的标题就借鉴了它），Martin Gardner1形貌了深得我心的一个思想：“看起来很难题的问题也可以有一个简朴的、意想不到的谜底。”与高级的方法差别，算法的啊哈！灵机一动 并非只有在大量的研究以后才气泛起；任何愿意在编程之前、之中和之后举行认真思考的法式员都有时机捕捉到这灵机一动。1　三个问题好了，平常的话讲得够多啦。本文将围绕三个小问题展开。

在继续阅读以前，请先试着解决它们。A．给定一个最多包罗40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“暂时”文件可用，可是仅有几百字节的内存，又该如何解决该问题？B．将一个n元一维向量向左旋转2i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。

简朴的代码使用一个n元的中间向量在n步内完成该事情。你能否仅使用数十个分外字节的存储空间，在正比于n的时间内完成向量的旋转?C．给定一个英语字典，找出其中的所有变位词荟萃。例如，“pots”、“stop”和“tops”互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来获得。

2　无处不在的二分搜索我想到的一个数在1到100之间，你来猜猜看。50？太小了。75？太大了。

如此，游戏举行下去，直到你猜中我想到的数为止。如果我的整数位于1到n之间，那么你可以在次之内猜中。

如果n是1 000，10次就可以完成；如果n是100万，则最多20次就可以完成。这个例子引出了一项可以解决众多编程问题的技术：二分搜索。初始条件是已知一个工具存在于一个给定的规模内，而一次探测操作可以告诉我们该工具是否低于、即是或高于给定的位置。二分搜索通过重复探测当前规模的中点来定位工具。

如果一次探测没有找到该工具，那么我们将当前规模减半，然后继续下一次探测。当找到所需要的工具或规模为空时停止。在法式设计中二分搜索最常见的应用是在有序数组中搜索元素。

在查找项50时，算法举行如下探测。众所周知，二分搜索法式要正确运行很难题。顺序搜索在搜索一个具有n个元素的表时，平均需要举行n/2次比力，而二分搜索仅仅举行不凌驾次的比力就可以完成。

这在系统性能上会造成庞大的差异。下面的故事来自于《ACM通讯》的实例研究“TWA Reservation System”。我们有一个执行线性搜索的法式，可以在1秒钟内对一块很是庞大的内存块完成100次搜索。随着网络的增长，处置惩罚每条消息所需的平均CPU时间上升了0.3毫秒，这对我们来说是庞大的变化。

我们发现问题的泉源是线性搜索。把法式改为使用二分搜索以后，该问题消失了。我在许多系统中也遇到过相同的问题。

法式员在开始的时候使用简朴的顺序搜索数据结构，这在开始的时候通常都足够快。当搜索变得太慢的时候，对表举行排序并使用二分搜索通常可以消除瓶颈。可是二分搜索的故事并没有在快速搜索有序数组这里终止。Roy Weil将该技术应用于清理一个约1000行的输入文件，其中仅包罗一个错误行。

很不幸，肉眼看不堕落误行。只能通过在法式中运行文件的一个（起始）部门而且视察到离奇错误的谜底来分辨，这将会花费几分钟的时间。他的前任调试人员试图通过每次运行整个法式中的少数几行法式来找堕落误行，但只在取得解决方案的门路上前进了一点点。

Weil是如何仅仅运行10次法式就找到罪魁罪魁的呢？经由前面的热身，我们现在来攻克问题A。输入为顺序文件（思量磁带或磁盘——虽然磁盘可以随机读写，可是重新至尾读取文件通常会快得多）。文件包罗最多40亿个随机排列的32位整数，而我们需要找出一个不存在于该文件中的32位整数。

（至少缺少一个整数，因为一共有232也就是4 294 967 296个这样的整数。）如果有足够的内存，可以接纳位图技术，使用536 870 912个8位字节形成位图来表现已看到的整数。

然而，该问题还问到在仅有几百个字节内存和几个稀疏顺序文件的情况下如何找到缺失的整数？为了接纳二分搜索技术，就必须界说一个规模、在该规模内表现元素的方式以及用来确定哪一半规模存在缺失整数的探测方法。如何来实现呢？我们接纳已知包罗至少一个缺失元素的一系列整数作为规模，并使用包罗所有这些整数在内的文件表现这个规模。

灵机一动的效果是通过统计中间点之上和之下的元素来探测规模：或者上面或者下面的规模具有至多全部规模的一半元素。由于整个规模中有一个缺失元素，因此我们所需的那一半规模中一定也包罗缺失的元素。这些就是解决该问题的二分搜索算法所需要的主要想法。

在翻阅谜底检察Ed Reingold是如何做的以前，请实验将这些想法组织起来。对于二分搜索技术在法式设计中的应用来说，这些应用仅仅是皮毛而已。求根法式使用二分搜索技术，通过一连地对分区间来求解单变量方程式（数值分析家称之为对分法）。

当选择算法区分出一个随机元素以后，就对该元素一侧的所有元素递归地挪用自身（这是一种随机二分搜索）。其他使用二分搜索的地方包罗树数据结构和法式调试（当法式没有任何提示就意外中止时，你会从源代码中哪一部门开始探测来定位错误语句呢？）。

在上述的每个例子中，分析法式并对二分搜索算法做些许修改，可以带给法式员功效强大的啊哈！灵机一动。3　基本操作的威力二分搜索是许多问题的解决方案，下面研究一个有几种解决方案的问题。

问题B仅使用几十个字节的分外空间将一个n元向量x在正比于n的时间内向左旋转i个位置。该问题在应用法式中以种种差别的伪装泛起。

在一些编程语言中，该功效是向量的一个基本操作。更重要地，旋转操作对应于交流相邻的差别巨细的内存块：每当拖动文件中的一块文字到其他地方时，就要求法式交流两块内存中的内容。

在许多应用场所下，运行时间和存储空间的约束会很严格。可以通过如下方式解决该问题：首先将x的前i个元素复制到一个暂时数组中，然后将余下的n－i个元素向左移动i个位置，最后将最初的i个元素从暂时数组中复制到x中余下的位置。可是，这种措施使用的i个分外的位置发生了过大的存储空间的消耗。另一种方法是界说一个函数将x向左旋转一个位置（其时间正比于n）然后挪用该函数i次。

但该方法又发生了过多的运行时间消耗。要在有限的资源内解决该问题，显然需要更庞大的法式。

有一个乐成的方法有点像精巧的杂技行动：移动x[0]光临时变量t，然后移动x[i]至x[0]，x[2i]至x[i]，依此类推（将x中的所有下标对n取模），直至返回到取x[0]中的元素，此时改为从t取值然后终止历程。当i为3且n为12时，元素按如下顺序移动。

如果该历程没有移动全部元素，就从x[1]开始再次举行移动，直到所有的元素都已经移动为止。从另外一面考察这个问题，可以获得一个差别的算法：旋转向量x其实就是交流向量ab的两段，获得向量ba。

这里a代表x中的前i个元素。假设a比b短，将b分为bl和br，使得br具有与a相同的长度。交流a和br，也就将ablbr转换为brbla。

序列a此时已处于其最终的位置，因此现在的问题就集中到交流b的两部门。由于新问题与原来的问题具有相同的形式，我们可以递归地解决之。使用该算法可以获得优雅的法式，可是需要巧妙的代码，而且要举行一些思考才气看出它的效率足够高。

问题看起来很难，除非最终获得了啊哈！灵机一动：我们将问题看做是把数组ab转换成ba，同时假定我们拥有一个函数可以将数组中特定部门的元素求逆。从ab开始，首先对a求逆，获得arb，然后对b求逆，获得arbr。最后整体求逆，获得(arbr)r。

此时就恰好是ba。于是，我们获得了如下用于旋转的代码，其中注释部门表现abcdefgh向左旋转三个位置以后的效果。

reverse(0,i-1) /* cbadefgh */reverse(i,n-1) /* cbahgfed */reverse(0,n-1) /* defghabc */Doug McIlroy3给出了将十元数组向上旋转5个位置的翻手例子。初始时掌心对着我们的脸，左手在右手上面。

翻转代码在时间和空间上都很高效，而且代码很是简短，很难堕落。Brian Kernighan4和P. J. Plauger5在其1981年出书的Software Tools in Pascal一书中，就使用该代码在文本编辑器中实现了行的移动。Kernighan陈诉称在第一次执行的时候法式就正确运行了，而他们先前基于链表的处置惩罚相似任务的代码则包罗几个错误。该代码用在几个文本处置惩罚系统中，其中包罗我最初用于录入本章内容的文本编辑器。

Ken Thompson6在1971年编写了编辑器和这种求逆代码，甚至在那时就主张把该代码看成一种知识。4　排序现在我们来讨论问题C。

给定一本英语单词字典（每个输入行是一个由小写字母组成的单词），要求找出所有的变位词分类。研究这个问题可以举出许多理由。首先是技术上的：获得这个问题的解决方案需要既具有正确的视角又能使用正确的工具。

第二个理由更具有说服力：你总不想成为聚会中唯一一个不知道“deposit”、“dopiest”、“posited”和“topside”是变位词的人吧？解决这个问题的许多方法都出奇地低效和庞大。任何一种思量单词中所有字母的排列的方法都注定了要失败。单词“cholecystoduodenostomy”（我的字典中单词“duodenocholecystostomy”的一个变位词）有22！种排列，少量的乘法运算讲明22! ≈ 1.1241021。纵然假设以闪电一样的速度每百亿分之一秒执行一种排列，这也要消耗1.1109 秒。

履历规则“π秒就是一个纳世纪”指出1.1109是数十年。而比力所有单词对的任何方法在我的机械上运行至少要花费一整夜的时间——在我使用的字典里有约莫230 000个单词，而纵然是一个简朴的变位词比力也将花费至少1 微秒的时间，因此，总时间估算起来就是230 000单词230 000比力/单词1微秒/比力=52 900106微秒=52 900秒≈14.7小时你能够找到同时制止上述缺陷的方法吗？我们获得的啊哈！灵机一动 就是标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。然后，将所有具有相同标识的单词集中在一起。

这将原始的变位词问题简化为两个子问题：选择标识和集中具有相同标识的单词。在进一步阅读之前，先好好想想这些问题。

对第一个问题，我们可以使用基于排序的标识7：将单词中的字母根据字母表顺序排列。“deposit”的标识就是“deiopst”，这也是“dopiest”和其他任何在该类中的单词的标识。

要解决第二个问题，我们将所有的单词根据其标识的顺序排序。我所知道的关于该算法的最好形貌就是Tom Cargill的翻手表现：先用一种方式排序（水平翻手），再用另一种方式排序（垂直翻手）。5　原理排序 排序最显而易见的用处是发生有序的输出，该输出既可以是系统规范要求的一部门，也可以是另一个法式（也许是一个二分搜索法式）的前期准备事情。可是在变位词问题中，排序并不是关注的焦点。

排序是为了将相等的元素（本例中为标识）集中到一起。这些标识发生了另外一个排序应用：将单词内字母排序使得同一个变位词类中的单词具有尺度型。

通过给每条记载添加一个分外的键，并根据这些键举行排序，排序函数可以用于重新排列磁盘文件中的数据。在第三部门，我们还会多次回首排序这个主题。二分搜索 该算法在有序表中查找元素时极为高效，而且可用于内存排序或磁盘排序。

唯一的缺陷就是整个表必须已知而且事先排好序。基于该简朴算法的思想在许多应用法式中都有应用。

标识 当使用等价关系来界说类时，界说一种标识使得类中的每一项都具有相同的标识，而该类以外的其他项则没有该标识，这是很有用的。对单词中的字母排序可以发生一个用于变位词类的标识。

其他标识通过排序给出。然后使用一个计数来代表重复的次数（于是标识“mississippi”可以写成“i4m1p2s4”或将1省略——“i4mp2s4”）。也可以使用一个包罗26个整数的数组来标识每个字母泛起的次数。

标识的其他应用包罗：美国联邦观察局用来索引指纹的方法，以及用来识别读音相同可是拼写差别的名字的Soundex启发式方法：Knuth8在其The Art of Computer Programming, Volume 3: Sorting and Sear ching9一书的形貌了Soundex方法。问题界说。确定用户的真实需求是法式设计的基础。

本文的中心思想是问题界说的下一步：使用哪些基本操作来解决问题？在每个例子中，啊哈！灵机一动都界说了一个新的基本操作使得问题获得简化。问题解决者的看法。优秀法式员都有点懒：他们坐下来并等候灵机一动的泛起而不急于使用最开始的想法编程。

固然，这必须通过在适当的时候开始写代码来加以平衡。真正的技术就在于对这个适其时候的掌握，这只能泉源于解决问题和反思谜底所获得的履历。

6　习题1．思量查找给定输入单词的所有变位词问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处置惩罚字典，又会如何？2．给定包罗4 300 000 000个32位整数的顺序文件，如何找出一个泛起至少两次的整数？3．前面涉及了两个需要精巧代码来实现的向量旋转算法。

将其划分作为独立的法式实现。在每个法式中，i和n的最大条约数如何泛起？4．几位读者指出，既然所有的三个旋转算法需要的运行时间都正比于n，杂技算法的运行速度显然是求逆算法的两倍。

杂技算法对数组中的每个元素仅存储和读取一次，而求逆算法需要两次。在实际的盘算机上举行实验以比力两者的速度差异，特别注意内存引用位置四周的问题。

5．向量旋转函数将向量ab变为ba。如何将向量abc变为cba？（这对交流非相邻内存块的问题举行了建模）。6．20世纪70年月末期，贝尔实验室开发出了“用户操作的电话号码簿辅助法式”，该法式允许雇员使用尺度的按键电话在公司电话号码簿中查找电话号码。要查找该系统设计者的名字Mike Lesk10，可以按“LESKM”（也就是“53756”），随后，系统会输出他的电话号码。

这样的服务现在随处可见。该系统中泛起的一个问题是，差别的名字有可能具有相同的按键编码。在Lesk的系统中发生这种情况时，系统会询问用户更多的信息。

给定一个大的名字文件（例如尺度的大都会电话号码簿），如何定位这些“错误匹配”呢？（当Lesk在这种规模的电话号码簿上做实验时，他发现错误匹配发生的概率仅仅是0.2%。）如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数？7．在20世纪60年月早期，Vic Vyssotsky与一个法式员一起事情，该法式员需要转置一个存储在磁带上的4 000×4 000的矩阵（每条记载的花样相同，为数十个字节）。他的同事最初提出的法式需要运行50个小时。

Vyssotsky如何将运行时间淘汰到半小时呢？8．[J. Ullman]给定一个n元实数荟萃、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不凌驾t？9．顺序搜索和二分搜索代表了搜索时间和预处置惩罚时间之间的折中。处置惩罚一个n元表格时，需要执行几多次二分搜索才气弥补对表举行排序所消耗的预处置惩罚时间？10．某一天，一个新研究员向托马斯·爱迪生报到。爱迪生要求他盘算出一个空灯泡壳的容积。

在使用测径仪和微积分举行数小时的盘算后，这个新员工给出了自己的谜底——150 cm3。而爱迪生在几秒钟之内就盘算完毕并给出了却果“更靠近155”。他是如何实现的呢？7　变位词法式的实现（边栏）我的变位词法式按三个阶段的“管道”组织，其中一个法式的输出文件作为下一个法式的输入文件。第一个法式标识单词，第二个法式排序标识后的文件，而第三个法式将这些单词压缩为每个变位词类一行的形式。

下面是一个仅有6个单词的字典的处置惩罚历程。输出包罗三个变位词类。

下面的C语言sign法式假定没有凌驾100个字母的单词，而且输入文件仅包罗小写字母和换行符。（因此我使用了一个一行的下令对字典举行预处置惩罚，将其中的大写字母改为小写字母。）int charcomp(char *x, char *y) { return *x - *y;}#define WORDMAX 100int main(void){ char word[WORDMAX], sig[WORDMAX]; while (scanf("%s", word) !=EOF) { strcpy(sig, word); qsort(sig, strlen(sig), sizeof(char), charcomp); printf("%s %sn", sig, word); } return 0;}while循环每次读取一个字符串到word中，直至文件末尾为止。

strcpy函数复制输入单词到单词sig中，然后挪用C尺度库函数qsort对单词sig中的字母举行排序（参数是待排序的数组、数组的长度、每个待排序项的字节数以及比力两个项的函数名。在本例中，待比力项为单词中的字母）。

最后，printf语句依次打印标识、单词自己和换行符。系统sort法式将所有具有相同标识的单词归拢到一起。

squash法式在同一行中将其打印出来。int main(void){ char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX]; int linenum = 0; strcpy(oldsig, ""); while (scanf("%s %s", sig, word) != EOF) { if (strcmp(oldsig, sig) !=0 && linenum >0) printf("n"); strcpy(oldsig, sig); linenum++; printf("%s ", word); } printf("n"); return 0;}大部门事情都是使用第二个printf语句来完成的。对每一个输入行，该语句输出第二个字段，后面跟一个空格。

if语句捕捉标识之间的差异。如果sig与oldsig（其上一次的值）差别，那么就打印换行符（文件中的第一条记载除外）。最后一个printf输出最后一个换行符。在使用小输入文件对这些简朴部门举行测试后，我通过下面的下令构建了变位词列表：sign <dictionary | sort | squash >gramlist该下令将文件dictionary输入到法式sign，毗连sign的输出至sort，毗连sort的输出至squash，并将squash的输出写入文件gramlist。

法式的运行时间为18秒：sign用时4秒、sort用时11秒而squash用时3秒。我在一个包罗230 000个单词的字典上运行了该法式。然而，不包罗众多的-s和-ed后缀。以下是一些很有趣的变位词类。

subessential suitablenesscanter creant cretan nectar recant tanrec trancecaret carte cater crate creat creta react recta tracedestain instead sainted satinedadroitly dilatory idolatry least setal slate stale steal stela talesreins resin rinse risen serin sirenconstitutionalism misconstitutional1Martin Gardner（1914—），美国著名的科普作家，主持《科学美国人》的数学游戏专栏25年，写作了大量文章和图书，有世界影响。——编者注2即循环移位。

——审校者注3 Doug McIlroy（1932—），著名盘算机科学家，美国工程院院士，现为达特茅斯学院兼职教授。他于1968年第一个提出了软件组件的观点。他到场设计了PL/I和C++语言、Multics和Unix操作系统。

Unix上许多工具是他开发的，包罗diff、echo、sort、spell和join等，管道实现也由他首创。他曾恒久担任贝尔实验室盘算技术研究部主任，并曾任ACM图灵奖主席。——编者注4 Brian Kernighan（1942—）著名盘算机科学家，现为普林斯顿大学教授。他与人互助缔造了Awk和AMPL编程语言，对Unix和C语言的设计也有很大孝敬。

他还与人合写了多部盘算机名著，包罗与Ritchie合著的The C Programming Language。——编者注5 P. J. Plauger，著名C/C++语言专家，现为著名尺度库开发商Dinkumware总裁。他曾担任ISO C尺度委员会卖力人，著有名著《C尺度库》（中文版由人民邮电出书社出书）。

——编者注6 Ken Thompson（1943—），著名盘算机科学家，1983年图灵奖得主。现为Google良好工程师。

他是Unix操作系统的主要设计者，并设计了C语言的前身B语言。——编者注7 该变位词算法是由许多人各自独立发现的，至少可以追溯到20世纪60年月中期。8 Don Knuth（1938—），中文名高德纳，著名盘算机科学家，斯坦福大学荣休教授。因对算法分析和编程语言设计领域的孝敬获1974年图灵奖。

他是名著The Art of Computer Programming的作者，设计了TEX排版系统。——编者注9 该书第2版英文影印版已由清华大学出书社引收支版，中文书名《盘算机法式设计艺术 第3卷 排序和查找》，中译版已由国防工业出书社出书，中文书名《盘算机法式设计艺术 第3卷 排序与查找》。——编者注10 Mike Lesk，著名法式员，ACM会士，美国工程院院士，现任Rutgers大学教授兼系主任。他在贝尔实验室事情期间开发了大量工具，包罗lex、uucp和stdio.h的前身。

他向导了美国NSF数字图书馆计划，该计划支持了斯坦福大学搜索引擎研究项目，促生了Google。——编者注本文节选自《编程珠玑（第2版•修订版）》内容简介本书是盘算机科学方面的经典名著。

书的内容围绕法式设计人员面临的一系列实际问题展开。作者Jon Bentley以其独占的洞察力和缔造力，引导读者明白这些问题并学会解决方法，而这些正是法式员实际编程生涯中至关重要的。本书的特色是通过一些经心设计的有趣而又颇具指导意义的法式，对实用法式设计技巧及基本设计原则举行了透彻而睿智的形貌，为庞大的编程问题提供了清晰而完备的解决思路。

本书对各个条理的法式员都具有很高的阅读价值。

本文来源：im体育 官网-www.021pop.com