一摞烙餅的排序

????有大小不一的一摞餅在你的一只手上，現(xiàn)在你需要將餅由大到小翻轉(zhuǎn)，即最大尺寸的餅在底部，最小尺寸的餅在最上面，而且你只能用一只手進(jìn)行翻轉(zhuǎn)。千言萬(wàn)語(yǔ)不如一張圖。

????上圖是三張餅的翻轉(zhuǎn)，你是否能寫出一個(gè)程序，對(duì)于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過(guò)程？
解題思路：
1、 最笨的辦法，一次翻轉(zhuǎn)一個(gè)未排序中最大的餅需要兩次翻轉(zhuǎn)，那么n個(gè)餅就需要2*（n-1）次。當(dāng)然這是最多的次數(shù)。
2、 萬(wàn)一翻轉(zhuǎn)之前部分餅的順序已經(jīng)是排好的了，如此一想，這種情況下那翻轉(zhuǎn)次數(shù)肯定會(huì)更少，但是這種情況還是比較難找。
3、 要找出最好的辦法，最笨的辦法，窮舉吧！當(dāng)然窮舉的過(guò)程為了縮短次數(shù)，當(dāng)以已經(jīng)翻轉(zhuǎn)的次數(shù)大于2*（n-1）那么那次窮舉就可以停止了。跟進(jìn)一步對(duì)當(dāng)前序列進(jìn)行翻轉(zhuǎn)次數(shù)預(yù)估，預(yù)估次數(shù)加上已翻轉(zhuǎn)次數(shù)大于2*（n-1），那么那次窮舉就可以停止了。
????窮舉的思路：上圖。從左到有是：頂端-底端。

源碼：

#include <iostream>using namespace std;class CPrefixSorting { private:int* m_CakeArray; // 烙餅信息數(shù)組int m_nCakeCnt; // 烙餅個(gè)數(shù)int m_nMaxSwap; // 最多交換次數(shù)，根據(jù)前面的推斷，這里最多為 m_nCakeCnt*2int* m_SwapArray; // 交換結(jié)果數(shù)組int* m_ReverseCakeArray; // 當(dāng)前翻轉(zhuǎn)烙餅信息數(shù)組int* m_ReverseCakeArraySwap; // 當(dāng)前翻轉(zhuǎn)烙餅交換結(jié)果數(shù)組int m_nSearch; // 當(dāng)前搜索次數(shù)信息 public:CPrefixSorting(){m_nCakeCnt = 0;m_nMaxSwap = 0;}~CPrefixSorting(){delete m_CakeArray;delete m_SwapArray;delete m_ReverseCakeArray;delete m_ReverseCakeArraySwap;}// 初始化烙餅信息：個(gè)數(shù)void init(int *pCakeArray, int nCakeCnt){// 初始化烙餅數(shù)組m_nCakeCnt = nCakeCnt;m_CakeArray = new int[nCakeCnt];for (int i = 0; i < m_nCakeCnt; ++i){m_CakeArray[i] = pCakeArray[i];}// 設(shè)置最多交換次數(shù)信息m_nMaxSwap = UpperBound(m_nCakeCnt);// 初始化交換結(jié)果數(shù)組m_SwapArray = new int[m_nMaxSwap];// 初始化中間交換結(jié)果信息m_ReverseCakeArray = new int[m_nCakeCnt];for (int i = 0; i < m_nCakeCnt; ++i){m_ReverseCakeArray[i] = m_CakeArray[i];}m_ReverseCakeArraySwap = new int[m_nMaxSwap];}void run(int*pCakeArray, int nCakeCnt){init(pCakeArray, nCakeCnt);m_nSearch = 0;search(0);}// 輸出烙餅具體翻轉(zhuǎn)次數(shù)void output(){for (int i = 0; i < m_nMaxSwap; ++i){cout << m_SwapArray[i]<<" ";}cout << endl << "|Search Times| :" << m_nSearch <<endl;cout << "Total Swap times = " << m_nMaxSwap << endl;}// 尋找當(dāng)前翻轉(zhuǎn)的上界int UpperBound(int nCakeCnt){return nCakeCnt * 2;}// 尋找當(dāng)前翻轉(zhuǎn)的下界int lowerBound(int* pCakeArray, int nCakeCnt){int t, ret = 0;// 根據(jù)當(dāng)前數(shù)組的排序信息情況來(lái)判斷最少需要交換多少次 // 要求餅大小間隔為1，故有待改進(jìn)for (int i = 1; i < nCakeCnt; ++i){// 判斷位置相鄰的兩個(gè)烙餅，是否為尺寸排序上相鄰的t = pCakeArray[i] - pCakeArray[i - 1];if (t == 1 || t == -1){}else{ret++;}}return ret;}// 排序的主函數(shù)void search(int step){int i, nEstimate;m_nSearch++;// 估算這次搜素所需的最小交換次數(shù)nEstimate = lowerBound(m_ReverseCakeArray, m_nCakeCnt); // 預(yù)估次數(shù)加已翻轉(zhuǎn)次數(shù)大于m_nMaxSwap就退出if (step + nEstimate > m_nMaxSwap)return;// 如果已經(jīng)排好序，即翻轉(zhuǎn)完成，記錄每次翻轉(zhuǎn)的餅序號(hào)if (isSorted(m_ReverseCakeArray, m_nCakeCnt)){// 記錄最少翻轉(zhuǎn)步驟if (step < m_nMaxSwap){m_nMaxSwap = step;for (i = 0; i < m_nMaxSwap; ++i){m_SwapArray[i] = m_CakeArray[m_ReverseCakeArraySwap[i]];}}return;}// 遞歸進(jìn)行翻轉(zhuǎn)for (i = 1; i < m_nCakeCnt; ++i){// 翻轉(zhuǎn)頂部餅到第i個(gè)餅reverse(0, i);// 記錄翻轉(zhuǎn)第i個(gè)餅序號(hào)m_ReverseCakeArraySwap[step] = i;// 進(jìn)行下一輪翻轉(zhuǎn)窮舉search(step + 1);//若第step+1步的翻轉(zhuǎn)失敗，回復(fù)到第step步的翻轉(zhuǎn)結(jié)果reverse(0, i);}}// 是否排好序bool isSorted(int* pCakeArray, int nCakeCnt){for (int i = 1; i < nCakeCnt; ++i){if (pCakeArray[i - 1] > pCakeArray[i]){return false;}}return true;}// 翻轉(zhuǎn)烙餅信息void reverse(int nBegin, int nEnd){int i, j, t;// 翻轉(zhuǎn)烙餅信息for (i = nBegin, j = nEnd; i < j; ++i, --j){t = m_ReverseCakeArray[i];m_ReverseCakeArray[i] = m_ReverseCakeArray[j];m_ReverseCakeArray[j] = t;}} };int main() {int CakeArray[] = {4,2,3,1,5,6,7,9,8}; //頂端-底端int size = sizeof(CakeArray) / sizeof(CakeArray[0]);CPrefixSorting a;a.run(CakeArray,size);a.output();getchar();return 0; }

總結(jié)

以上是生活随笔為你收集整理的编程之美 1.3 一摞烙饼的排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。