14萬程序員挑戰過的演算法趣題

想知道比爾蓋茨的編程水平嗎？點擊下面的標題

講真，比爾·蓋茨的編程水平究竟怎麼樣？

計算機的世界每天都在發生著深刻的變化。新操作系統的發布、CPU性能的提升、智能手機和平板電腦的流行、存儲介質的變化、雲的普及……這樣的變化數不勝數。

在這樣日新月異的時代中，「演算法」是不變的重要基石。要編寫高效率的程序，就需要優化演算法。無論開發工具如何進化，熟識並能靈活運用演算法仍然是對程序員的基本要求。

本文為那些已經學習過排序、搜索等知名演算法，並想要學習更多有趣的演算法，進一步提升編程技巧的工程師準備了四道數學謎題形式的問題。這四道趣題分入門、初級、中級、高級，四種級別。

程序員都想挑戰這四道演算法趣題！通過挑戰你也可以看到自己大體處於哪個級別。

在挑戰之前，先介紹下問題的具體形式：

每個問題大致分為「問題」和「詳解」兩部分。

請各位先通讀問題描述，並動手編寫程序嘗試解題。在這個過程中，具體的實現方法是其次，更重要的是思考「通過哪些步驟來實現才能夠解決問題」。

每個問題都有思路講解和源代碼示例。請留意自己編程時在處理速度、可讀性等方面進行的優化，和本文的源代碼示例有什麼不同。如果事先看了思路講解和答案，就會失去解題的樂趣，所以這裡建議大家先編程解題，再看講解。

為了大家更好的享受解題樂趣，把「詳解」和「答案」放在了最後。

難度係數：★

優秀的掃地機器人

現在有很多製造商都在賣掃地機器人，它非常有用，能為忙碌的我們分擔家務負擔。不過我們也很難理解為什麼掃地機器人有時候會反覆清掃某一個地方。

假設有一款不會反覆清掃同一個地方的機器人，它只能前後左右移動。舉個例子，如果第1 次向後移動，那麼連續移動3 次時，就會有以下9 種情況（ 圖6 ）。又因為第1 次移動可以是前後左右4 種情況，所以移動3 次時全部路徑有9×4 ＝ 36 種。

※ 最初的位置用0 表示，其後的移動位置用數字錶示。

朋友的朋友也是朋友嗎

「六度空間理論」非常有名。大概的意思是1 個人只需要通過6 個中間人就可以和世界上任何1 個人產生間接聯繫。本題將試著找出數字的好友（這裡並不考慮親密指數）。

假設擁有同樣約數（不包括1）的數字互為「好友」，也就是說，如果兩個數字的最大公約數不是1，那麼稱這兩個數互為好友。

從1~N 中任意選取一個「合數」，求從它開始，要經歷幾層好友，才能和其他所有的數產生聯繫（所謂的「合數」是指「有除1 以及自身以外的約數的自然數」）。

舉個例子，N ＝ 10 時，1~10 的合數是4、6、8、9、10 這5 個。

如果選取的是10，那麼10 的好友數字就是公約數為2 的4、6、8這3 個。而9 是6 的好友數字（公約數為3），所以10 只需要經過2 層就可以和9 產生聯繫（圖5 ）。如果選取的是6，則只需經過1 層就可以聯繫到4、8、9、10 這些數字。因此N ＝ 10 時，無論最初選取的合數是什麼，最多經過2 層就可以與其他所有數產生聯繫。

難度係數：★★★

優雅的IP 地址

可能大部分讀者都清楚，IPv4 中的IP 地址是二進位的32 位數值。不過，這樣的數值對我們人類而言可讀性比較差，所以我們通常會以8 位為1 組分割，用類似192.168.1.2 這種十進位數來表示它（ 圖12 ）。

這裡，我們思考一下十進位數0~9 這10 個數字各出現1 次的IP 地址（像正常情況一樣，省略每組數字首位的0。也就是說，不能像192.168.001.002 這樣表示，而要像192.168.1.2 這樣來表示）

求用二進位數表示上述形式的IP 地址時，能使二進位數左右對稱的IP 地址的個數（用二進位數表示時不省略0，用完整的32 位數表示）。

難度係數：★★★★

異性相鄰的座次安排

（IQ：130 目標時間：60分鐘）

回想起學生時期調座位的時候，我們的心裡總是會小鹿亂撞。想必很多人都對誰會坐自己旁邊這件事莫名地激動吧？

這裡我們考慮一種「前後左右的座位上一定都是異性」的座次安排。也就是說，像圖26 右側那樣，前後左右都是同性的座次安排是不符合要求的（男生用藍色表示，女生用灰色表示）。

假設有一個男生和女生分別有15 人的班級，要像圖26 那樣，排出一個6×5的座次。求滿足上述條件的座次安排共多少種（前後或者左右鏡像的座次也看作不同的安排。另外，這裡不在意具體某個學生坐哪裡，只看男生和女生的座次安排）？

用坐標(0, 0) 表示最初的位置。從這個原點開始，避開已經走過的坐標，使機器人前進。用深度優先搜索就可以實現邏輯，如代碼清單08.01 所示。

324932種。

要解決這個問題，首先要正確理解問題中出現的詞。首先是「合數」。

其次是「公約數」這個詞。國小的時候，我們就做過求最大公約數的題。公約數的意思就是「共同的約數」。這裡，擁有共同約數的數字互為「好友」，那麼就需要求最大公約數非1 的情況。

從1~N 中選取7 個合數，且「最多經過6 層」，那麼可以得知，我們要找的是「由2 個數相乘得到的數字」的組合。這樣的話，乘法運算中的這2 個數就會成為公約數。

舉個例子，選出a~h 這些數。簡單地說就是，當7 個數字分別是以下的形式時，經過6 層就能與其他所有數產生聯繫。

a × b, b× c, c× d, d × e, e × f, f× g, g ×h

※這裡a~h 這些數字必須「互質」。

更進一步考慮，也可以像本題中的例子一樣，把第1 個數字設置成「平方數」（即4），也就是說變成下面這樣的組合更好。

a × a, a × b, b × c, c × d, d × e, e × f, f × g

末尾如果同樣設置成平方數就會變得更小，也就是變成下面這樣的組合。

a × a, a × b, b × c, c × d, d × e, e × f, f × f

用Ruby 可以像代碼清單19.01 這樣實現。

55

滿足條件的組合為：

[4, 26, 39, 33, 55, 35, 49]

按照題意，用十進位數表示時要使用0~9 這10 個數字各1 次，那麼最高位是除0 以外的9 種情況，而其他各個數位可分別使用0~9 這10個數字各1 次，其排列組合一共9!（9 的階乘）種，所以總共要遍歷9×9! 種，也就是3265920 種情況。

要想求左右對稱的二進位數，可以通過把16 位的二進位數逆序排列，並將結果與該16 位的二進位數本身拼合，即生成32 位數來求得。因為是16 位，所以全量搜索時只需要遍歷65536 種情況即可。

然後，把這個二進位數轉換成十進位數，分別使用0~9 這10 個數字各1 次即可。

用Ruby 實現時，代碼如代碼清單40.01 所示。

執行程序可得到正確答案「8」，因而符合條件的IP 地址有8 個，如表4 所示。

用十進位數表示的時候，如果以點號分割的各部分左右對稱，那麼整體也就左右對稱，因而只需要調查0~255 這些數對應的二進位數中左右對稱的數就可以了。也就是說，A.B.C.D 這種形式中，A 要和D 對稱，B 要和C 對稱。

下面我們試著找出A~D 的各種組合中，0~9 這10 個數字各使用1次的組合。每組（A, D）,（ B, C）生成的IP地址有8 種情況，所以用組合數乘以8 就可以求出結果。

用Ruby 實現時，代碼如代碼清單40.02 所示。

8個。

如果完全按照問題描述實現，只需要遍歷30 個座位中15 個男生的座次，滿足條件就OK 了。如果不考慮可擴展性、處理速度等，只需要把不符合條件的情況排除就可以了，並不是很難。

這裡，我們事先準備好要排除的座次安排，統計不在這個範圍內的座次安排即可。用Ruby 實現時，如代碼清單68.01 所示。

要想改善處理速度，就要考慮「如何縮小搜索範圍」。基本的辦法不外乎「剪枝」和「內存化」。

這裡，我們事先準備前2 排的座次安排，然後生成下一排可能的安排，並遞歸地搜索下去。同時，把已經搜索過的結果保存到內存中，避免重複搜索（代碼清單68.02）。

上面這個程序可以在2 秒左右求出正確答案。

13374192種。

作者 | 圖文來自網路、如涉及版權問題，請聯繫我們以便處理。文章內容純屬作者個人觀點，不代表本網觀點。