Author: Fox

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

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

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

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

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

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

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

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

1) 相似點★：

a. 都要不斷調整位置，最終實現從小到大排好；

b. 都要借助中間量進行調整。

2) 不同處★：

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

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

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

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

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) 存儲結構★★★：

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

H->next = N->next

N->prior = H->prior = NULL

N->next->prior = H

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

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

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

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

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

師：然也。

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

整個鏈表的形態如下：

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節點的prior，H、C節點的next，其他節點不變。

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

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

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

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

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

冒泡排序思想：

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

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

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

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

俗：USA, CNN（操你娘）。

師：翻轉。既不在前，也不在后，使之在前，使之在后。

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

師：然也。

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

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

b. 是否大頭在后？是，轉f；

c. 是否大頭在前？是，轉e；

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

e. 將隊頭n-i與第n-i個元素對調，++times；

f. ++i，轉a；

g. 輸出序列（0, 1, ..., n）和翻轉次數times；OVER:D。

快速排序思想：

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

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

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

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

對應操作規則如下：

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兩個子列，則翻轉一次成A(O)B(O)1 2 3 4為最終結果，否則，認為B(C)A(C)可以作為一個逆序有序數列考慮，暫時無需翻轉；

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可以作為一個有序數列考慮，如果當前只有A、B兩個子列，則正序序列A(O)B(O)1 2 3 4為最終結果。

上面規則的制定其實是反向導出的，遵循的原則是，正序有序的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個有序子列是可行的，但對于完全無序的數列，分析出所有有序子列，既不現實，也無必要。

修改規則如下：當隊頭無序&&相鄰數列有序||隊頭有序，翻轉隊頭；否則，將隊頭連同該元素一同翻轉。

由此可見，這算法還要改進：

a. 判斷Array[0]是否正序連續（連續個數nNum1），如果nNum1==n，轉i，如果nNum1!=1，轉c；

b. 判斷Array[0]是否逆序連續（連續個數nNum1），如果nNum1==n，翻轉Array，轉f；

c. 從下標nNum1開始查找Array[0]+1（bObserve = true）和Array[0]-1（bObserve = false）的下標nStart2，如果nNum1==nStart2，bOrder1==true，轉e，如果nNum1!=1，置nEnd2=nStart2；

d. 判斷( bObserve == true&&Array[nStart2]+1==Array[nStart2+1] ) || ( bObserve == false&&Array[nStart2]==Array[nStart2+1]+1 )，true則置nEnd2=nStart2，false則置nEnd2=nStart2+1；

e. 翻轉Array[0] to Array[nEnd2]，轉a；

f. 輸出Array及times。

這樣來看，改進后的算法竟簡單了許多！

不幸的是：按上面給出的算法翻轉合并1 3 5 6 4 8 7 9 2 0：

1 3 5 6 4 8 7 9| 2| 0

2 9 7 8 4 6 5| 3| 1 0

3 5 6| 4| 8 7 9 2 1 0

4 6| 5| 3 8 7 9 2 1 0

5 6| 4 3 8 7 9 2 1 0

6 5 4 3 8| 7| 9 2 1 0

7 8 3 4 5| 6| 9 2 1 0

進入死循環了……

很明顯應該是下面這個樣子：

1 3 5 6 4 8 7 9 2| 0

9 8 7 4 6 5| 3 1 2 0

5 6 4| 7 8 9 3 1 2 0

6 5 4 7| 8 9 3 1 2 0

4 5 6 7 8 9 3| 1 2 0

3 4 5 6 7 8 9 1 2| 0

1 9 8 7 6 5 4 3 2| 0

2 3 4 5 6 7 8 9 1| 0

9 8 7 6 5 4 3 2 1 0|

0 1 2 3 4 5 6 7 8 9

執行9次翻轉。算法如何得到呢？

a. 確定最小無序完整子集Sn（Sn中含n>1個連續數）；

b. 將Sn最前面的有序子集So（o>1）加以考慮，一個子集？兩個子集？

______________________________________________________________________________

O, my God!

這個問題，從前天晚上到現在，思考、分析、抽象了至少有15個小時以上了：

a. Apr.18th-19th: 23:00 - 01:30

b. Apr.19th: 11:00 - 13:00

c. Apr.19th-20th: 22:00 - 05:30

d. Apr.20th: 11:00 - 15:00

結果是，到現在無法給出一個最優的翻轉算法。一個周末都花在這上面了，準備放棄L。

LP催著我讓我回學校，是該回去了！