第2章 啊哈！算法
编程珠玑（第2版•修订版）
研究算法给实际编程的程序员带来许多好处。算法课教给学生完成重要任务的方法和解决新问题的技术。在后续的章节中将会看到，先进的算法工具有时候对软件系统影响很大——减少开发时间，同时使执行速度更快。
算法与其他那些深奥的思想一样重要，但在更一般的编程层面上具有更重要的影响。在《啊哈!灵机一动》一书中（本章的标题就借鉴了它），Martin Gardner①描述了深得我心的一个思想：“看起来很困难的问题也可以有一个简单的、意想不到的答案。”与高级的方法不同，算法的啊哈！灵机一动并非只有在大量的研究以后才能出现；任何愿意在编程之前、之中和之后进行认真思考的程序员都有机会捕捉到这灵机一动。
2.1 三个问题
好了，泛泛的话讲得够多啦。本章将围绕三个小问题展开。在继续阅读以前，请先试着解决它们。
A．给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
B．将一个n元一维向量向左旋转②i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转?
C．给定一个英语字典，找出其中的所有变位词集合。例如，“pots”、“stop”和“tops”互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。
时间： 2024-09-20 05:39:18