《程式設計珠玑（第2版•修訂版）》—第2章2.1節三個問題

本節書摘來自異步社群《程式設計珠玑（第2版•修訂版）》一書中的第2章2.1節三個問題，作者【美】jon bentley，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

第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”互為變位詞，因為每一個單詞都可以通過改變其他單詞中字母的順序來得到。