Author: Fox

首先聲明：本人沒有解決掉這個問題。

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

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

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

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

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

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

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

1) 相似點★：

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

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

2) 不同處★：

a. 漢諾塔有多出來的兩根針，翻烙餅只有一只手，明確說明沒有第三只手；

b. 漢諾塔一次只能移動一個，翻烙餅沒限制；

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

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

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

a. Input : n.

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

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

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

我最開始想到的是：這一摞烙餅其實就是一個雙鏈表，每翻一次相當于將頭節(jié)點H與某非頭節(jié)點N進行如下變換：

H->next = N->next

N->prior = H->prior = NULL

N->next->prior = H

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

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

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

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

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

師：然也。

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

整個鏈表的形態(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é)點的prior，H、C節(jié)點的next，其他節(jié)點不變。

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

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

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

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

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

冒泡排序思想：

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

師：要使大頭在后，應使大頭在后。

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

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

俗：USA, CNN（操你娘）。

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

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

師：然也。

Fox：O, my God！整點實際的吧！整個過程分為n輪，在第i(i=0, 1, ..., n-1)輪：

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

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

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

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

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

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

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

快速排序思想：

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

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

我只好自己重新考慮局部有序之后的問題。

十分鐘后，我有了如下的答案（目前我能想到的最佳答案），但不得不承認，表述算法比給出一種情況對應的解要麻煩的多的多的多，假定A、B滿足A==B-1，即A、B為相鄰數(shù)列（為簡單記，元素和數(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>。

對應操作規(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)：如果當前只剩A、B兩個子列，則翻轉(zhuǎn)一次成A(O)B(O)1 2 3 4為最終結(jié)果，否則，認為B(C)A(C)可以作為一個逆序有序數(shù)列考慮，暫時無需翻轉(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可以作為一個有序數(shù)列考慮，如果當前只有A、B兩個子列，則正序序列A(O)B(O)1 2 3 4為最終結(jié)果。

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