游戲人生

Author: Fox

首先聲明：本人沒有解決掉這個(gè)問(wèn)題。

相比第一道讓CPU占用率曲線聽你指揮對(duì)Windows系統(tǒng)中CPU占有率概念的考察和對(duì)API的使用，以及第二道中國(guó)象棋將帥問(wèn)題對(duì)抽象建模的考察。這道題目才算是一道算法題吧？之前那兩道尤其是中國(guó)象棋將帥問(wèn)題總有點(diǎn)腦筋急轉(zhuǎn)彎的味道。

題目：星期五的晚上，一幫同事在希格瑪大廈附近的“硬盤酒吧”多喝了幾杯。程序員多喝了幾杯之后談什么呢？自然是算法問(wèn)題。有個(gè)同事說(shuō)：

“我以前在餐館打工，顧客經(jīng)常點(diǎn)非常多的烙餅。店里的餅大小不一，我習(xí)慣在到達(dá)顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一只手托著盤子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個(gè)個(gè)兒，反復(fù)幾次之后，這摞烙餅就排好序了。

我后來(lái)想，這實(shí)際上是個(gè)有趣的排序問(wèn)題：假設(shè)有n塊大小不一的烙餅，那最少要翻幾次，才能達(dá)到最后大小有序的結(jié)果呢？

你能否寫出一個(gè)程序，對(duì)于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過(guò)程呢？

排序問(wèn)題是數(shù)據(jù)結(jié)構(gòu)和算法中比較重要的一個(gè)了，之前在一篇被同事成為標(biāo)題黨的文章中因?yàn)樘岬脚判蛑嘘P(guān)于（非）穩(wěn)定排序的概念還被很多TX鄙視了一番，甚至引來(lái)人身攻擊，現(xiàn)在想來(lái)都有些后怕。

這道題目一眼看上去最先讓我想到的居然是那道經(jīng)典的漢諾塔（Tower of Hanoi）問(wèn)題（當(dāng)然，漢諾塔不算排序問(wèn)題）。

1) 相似點(diǎn)★：

a. 都要不斷調(diào)整位置，最終實(shí)現(xiàn)從小到大排好；

b. 都要借助中間量進(jìn)行調(diào)整。

2) 不同處★：

a. 漢諾塔有多出來(lái)的兩根針，翻烙餅只有一只手，明確說(shuō)明沒有第三只手；

b. 漢諾塔一次只能移動(dòng)一個(gè)，翻烙餅沒限制；

c. 漢諾塔要保證小的始終在上面，翻烙餅沒限制；

d. 漢諾塔移動(dòng)之前就有序，所以其移動(dòng)次數(shù)是固定的，算法的邏輯也固定（不管是遞歸還是棧操作），翻烙餅沒有這個(gè)前提。

3) 把題目用程序語(yǔ)言描述一下吧★：

a. Input : n.

b. Process : generate n random number 0-(n-1), sortting.

c. Output : 0, 1, ..., n-1, and move times num.

4) 存儲(chǔ)結(jié)構(gòu)★★★：

我最開始想到的是：這一摞烙餅其實(shí)就是一個(gè)雙鏈表，每翻一次相當(dāng)于將頭節(jié)點(diǎn)H與某非頭節(jié)點(diǎn)N進(jìn)行如下變換：

H->next = N->next

N->prior = H->prior = NULL

N->next->prior = H

如果使用普通的雙鏈表，這兒就有一個(gè)很明顯的問(wèn)題，H和N之間的所有節(jié)點(diǎn)（如果有的話）的前趨prior和后繼next互換了，對(duì)于n比較大的情況，這個(gè)操作明顯浪費(fèi)時(shí)間啊（交換前趨prior和后繼next和題目要求的翻幾次似乎也沒有關(guān)系吧？只是我作為一個(gè)一線的Coder考慮的太具體了）。如果摒棄前趨和后繼的概念，又該怎樣描述呢？

唐朝禪宗大師青原行思曾說(shuō)：參禪之初，看山是山，看水是水；禪有悟時(shí)，看山不是山，看水不是水；禪中徹悟，看山仍然山，看水仍然是水。

俗：日，扯那么多，什么意思？

師：前趨不是前趨，后繼不是后繼。

俗：日，前趨不是前趨，難道是后繼嗎？

師：然也。

Fox：O, my God！整點(diǎn)實(shí)際的吧！翻轉(zhuǎn)一次之后，前趨視為后繼，后繼視為前趨，第奇數(shù)次翻轉(zhuǎn)的前趨是后繼，第偶數(shù)次翻轉(zhuǎn)的后繼是前趨。

整個(gè)鏈表的形態(tài)如下：

H:Head, F:First, G:F's next, B:C's prior, C:Change, D, C's next, L:Last.

H<==>F<==>G<=...=>B<==>C<==>D<=...=>L

F與C交換的操作如下（Word、PS畫圖），n表示next，p表示prior：

這里只需要修改F、D節(jié)點(diǎn)的prior，H、C節(jié)點(diǎn)的next，其他節(jié)點(diǎn)不變。

后面想了一下，這種方式很難在不添加flag或者對(duì)換n、p的情況下正常操作，沒有找到好的方法L，如果你有好的方法不妨告訴我。

最后只好作罷，何苦呢？直接使用數(shù)組就完了嘛J！既然是數(shù)組，除了翻轉(zhuǎn)移動(dòng)麻煩一點(diǎn)，理解和操作還是很容易的。

果然不是搞數(shù)學(xué)、算法出身的，一上來(lái)考慮的就是如何存儲(chǔ)^.^''''，而不是算法本身。

更可笑的是，扯了半天，最后居然還是用數(shù)組！

5) 算法分析★★★★★：

冒泡排序思想：

最關(guān)鍵的是要抽象出隨機(jī)數(shù)列特征（含當(dāng)前和移動(dòng)后數(shù)列特征的抽象），并盡量使每一次翻轉(zhuǎn)有效（所謂有效，即盡量保證每一次操作都向最后的有序靠近而非背離 ）。

師：要使大頭在后，應(yīng)使大頭在后。

俗：日，這是什么狗屁邏輯？

師：因果。在前既是在后。

俗：USA, CNN（操你娘）。

師：翻轉(zhuǎn)。既不在前，也不在后，使之在前，使之在后。

俗：日，什么東西？既不在前，也不在后，不前不后，難道在中間啊？

師：然也。

Fox：O, my God！整點(diǎn)實(shí)際的吧！整個(gè)過(guò)程分為n輪，在第i(i=0, 1, ..., n-1)輪：

a. 找到大頭n-i，是否有序？是，轉(zhuǎn)g；

b. 是否大頭在后？是，轉(zhuǎn)f；

c. 是否大頭在前？是，轉(zhuǎn)e；

d. 將隊(duì)頭（第一個(gè)元素）與大頭n-i對(duì)調(diào)（別忘了是翻轉(zhuǎn)，中間元素也變序了），++times；

e. 將隊(duì)頭n-i與第n-i個(gè)元素對(duì)調(diào)，++times；

f. ++i，轉(zhuǎn)a；

g. 輸出序列（0, 1, ..., n）和翻轉(zhuǎn)次數(shù)times；OVER:D。

快速排序思想：

在最開始的時(shí)候，我就想到使用快速排序的思想，先使整個(gè)數(shù)列局部有序，最后調(diào)整使全部有序。悲哀的是，在我考慮 4 3 1 2這個(gè)數(shù)列的時(shí)候，我斷定還要通過(guò)上面的方式重新像冒泡排序一樣重新來(lái)過(guò)，立即放棄想法，于是給了上面的思路，而且堅(jiān)定的認(rèn)為這個(gè)方法已經(jīng)很好。結(jié)果，下午GR告訴我他的反例：4 3 1 2 --> 2 1 3 4|--> 1 2| 3 4，“|”表示從該處翻轉(zhuǎn)。

我必須承認(rèn)，這才是好的方法，我過(guò)分拘泥于不去改動(dòng)已經(jīng)有序的部分。然而，這家伙只知道反駁我，卻無(wú)法給出算法。

我只好自己重新考慮局部有序之后的問(wèn)題。

十分鐘后，我有了如下的答案（目前我能想到的最佳答案），但不得不承認(rèn)，表述算法比給出一種情況對(duì)應(yīng)的解要麻煩的多的多的多，假定A、B滿足A==B-1，即A、B為相鄰數(shù)列（為簡(jiǎn)單記，元素和數(shù)列統(tǒng)稱數(shù)列）。則A、B的組合類型有8種：B(O)A(O)、B(C)A(O)、B(O)A(C)、B(C)A(C)、A(C)B(O)、A(O)B(O)、A(C)B(C)、A(O)B(C)，O表示正向（obverse）C表示逆向（reverse），以1 2 3 4為例：

B(O)A(O)：3 4 1 2<2>、B(C)A(O)：4 3 1 2<4>、B(O)A(C)：3 4 2 1<5>、B(C)A(C)：4 3 2 1<7>；

A(C)B(C)：2 1 4 3<1>、A(O)B(C)：1 2 4 3<3>、A(C)B(O)：2 1 3 4<6>、A(O)B(O)：1 2 3 4<8>。

對(duì)應(yīng)操作規(guī)則如下：

a. 0x0101: B(O)A(O) --> B(C)A(O)； 3

b. 0x0001: B(C)A(O) --> A(C)B(O)； 2

c. 0x0101: B(O)A(C) --> B(C)A(C)；1

d. 0x0000: B(C)A(C)：如果當(dāng)前只剩A、B兩個(gè)子列，則翻轉(zhuǎn)一次成A(O)B(O)1 2 3 4為最終結(jié)果，否則，認(rèn)為B(C)A(C)可以作為一個(gè)逆序有序數(shù)列考慮，暫時(shí)無(wú)需翻轉(zhuǎn)；

e. 0x1010: A(C)B(C) --> A(O)B(C)； 3

f. 0x1110: A(O)B(C) --> B(O)A(C)；  2

g. 0x1011: A(C)B(O) --> A(O)B(O)；1

h. 0x1111: A(O)B(O)：A、B可以作為一個(gè)有序數(shù)列考慮，如果當(dāng)前只有A、B兩個(gè)子列，則正序序列A(O)B(O)1 2 3 4為最終結(jié)果。

上面規(guī)則的制定其實(shí)是反向?qū)С?/strong>的，遵循的原則是，正序有序的A(O)B(O)和逆序有序的B(C)A(C)可以看作一個(gè)序列，A(C)B(O)、B(O)A(C)可一步達(dá)到，B(C)A(O)、A(O)B(C)可兩步達(dá)到，B(O)A(O)、A(C)B(C)可三步達(dá)到。即對(duì)于4個(gè)元素，最壞的的A(C)B(C)需要4步（對(duì)應(yīng)于上面的冒泡法卻只需要3步L）。而且當(dāng)元素比較多的時(shí)候，記住1、2個(gè)有序子列是可行的，但對(duì)于完全無(wú)序的數(shù)列，分析出所有有序子列，既不現(xiàn)實(shí)，也無(wú)必要。