準(zhǔn)備好了嗎把兩個(gè)數(shù)分割叫做什么？我們開(kāi)始答題吧！

　　Q1：入門(mén)

　　嘗試用編程解決問(wèn)題

　　難度系數(shù)：★

　　優(yōu)秀的掃地機(jī)器人

　?。↖Q：80 目標(biāo)時(shí)間：20分鐘）

　　現(xiàn)在有很多制造商都在賣(mài)掃地機(jī)器人把兩個(gè)數(shù)分割叫做什么，它非常有用把兩個(gè)數(shù)分割叫做什么，能為忙碌的我們分擔(dān)家務(wù)負(fù)擔(dān)。不過(guò)我們也很難理解為什么掃地機(jī)器人有時(shí)候會(huì)反復(fù)清掃某一個(gè)地方。

　　假設(shè)有一款不會(huì)反復(fù)清掃同一個(gè)地方的機(jī)器人把兩個(gè)數(shù)分割叫做什么，它只能前后左右移動(dòng)。舉個(gè)例子，如果第1 次向后移動(dòng)，那么連續(xù)移動(dòng)3 次時(shí)，就會(huì)有以下9 種情況（ 圖6 ）。又因?yàn)榈? 次移動(dòng)可以是前后左右4 種情況，所以移動(dòng)3 次時(shí)全部路徑有9×4 ＝ 36 種。

　　※ 最初的位置用0 表示，其后的移動(dòng)位置用數(shù)字表示。

　　問(wèn)題：

　　求這個(gè)機(jī)器人移動(dòng)12 次時(shí)，有多少種移動(dòng)路徑？

　　Q2：初級(jí)

　　解決簡(jiǎn)單問(wèn)題體會(huì)算法效果

　　難度系數(shù)：★★

　　朋友的朋友也是朋友嗎

　?。↖Q：90目標(biāo)時(shí)間：25分鐘）

　　“六度空間理論”非常有名。大概的意思是1 個(gè)人只需要通過(guò)6 個(gè)中間人就可以和世界上任何1 個(gè)人產(chǎn)生間接聯(lián)系。本題將試著找出數(shù)字的好友（這里并不考慮親密指數(shù)）。

　　假設(shè)擁有同樣約數(shù)（不包括1）的數(shù)字互為“好友”，也就是說(shuō)，如果兩個(gè)數(shù)字的最大公約數(shù)不是1，那么稱這兩個(gè)數(shù)互為好友。

　　從1~N 中任意選取一個(gè)“合數(shù)”，求從它開(kāi)始，要經(jīng)歷幾層好友，才能和其把兩個(gè)數(shù)分割叫做什么他所有的數(shù)產(chǎn)生聯(lián)系（所謂的“合數(shù)”是指“有除1 以及自身以外的約數(shù)的自然數(shù)”）。

　　舉個(gè)例子，N ＝ 10 時(shí)，1~10 的合數(shù)是4、6、8、9、10 這5 個(gè)。

　　如果選取的是10，那么10 的好友數(shù)字就是公約數(shù)為2 的4、6、8這3 個(gè)。而9 是6 的好友數(shù)字（公約數(shù)為3），所以10 只需要經(jīng)過(guò)2 層就可以和9 產(chǎn)生聯(lián)系（圖5 ）。如果選取的是6，則只需經(jīng)過(guò)1 層就可以聯(lián)系到4、8、9、10 這些數(shù)字。因此N ＝ 10 時(shí)，無(wú)論最初選取的合數(shù)是什么，最多經(jīng)過(guò)2 層就可以與其他所有數(shù)產(chǎn)生聯(lián)系。

　　問(wèn)題：

　　求從1~N 中選取7 個(gè)合數(shù)時(shí)，最多經(jīng)過(guò)6 層就可以與其他所有數(shù)產(chǎn)生聯(lián)系的最小的N。

　　Q3：中級(jí)

　　優(yōu)化算法實(shí)現(xiàn)高速處理

　　難度系數(shù)：★★★

　　優(yōu)雅的IP 地址

　?。↖Q：100 目標(biāo)時(shí)間：30分鐘）

　　可能大部分讀者都清楚，IPv4 中的IP 地址是二進(jìn)制的32 位數(shù)值。不過(guò)，這樣的數(shù)值對(duì)我們?nèi)祟?lèi)而言可讀性比較差，所以我們通常會(huì)以8 位為1 組分割，用類(lèi)似192.168.1.2 這種十進(jìn)制數(shù)來(lái)表示它（ 圖12 ）。

　　這里，我們思考一下十進(jìn)制數(shù)0~9 這10 個(gè)數(shù)字各出現(xiàn)1 次的IP 地址（像正常情況一樣，省略每組數(shù)字首位的0。也就是說(shuō)，不能像192.168.001.002 這樣表示，而要像192.168.1.2 這樣來(lái)表示）

　　問(wèn)題：

　　求用二進(jìn)制數(shù)表示上述形式的IP 地址時(shí)，能使二進(jìn)制數(shù)左右對(duì)稱的IP 地址的個(gè)數(shù)（用二進(jìn)制數(shù)表示時(shí)不省略0，用完整的32 位數(shù)表示）。

　　Q4：高級(jí)

　　改變思路讓程序速度更快

　　難度系數(shù)：★★★★

　　異性相鄰的座次安排

　?。↖Q：130 目標(biāo)時(shí)間：60分鐘）

　　回想起學(xué)生時(shí)期調(diào)座位的時(shí)候，我們的心里總是會(huì)小鹿亂撞。想必很多人都對(duì)誰(shuí)會(huì)坐自己旁邊這件事莫名地激動(dòng)吧？

　　這里我們考慮一種“前后左右的座位上一定都是異性”的座次安排。也就是說(shuō)，像圖26 右側(cè)那樣，前后左右都是同性的座次安排是不符合要求的（男生用藍(lán)色表示，女生用灰色表示）。

　　問(wèn)題：

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

　　答案及解析

　　Q1-Q4

　　Q1解題思路

　　用坐標(biāo)(0, 0) 表示最初的位置。從這個(gè)原點(diǎn)開(kāi)始，避開(kāi)已經(jīng)走過(guò)的坐標(biāo)，使機(jī)器人前進(jìn)。用深度優(yōu)先搜索就可以實(shí)現(xiàn)邏輯，如代碼清單08.01 所示。

　　Q1答案

　　324932種。

　　Q2解題思路

　　要解決這個(gè)問(wèn)題，首先要正確理解問(wèn)題中出現(xiàn)的詞。首先是“合數(shù)”。

　　其次是“公約數(shù)”這個(gè)詞。小學(xué)的時(shí)候，我們就做過(guò)求最大公約數(shù)的題。公約數(shù)的意思就是“共同的約數(shù)”。這里，擁有共同約數(shù)的數(shù)字互為“好友”，那么就需要求最大公約數(shù)非1 的情況。

　　從1~N 中選取7 個(gè)合數(shù)，且“最多經(jīng)過(guò)6 層”，那么可以得知，我們要找的是“由2 個(gè)數(shù)相乘得到的數(shù)字”的組合。這樣的話，乘法運(yùn)算中的這2 個(gè)數(shù)就會(huì)成為公約數(shù)。

　　舉個(gè)例子，選出a~h 這些數(shù)。簡(jiǎn)單地說(shuō)就是，當(dāng)7 個(gè)數(shù)字分別是以下的形式時(shí)，經(jīng)過(guò)6 層就能與其他所有數(shù)產(chǎn)生聯(lián)系。

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

　　※這里a~h 這些數(shù)字必須“互質(zhì)”。

　　Point！

　　更進(jìn)一步考慮，也可以像本題中的例子一樣，把第1 個(gè)數(shù)字設(shè)置成“平方數(shù)”（即4），也就是說(shuō)變成下面這樣的組合更好。

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

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

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

　　用Ruby 可以像代碼清單19.01 這樣實(shí)現(xiàn)。

　　Q2答案

　　55

　　滿足條件的組合為：

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

　　Q3解題思路

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

　　要想求左右對(duì)稱的二進(jìn)制數(shù)，可以通過(guò)把16 位的二進(jìn)制數(shù)逆序排列，并將結(jié)果與該16 位的二進(jìn)制數(shù)本身拼合，即生成32 位數(shù)來(lái)求得。因?yàn)槭?6 位，所以全量搜索時(shí)只需要遍歷65536 種情況即可。

　　然后，把這個(gè)二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)，分別使用0~9 這10 個(gè)數(shù)字各1 次即可。

　　用Ruby 實(shí)現(xiàn)時(shí)，代碼如代碼清單40.01 所示。

　　執(zhí)行程序可得到正確答案“8”，因而符合條件的IP 地址有8 個(gè)，如表4 所示。

　　Point！

　　用十進(jìn)制數(shù)表示的時(shí)候，如果以點(diǎn)號(hào)分割的各部分左右對(duì)稱，那么整體也就左右對(duì)稱，因而只需要調(diào)查0~255 這些數(shù)對(duì)應(yīng)的二進(jìn)制數(shù)中左右對(duì)稱的數(shù)就可以了。也就是說(shuō)，A.B.C.D 這種形式中，A 要和D 對(duì)稱，B 要和C 對(duì)稱。

　　下面我們?cè)囍页鯝~D 的各種組合中，0~9 這10 個(gè)數(shù)字各使用1次的組合。每組（A, D）,（ B, C）生成的IP地址有8 種情況，所以用組合數(shù)乘以8 就可以求出結(jié)果。

　　用Ruby 實(shí)現(xiàn)時(shí)，代碼如代碼清單40.02 所示。

　　Q3答案

　　8個(gè)。

　　Q4解題思路

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

　　這里，我們事先準(zhǔn)備好要排除的座次安排，統(tǒng)計(jì)不在這個(gè)范圍內(nèi)的座次安排即可。用Ruby 實(shí)現(xiàn)時(shí)，如代碼清單68.01 所示。

　　要想改善處理速度，就要考慮“如何縮小搜索范圍”。基本的辦法不外乎“剪枝”和“內(nèi)存化”。

　　這里，我們事先準(zhǔn)備前2 排的座次安排，然后生成下一排可能的安排，并遞歸地搜索下去。同時(shí)，把已經(jīng)搜索過(guò)的結(jié)果保存到內(nèi)存中，避免重復(fù)搜索（代碼清單68.02）。

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