問題描述： 有一摞烙餅，因為一只手端著盤子，所以只能用另外一只手來給烙餅排序，將烙餅由大到小排好序。這樣就要求我們在給烙餅排序的時候總是將最上面的N個烙餅一起翻轉(zhuǎn)。如果最下面的烙餅是最大的，那么只需要解決上面的N-1個烙餅，同理可以最后到解決兩個烙餅的排序。

簡單的排序方法：先找到最大的烙餅，將其和其以上的烙餅一起翻轉(zhuǎn)，這樣最大的烙餅就在盤子的最上面了，然后翻轉(zhuǎn)所有的烙餅，這樣最大的烙餅就在盤子的最下面了。同樣的，處理剩下的N-1個烙餅，知道最后所有的烙餅都排好序?？梢灾牢覀冏疃嘈枰M(jìn)行2*（N-1）次翻轉(zhuǎn)就可以將所有的烙餅排好序。

問題？ 如果減少烙餅的反轉(zhuǎn)次數(shù)，達(dá)到一個最優(yōu)的解。 加入這堆老兵中有幾個不同的部分相對有序，憑直接來猜測，可以把笑一下的烙餅進(jìn)行翻轉(zhuǎn)，每次考慮翻轉(zhuǎn)烙餅的時候總是把相鄰的烙餅盡可能的放到一起。

解決方法： 通過窮舉法來找所有可能方案中的最優(yōu)方案，自然會用到動態(tài)規(guī)劃或者遞歸的方法來實現(xiàn)?？梢詮牟煌姆D(zhuǎn)策略開始，比如第一次先翻最小的，然后遞歸的把所有的可能都全部翻轉(zhuǎn)一次。

既然2（N-1）是一個最多的翻轉(zhuǎn)次數(shù)，就可以得知，如果算法中的翻轉(zhuǎn)次數(shù)超過了2（N-1），我們就應(yīng)該放棄這個算法。

我們總是希望UpperBound越小越好，而LowerBound則越大越好，這樣就可以盡可能的減少搜索的次數(shù)，是算法的性能更好。

代碼如下：（代碼可能需要仔細(xì)的閱讀，才能明白算法的含義）

#pragma once
class CPrefixSorting
{
public:
	~CPrefixSorting(void);
	CPrefixSorting()
	{
		m_nCakeCnt=0;
		m_nMaxSwap=0;
	}

	// 計算烙餅翻轉(zhuǎn)信息
	// @param
	// pCakeArray  存儲烙餅索引數(shù)組
	// nCakeCnt    烙餅個數(shù)
	// 
	void Run(int* pCakeArray, int nCakeCnt)
	{
		Init(pCakeArray,nCakeCnt);
		m_nSearch=0;
		Search(0);
	}

	// 輸出烙餅的翻轉(zhuǎn)次數(shù)，翻轉(zhuǎn)信息
	void Output()
	{
		for(int i=0;i<m_nMaxSwap;i++)
		{
			printf("%d",m_SwapArray[i]);
		}
		printf("\n |Search Times|:%d\n",m_nSearch);
		printf("Total Swap times=%d\n",m_nMaxSwap);
	}

private:
	int* m_CakeArray;    // 烙餅信息數(shù)組
	int m_nCakeCnt;      // 烙餅的個數(shù)
	int m_nMaxSwap;      // 最多交換次數(shù)，根據(jù)前面的推斷，最多為m_nCakeCnt*2
	int* 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ù)信息

	// 初始化數(shù)組信息
	// @param
	// pCakeArray   存儲烙餅索引數(shù)組
	// nCakeCnt     烙餅個數(shù)
	//
	void Init(int* pCakeArray,int nCakeCnt)
	{
		m_nCakeCnt=nCakeCnt;

		// 初始化烙餅數(shù)組
		m_CakeArray=new int[m_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+1];

		// 初始化中間交換結(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];
	}

	// 翻轉(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ù)組的排序信息情況來判斷最少需要交換多少次
		for(int i=1;i<nCakeCnt;i++)
		{
			// 判斷位置相鄰的兩個烙餅是否為尺寸排序上相等的
			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++;

		// 估算當(dāng)前搜索所需要的最小的交換次數(shù)
		nEstimate=LowerBound(m_ReverseCakeArray,m_nCakeCnt);
		if(step+nEstimate>m_nMaxSwap)
		{
			return;
		}

		// 如果已經(jīng)排好序，即翻轉(zhuǎn)完成后，輸出結(jié)果
		if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
		{
			if(step<m_nMaxSwap)
			{
				m_nMaxSwap=step;// 修改最大的翻轉(zhuǎn)次數(shù)，讓m_nMaxSwap記錄最小的翻轉(zhuǎn)次數(shù)
				for(i=0;i<m_nMaxSwap;i++)
				{
					m_SwapArray[i]=m_ReverseCakeArraySwap[i];
				}
			}
			return;
		}

		// 遞歸進(jìn)行翻轉(zhuǎn)
		for(i=1;i<m_nCakeCnt;i++)
		{
			Reverse(0,i);
			m_ReverseCakeArraySwap[step]=i;
			Search(step+1);
			Reverse(0,i);
		}
	}

	// 判斷是否已經(jīng)排好序
	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)烙餅信息
	// 非常經(jīng)典的數(shù)組翻轉(zhuǎn)算法
	void Reverse(int nBegin,int nEnd)
	{
		int i,j,t;
		for(i=nBegin,j=nEnd;i<j;i++,j--)
		{
			t=m_ReverseCakeArray[i];
			m_ReverseCakeArray[i]=m_ReverseCakeArray[j];
			m_ReverseCakeArray[j]=t;
		}
	}
};

// CPrefixSorting.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "PrefixSorting.h"

using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"--->begin"<<endl;
	CPrefixSorting panCakeSort;
	int panCake[5]={3,5,1,4,2};
	panCakeSort.Run(panCake,5);
	panCakeSort.Output();
	return 0;
}

// CPrefixSorting.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "PrefixSorting.h"

using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"--->begin"<<endl;
	CPrefixSorting panCakeSort;
	int panCake[5]={3,5,1,4,2};
	panCakeSort.Run(panCake,5);
	panCakeSort.Output();
	return 0;
}

輸出的結(jié)果為：