1.3 一摞烙餅的排序

參考《編程之美–1.3 一摞烙餅的排序》
問題描述：
一摞亂序擺放的烙餅，每次只能抓取最上面幾塊烙餅并翻轉，多次翻轉后能夠實現烙餅的從小到大（從上往下）的有序擺放。
問題分析：
這里我們使用回溯法解決這個問題。直接用回溯法效率是低下的，因此要進行剪枝。這里的剪枝條件是利用翻轉次數的上界和下界完成的。
上界：
[4,2,1,5,3] -> [5,1,2,4,3] -> [3,4,2,1,5]
兩步可以按大小順序將某塊餅放到它應該在的位置。
同理，可以把其他四塊烙餅擺放好，要注意最后一塊烙餅會在最后第二塊烙餅擺放正確后位于正確位置。假設烙餅個數為n，則翻轉次數上界為2（n-1）。
下界：
上界我們已經得出了，下面考慮下界。在試驗翻轉的時候，我們可以發現，當烙餅堆部分有序時，翻轉次數較少。若一摞烙餅中有m對相鄰的烙餅半徑不相鄰，理想情況下需要m次翻轉來排序，[3,4,2,1,5,6]，此時就需要兩次來翻轉。

代碼如下：

#include <iostream> #include <windows.h> #include <math.h> #include <assert.h>using namespace std;class PreFixSorting { public:PreFixSorting(){CakeCount = 0;MaxSwap = 0;}~PreFixSorting(){if(CakeArray != NULL){delete CakeArray;}if(SwapArray != NULL){delete SwapArray;}if(ReverseCakeArray != NULL){delete ReverseCakeArray;}if(ReverseCakeArraySwap != NULL){delete ReverseCakeArraySwap;}}//計算烙餅翻轉信息//@param//pCakeArray 存儲烙餅索引數組，索引大的烙餅個頭大//pCakeCount 烙餅個數void Run(int* pCakeArray, int pCakeCount){Init(pCakeArray, pCakeCount);nSearch = 0;Search(0);}void Output(){for(int i = 0; i < MaxSwap; i++){cout<<SwapArray[i]<<" ";}cout<<'\n'<<"|Search Times|: "<<nSearch<<endl;cout<<"Total Swap Times = "<<MaxSwap<<endl;}private://初始化數組信息//@param//pCakeArray 存儲烙餅索引數組，索引大的烙餅個頭大//pCakeCount 烙餅個數void Init(int *pCakeArray, int pCakeCount){assert(pCakeArray != NULL);assert(pCakeCount > 0);CakeCount = pCakeCount;//初始化烙餅數組CakeArray = new int[CakeCount];assert(CakeArray != NULL);for(int i = 0; i < CakeCount; i++){CakeArray[i] = pCakeArray[i];}//獲取最多交換次數MaxSwap = UpperBound(CakeCount);//初始化交換結果數組SwapArray = new int[MaxSwap + 1];assert(SwapArray != NULL);//初始化中間交換結果數組ReverseCakeArray = new int[CakeCount];for(int i = 0; i < CakeCount; i++){ReverseCakeArray[i] = CakeArray[i];}ReverseCakeArraySwap = new int[MaxSwap];}//尋找當前翻轉上界int UpperBound(int pCakeCount){return (pCakeCount-1)*2;}//尋找當前翻轉下界int LowerBound(int* pCakeArray, int pCakeCount){int t, ret = 0;//根據當前數組排序情況判斷最少需要交換的次數for(int i = 1; i < pCakeCount; i++){//判斷位置相鄰的兩個烙餅是否索引相鄰t = pCakeArray[i] - pCakeArray[i-1];if((t == 1) || (t == -1)){}else{ret++ ;}}return ret;}//排序主函數void Search(int step){int i, nEstimate;nSearch++;//估算交換次數下界nEstimate = LowerBound(ReverseCakeArray, CakeCount);if(step + nEstimate > MaxSwap ){return;}//若已排好序則輸出結果if(IsSorted(ReverseCakeArray, CakeCount)){if(step < MaxSwap){MaxSwap = step;for(int i = 0; i < MaxSwap; i++){SwapArray[i] = ReverseCakeArraySwap[i];}return;}}//回溯法遞歸翻轉for(i = 1; i < CakeCount; i++){Reverse(0, i);ReverseCakeArraySwap[step] = i;Search(step + 1);Reverse(0, i);}}//true： 已排序//false： 未排序bool IsSorted(int* pCakeArray, int pCakeCount){for(int i = 1; i < pCakeCount; i++){if(pCakeArray[i-1] > pCakeArray[i]){return false;}}return true;}//翻轉烙餅數組void Reverse(int nBegin, int nEnd){assert(nEnd > nBegin);int i, j, t;for(i = nBegin, j = nEnd; i < j; i++, j--){t = ReverseCakeArray[i];ReverseCakeArray[i] = ReverseCakeArray[j];ReverseCakeArray[j] = t;}}private:int* CakeArray; //烙餅數組int CakeCount; //烙餅個數int MaxSwap; //交換次數上界int* SwapArray; //翻轉烙餅結果數組（翻轉前幾層烙餅，用于輸出）int* ReverseCakeArray; //當前轉烙餅數組（中間狀態）int* ReverseCakeArraySwap; //當前翻轉烙餅結果數組int nSearch; //當前搜索次數 };int main() {PreFixSorting pfs;int CakeArray[] = {4,2,1,5,3};int CakeCount = 5;pfs.Run(CakeArray,CakeCount);pfs.Output();return 0;}

注意： 關于這里的上下界，其實目前研究的結果是上界最小為(5n+5)/3向上取整，下界最大為15n/14向上取整。用這個上下界的搜索次數更少，效率更高（n較大時）。

總結

以上是生活随笔為你收集整理的1.3 一摞烙饼的排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。