前兩個(gè)星期就看編程之美的一摞烙餅排序問題，剛開始看其代碼沒看懂什么意思，后來看了人家的博客才知道是怎么回事了，自己寫了一遍其代碼做各種各樣的測(cè)試，嚇我一跳，一個(gè)剪枝操作竟然省了那么多的時(shí)間，想起上一道題的將帥問題，頓時(shí)讓我領(lǐng)悟到這編程之美的書籍，題目不但有意思，其代碼真的優(yōu)雅和美，好了接下來看這個(gè)烙餅排序問題。
題目：
星期五的晚上，一幫同事在希格瑪大廈附近的“硬盤酒吧”多喝了幾杯。程序員多喝了幾杯之后談什么呢？自然是算法問題。有個(gè)同事說：“我以前在餐館打工，顧客經(jīng)常點(diǎn)非常多的烙餅。店里的餅大小不一，我習(xí)慣在到達(dá)顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一只手托著盤子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個(gè)個(gè)兒，反復(fù)幾次之后，這摞烙餅就排好序了。我后來想，這實(shí)際上是個(gè)有趣的排序問題：假設(shè)有n塊大小不一的烙餅，那最少要翻幾次，才能達(dá)到最后大小有序的結(jié)果呢？”
你能否寫出一個(gè)程序，對(duì)于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過程呢？
編程之美的代碼：

class CprefixSorting {public://初始化CprefixSorting(){mCakecnt=0;mMaxSwap=0;};//釋放數(shù)組內(nèi)存空間virtual ~CprefixSorting(){if(mCakeArray!=NULL)delete mCakeArray;if(mReverseCakeArraySwap!=NULL)delete mReverseCakeArraySwap;if(mSwapArray!=NULL)delete mSwapArray;if(mReverseCakeArray!=NULL)delete mReverseCakeArray;};//最大的上界int UpperBound(int mCakecnt){//這里修正了編程之美的上界return 2*(mCakecnt-1);}//最小的下界int LowerBound(int *reverseCake,int cakeCnt ){int t;int reverseCnt=0;//統(tǒng)計(jì)最少需要翻轉(zhuǎn)的次數(shù)for(int i=1;i<cakeCnt;i++){//判斷是否相鄰t=reverseCake[i]-reverseCake[i-1];if(t==1||t==-1){}else{reverseCnt++;}}return reverseCnt;}//判斷烙餅是否排好序bool IsSorted(int* reverseCakeArray,int cakeCnt ){for(int i=1;i<cakeCnt;i++){if(reverseCakeArray[i-1]>reverseCakeArray[i]){return false;}}return true;}//初始化信息void Init(int * cakeArray,int cakeCnt){assert(cakeArray!=NULL);assert(cakeCnt>0);mCakecnt=cakeCnt;mCakeArray=new int[mCakecnt];assert(mCakeArray!=NULL);for(int i=0;i<mCakecnt;i++){mCakeArray[i]=cakeArray[i];}//設(shè)置最大存儲(chǔ)空間mMaxSwap=UpperBound(mCakecnt);mSwapArray=new int[mMaxSwap+1];assert(mSwapArray!=NULL);mReverseCakeArray=new int[mCakecnt];for(int i=0;i<mCakecnt;i++){mReverseCakeArray[i]=mCakeArray[i];}mReverseCakeArraySwap=new int[mMaxSwap];}//排序的核心函數(shù)void Search(int step){//存儲(chǔ)最小搜索次數(shù)int lowCnt;mSearch++;lowCnt=LowerBound(mReverseCakeArray,mCakecnt);//這里也修正了編程之美的剪枝//當(dāng)當(dāng)前的搜索和最小的下界若比前面最小次數(shù)的還要大//就停止搜索，以便減少時(shí)間的開銷//這剪枝是遞歸分支限界法的核心if(step+lowCnt>mMaxSwap||step>=mMaxSwap){return;}if(IsSorted(mReverseCakeArray,mCakecnt)){if(step<mMaxSwap){mMaxSwap=step;for(int i=0;i<mCakecnt;i++){mSwapArray[i]=mReverseCakeArraySwap[i];}}return;}//遍歷遞歸進(jìn)行翻轉(zhuǎn)for(int i=1;i<mCakecnt;i++){//翻轉(zhuǎn)Reserver(0,i);//儲(chǔ)存當(dāng)前搜索值對(duì)應(yīng)翻轉(zhuǎn)月餅的索引mReverseCakeArraySwap[step]=i;//搜索下一個(gè)節(jié)點(diǎn)Search(step+1); // printf("step:%d\n",step+1); // for(int j=0;j<mCakecnt;j++) // { // printf("%d ",mReverseCakeArray[j]); // } // printf("\n");//返回上一層Reserver(0,i);}}//翻轉(zhuǎn)烙餅信息void Reserver(int begin,int end){for(int i=begin,j=end;i<j;i++,j--){int t=mReverseCakeArray[i];mReverseCakeArray[i]=mReverseCakeArray[j];mReverseCakeArray[j]=t;}}//運(yùn)行函數(shù)接口void Run(int *cakeArray,int cakeCnt){Init(cakeArray,cakeCnt);mSearch=0;Search(0);}void Output(){for(int i=0;i<mMaxSwap;i++){//輸出每層翻轉(zhuǎn)其烙餅的索引printf("%d ",mSwapArray[i]);}//輸出搜索次數(shù)printf("\n |Search Times : %d\n",mSearch);//輸出需翻轉(zhuǎn)最少的次數(shù)printf("Total Swap times= %d\n",mMaxSwap);}private:int * mCakeArray;//儲(chǔ)存對(duì)應(yīng)索引烙餅大小信息數(shù)組int mCakecnt;//烙餅的個(gè)數(shù)int mMaxSwap;//烙餅的最大交換次數(shù)int * mReverseCakeArray;//儲(chǔ)存當(dāng)前翻轉(zhuǎn)后對(duì)應(yīng)索引烙餅的大小信息int mSearch; //當(dāng)前搜索次數(shù)int * mReverseCakeArraySwap;//儲(chǔ)存當(dāng)前對(duì)應(yīng)搜索值的被翻轉(zhuǎn)的烙餅索引int * mSwapArray;//存儲(chǔ)已經(jīng)完全排好序的所有對(duì)應(yīng)搜索值得被烙餅索引 };#endif // CPREFIXSORTING_H int main() {CprefixSorting test;int aa[3]={3,1,2};test.Run(aa,3);test.Output(); }

運(yùn)行結(jié)果：
2 1
|Search Times : 19
Total Swap times= 2
剪枝操作的關(guān)鍵就是看其上界和下界兩個(gè)邊界，如果下界越大，上界越小其運(yùn)行效率越高，測(cè)試：
修改上界值較大(調(diào)整更大的上界)：
//最大的上界
int UpperBound(int mCakecnt)
{
return 2*mCakecnt;
}
運(yùn)行結(jié)果
2 1
|Search Times : 31
修改下界值較小(調(diào)整更小的下界)
lowCnt=-1;
運(yùn)行結(jié)果：
2 1
|Search Times : 31
Total Swap times= 2
從結(jié)果可以看出，上界和下界的數(shù)值對(duì)其所搜次數(shù)的影響，這里如果你傳入的數(shù)組數(shù)目越多，影響會(huì)更明顯的，因?yàn)檫@里涉及了一種搜索樹的結(jié)構(gòu)，該樹深度越高，樹的節(jié)點(diǎn)就越多，越密集那么消耗的時(shí)間的次數(shù)就越高，這時(shí)利用分支限界法(即巧妙的利用邊界才停止其往下搜索)，控制搜索深度，這樣就可以大大的減少時(shí)間效率了，如圖：

參考博客：
http://blog.csdn.net/zuiaituantuan/article/details/6056601

總結(jié)

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

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