Author: Fox
首先聲明：本人沒有解決掉這個(gè)問題。
相比第一道讓CPU占用率曲線聽你指揮對Windows系統(tǒng)中CPU占有率概念的考察和對API的使用，以及第二道中國象棋將帥問題對抽象建模的考察。這道題目才算是一道算法題吧？之前那兩道尤其是中國象棋將帥問題總有點(diǎn)腦筋急轉(zhuǎn)彎的味道。
題目：星期五的晚上，一幫同事在希格瑪大廈附近的“硬盤酒吧”多喝了幾杯。程序員多喝了幾杯之后談什么呢？自然是算法問題。有個(gè)同事說：
“我以前在餐館打工，顧客經(jīng)常點(diǎn)非常多的烙餅。店里的餅大小不一，我習(xí)慣在到達(dá)顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一只手托著盤子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個(gè)個(gè)兒，反復(fù)幾次之后，這摞烙餅就排好序了。
我后來想，這實(shí)際上是個(gè)有趣的排序問題：假設(shè)有n塊大小不一的烙餅，那最少要翻幾次，才能達(dá)到最后大小有序的結(jié)果呢？
你能否寫出一個(gè)程序，對于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過程呢？
排序問題是數(shù)據(jù)結(jié)構(gòu)和算法中比較重要的一個(gè)了，之前在一篇被同事成為標(biāo)題黨的文章中因?yàn)樘岬脚判蛑嘘P(guān)于（非）穩(wěn)定排序的概念還被很多TX鄙視了一番，甚至引來人身攻擊，現(xiàn)在想來都有些后怕。
這道題目一眼看上去最先讓我想到的居然是那道經(jīng)典的漢諾塔（Tower of Hanoi）問題（當(dāng)然，漢諾塔不算排序問題）。
1) 相似點(diǎn)★：
a. 都要不斷調(diào)整位置，最終實(shí)現(xiàn)從小到大排好；
b. 都要借助中間量進(jìn)行調(diào)整。
2) 不同處★：
a. 漢諾塔有多出來的兩根針，翻烙餅只有一只手，明確說明沒有第三只手；
b. 漢諾塔一次只能移動(dòng)一個(gè)，翻烙餅沒限制；
c. 漢諾塔要保證小的始終在上面，翻烙餅沒限制；
d. 漢諾塔移動(dòng)之前就有序，所以其移動(dòng)次數(shù)是固定的，算法的邏輯也固定（不管是遞歸還是棧操作），翻烙餅沒有這個(gè)前提。
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)★★★：
我最開始想到的是：這一摞烙餅其實(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è)很明顯的問題，H和N之間的所有節(jié)點(diǎn)（如果有的話）的前趨prior和后繼next互換了，對于n比較大的情況，這個(gè)操作明顯浪費(fèi)時(shí)間?。?font color=#800000>交換前趨prior和后繼next和題目要求的翻幾次似乎也沒有關(guān)系吧？只是我作為一個(gè)一線的Coder考慮的太具體了）。如果摒棄前趨和后繼的概念，又該怎樣描述呢？
唐朝禪宗大師青原行思曾說：參禪之初，看山是山，看水是水；禪有悟時(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或者對換n、p的情況下正常操作，沒有找到好的方法L，如果你有好的方法不妨告訴我。
最后只好作罷，何苦呢？直接使用數(shù)組就完了嘛J！既然是數(shù)組，除了翻轉(zhuǎn)移動(dòng)麻煩一點(diǎn)，理解和操作還是很容易的。
果然不是搞數(shù)學(xué)、算法出身的，一上來考慮的就是如何存儲^.^''''，而不是算法本身。
更可笑的是，扯了半天，最后居然還是用數(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è)過程分為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對調(diào)（別忘了是翻轉(zhuǎn)，中間元素也變序了），++times；
e. 將隊(duì)頭n-i與第n-i個(gè)元素對調(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í)候，我斷定還要通過上面的方式重新像冒泡排序一樣重新來過，立即放棄想法，于是給了上面的思路，而且堅(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)，這才是好的方法，我過分拘泥于不去改動(dòng)已經(jīng)有序的部分。然而，這家伙只知道反駁我，卻無法給出算法。
我只好自己重新考慮局部有序之后的問題。
十分鐘后，我有了如下的答案（目前我能想到的最佳答案），但不得不承認(rèn)，表述算法比給出一種情況對應(yī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>。
對應(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í)無需翻轉(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á)到。即對于4個(gè)元素，最壞的的A(C)B(C)需要4步（對應(yīng)于上面的冒泡法卻只需要3步L）。而且當(dāng)元素比較多的時(shí)候，記住1、2個(gè)有序子列是可行的，但對于完全無序的數(shù)列，分析出所有有序子列，既不現(xiàn)實(shí)，也無必要。
修改規(guī)則如下：當(dāng)隊(duì)頭無序&&相鄰數(shù)列有序||隊(duì)頭有序，翻轉(zhuǎn)隊(duì)頭；否則，將隊(duì)頭連同該元素一同翻轉(zhuǎn)。
由此可見，這算法還要改進(jìn)：
a. 判斷Array[0]是否正序連續(xù)（連續(xù)個(gè)數(shù)nNum1），如果nNum1==n，轉(zhuǎn)i，如果nNum1!=1，轉(zhuǎn)c；
b. 判斷Array[0]是否逆序連續(xù)（連續(xù)個(gè)數(shù)nNum1），如果nNum1==n，翻轉(zhuǎn)Array，轉(zhuǎn)f；
c. 從下標(biāo)nNum1開始查找Array[0]+1（bObserve = true）和Array[0]-1（bObserve = false）的下標(biāo)nStart2，如果nNum1==nStart2，bOrder1==true，轉(zhuǎn)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. 翻轉(zhuǎn)Array[0] to Array[nEnd2]，轉(zhuǎn)a；
f. 輸出Array及times。
這樣來看，改進(jìn)后的算法竟簡單了許多！
不幸的是：按上面給出的算法翻轉(zhuǎn)合并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
進(jìn)入死循環(huán)了……
很明顯應(yīng)該是下面這個(gè)樣子：
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
執(zhí)行9次翻轉(zhuǎn)。算法如何得到呢？
a. 確定最小無序完整子集Sn（Sn中含n>1個(gè)連續(xù)數(shù)）；
b. 將Sn最前面的有序子集So（o>1）加以考慮，一個(gè)子集？兩個(gè)子集？
______________________________________________________________________________
O, my God!
這個(gè)問題，從前天晚上到現(xiàn)在，思考、分析、抽象了至少有15個(gè)小時(shí)以上了：
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
結(jié)果是，到現(xiàn)在無法給出一個(gè)最優(yōu)的翻轉(zhuǎn)算法。一個(gè)周末都花在這上面了，準(zhǔn)備放棄L。
LP催著我讓我回學(xué)校，是該回去了！