/*
一摞烙饼的排序:
把一摞并按照大小次序摆好，小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最
上面的几块饼。把它们上下颠倒一下，反复几次，烙饼就排好序了。
请写一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程。
分析:
每次我们只能选择最上方的一摞饼，一起翻转。不能一张一张直接抽取出来，然后进行插入，也不能交换任意两块
饼。因此，基本的排序方法不好用。
每次操作都是针对最上面的饼，如果最底层的饼已经排序，只需要处理上面的n-1个饼。问题变为n-2,n-3,...,
直到最上面的两个饼排好序。
解法1:
为了把最大的烙饼放在最下面，我们走两步:
1将最上面和最大的烙饼(包括这两张饼)一起反转
2将整坨烙饼全部翻转
之后我们对上面n-1，n-2个饼重复上述过程
经过两次反转可以把最大的烙饼翻转到最下面，最多需要把上面的n-1，
个烙饼一次翻转两次。至多需要2(n-1)次翻转就可以把所有烙饼排好序。
因为第二小的烙饼排好的时候，最小的烙饼已经在最上面了(参见冒泡)。
改进:
假如这坨烙饼中几个不同部分相对有序，我们先把小些的烙饼反转，比每次翻转最大的烙饼要快。
考虑每次翻转的时候，把原本应该相邻的烙饼换到一起，等所有烙饼都换到一起后，就完成排序了。
每次反转最大的烙饼实际上是:把最大的和次最大的交换到一起。
分析算法的主要流程:
设定了烙饼组，当前组，交换组，最终交换组，个数，最大次数，搜索次数
1原始数据赋给烙饼组，交换组，个数->最大数
2搜索：估算最小交换次数（检验相邻位置烙饼大小是否相邻），检验是否超过最大次数，检验是否已经排好序->检验是否小于最大次数->交换组赋给
最终交换组
递归翻转:从小向大翻，先逆置，在设置交换组的第几步为第几张饼。递归搜索，再逆置(?为什么)
输入:
10
3 2 1 6 5 4 9 8 7 0
输出:
4 8 6 8 4 9
172126
6
*/
/*
关键:
1 考虑每次翻转的时候，把原本应该相邻的烙饼换到一起，等所有烙饼都换到一起后，就完成排序了。
每次反转最大的烙饼实际上是:把最大的和次最大的交换到一起。
2 搜索：估算最小交换次数（检验相邻位置烙饼大小是否相邻），检验是否超过最大次数，检验是否已经排好序->检验是否小于最大次数->交换组赋给
最终交换组
递归翻转:从小向大翻，先逆置，在设置交换组的第几步为第几张饼。递归搜索，再逆置(?为什么)
3 int iMinSearchTimes = lowerBound(_pCurCakeArr,_iCakeSize);//对当前数组，判定最少的交换次数。
//在到达当前烙饼状态之前，我们已经翻转了step次，iMinSearchTimes是我们至少还需要翻转多少次才能成功
//iMinSearchTimes越大，_iMaxSwapTimes越小，越容易剪枝。总结：上界越小，下界越大，剪枝越多
if(iStep + iMinSearchTimes > _iMaxSwapTimes)//如果已经搜索的次数加上最少搜索次数仍大于最大搜索次数
//说明不符合要求，直接退出
{
return;
}
4 if(isSorted(_pCurCakeArr,_iCakeSize))//递归出口，判断当前烙饼组是否已经排好序了,把成员变量作为形参传递，难道是为了防止多线程的脏读?
{
if(iStep < _iMaxSwapTimes)//直接判断步数是否已经超过最大步数
{
_iMaxSwapTimes = iStep;//更新最大交换步数
for(int i = 0 ; i < _iMaxSwapTimes ; i++)//将当前烙饼数组赋予最终交换数组,注意这里是最大交换次数的赋值，不是烙饼大小
{
_pSwapArr[i] = _pReverseArr[i];
5 for(int i = 1 ; i < _iCakeSize ; i++)//递归主体,从小到下依次反转
{
reverse(0,i);
_pReverseArr[iStep] = i;//设定当前交换数组的当前步数为烙饼的下标,?
search(iStep+1);
reverse(0,i);//?为什么最后还要搞一次逆置
6 int CakeSort<T>::upperBound(int iCakeSize)//最多交换次数为2*n
7 for(int i = 1 ; i < iCakeSize ; i++)//最少的交换次数=判断相邻两个烙饼之间交换次数
{
int iDiff = pArrCake[i] - pArrCake[i-1];
if(iDiff == 1 || iDiff == -1)
8assert(iBeg < iEnd);//注意，逆置数组的时候要注意判定开始位置要小于结束位置,本题关键是逆置而非排序
*/
#include <stdio.h>
#include <assert.h>
#include <boost/shared_ptr.hpp>
#include <boost/shared_array.hpp>
using namespace std;
using namespace boost;
const int MAXSIZE = 12;
typedef shared_array<int> ptrArr;
template<typename T>
class CakeSort
{
public:
CakeSort();
~CakeSort();
void run(int* pCakeArr,int iCakeSize);
void init(int* pCakeArr,int iCakeSize);
int upperBound(int iCakeSize);
void search(int iStep);
//int lowerBound(int* pArrCake,int iCakeSize);
//int lowerBound(ptrArr pArrCake,int iCakeSize);
int lowerBound(T pArrCake,int iCakeSize);
//bool isSorted(int* pArrCake,int iCakeSize);
//bool isSorted(ptrArr pArrCake,int iCakeSize);
bool isSorted(T pArrCake,int iCakeSize);
void reverse(int iBeg,int iEnd);
void output();
private:
int _iCakeSize;//烙饼个数
int _iSearchTimes;//搜索次数
int _iMaxSwapTimes;//最多交换次数
//int* _pCakeArr;//烙饼组
//int* _pCurCakeArr;//当前组
//int* _pReverseArr;//中间交换组
//int* _pSwapArr;//最终交换组
ptrArr _pCakeArr;//烙饼组
ptrArr _pCurCakeArr;//当前组
ptrArr _pReverseArr;//中间交换组
ptrArr _pSwapArr;//最终交换组
};
template<typename T>
CakeSort<T>::CakeSort()
//CakeSort::CakeSort()
{
_iCakeSize = 0;
_iMaxSwapTimes = 0;
}
template<typename T>
CakeSort<T>::~CakeSort()
//CakeSort::~CakeSort()
{
//if(_pCakeArr)
//{
// delete[] _pCakeArr;//注意删除的是指针，而不是数组,还是有疑问，因为new的是一个数组，？
//}
//if(_pCurCakeArr)
//{
// delete[] _pCurCakeArr;
//}
//if(_pReverseArr)
//{
// delete[] _pReverseArr;
//}
//if(_pSwapArr)
//{
// delete[] _pSwapArr;
//}
}
template<typename T>
void CakeSort<T>::run(int* pCakeArr,int iCakeSize)
//void CakeSort::run(int* pCakeArr,int iCakeSize)
{
init(pCakeArr,iCakeSize);
_iSearchTimes = 0;
search(0);
}
template<typename T>
void CakeSort<T>::init(int* pCakeArr,int iCakeSize)
//void CakeSort::init(int* pCakeArr,int iCakeSize)
{
assert(pCakeArr && iCakeSize >= 0);
_iCakeSize = iCakeSize;
//_pCakeArr = new int[iCakeSize];
_pCakeArr.reset(new int[iCakeSize]);
//_pCurCakeArr = new int[iCakeSize];//初始化当前烙饼数组
_pCurCakeArr.reset(new int[iCakeSize]);
//assert(_pCakeArr && _pCurCakeArr);
for(int i = 0 ; i < iCakeSize ; i++)//设定原始数据
{
_pCakeArr[i] = pCakeArr[i];
_pCurCakeArr[i] = pCakeArr[i];
}
_iMaxSwapTimes = upperBound(_iCakeSize);
//_pSwapArr = new int[_iMaxSwapTimes + 1];//初始化交换结果数组,交换结果次数等于最大次数加1?
_pSwapArr.reset(new int[_iMaxSwapTimes + 1]);
//_pReverseArr = new int[_iMaxSwapTimes];
_pReverseArr.reset(new int[_iMaxSwapTimes]);
//assert(_pSwapArr && _pReverseArr);
}
template<typename T>
int CakeSort<T>::upperBound(int iCakeSize)//最多交换次数为2*n
//int CakeSort::upperBound(int iCakeSize)
{
return 2*iCakeSize;
}
template<typename T>
void CakeSort<T>::search(int iStep)
//void CakeSort::search(int iStep)
{
_iSearchTimes++;//搜索次数累加
int iMinSearchTimes = lowerBound(_pCurCakeArr,_iCakeSize);//对当前数组，判定最少的交换次数。
//在到达当前烙饼状态之前，我们已经翻转了step次，iMinSearchTimes是我们至少还需要翻转多少次才能成功
//iMinSearchTimes越大，_iMaxSwapTimes越小，越容易剪枝。总结：上界越小，下界越大，剪枝越多
if(iStep + iMinSearchTimes > _iMaxSwapTimes)//如果已经搜索的次数加上最少搜索次数仍大于最大搜索次数
//说明不符合要求，直接退出
{
return;
}
if(isSorted(_pCurCakeArr,_iCakeSize))//递归出口，判断当前烙饼组是否已经排好序了,把成员变量作为形参传递，难道是为了防止多线程的脏读?
{
if(iStep < _iMaxSwapTimes)//直接判断步数是否已经超过最大步数
{
_iMaxSwapTimes = iStep;//更新最大交换步数
for(int i = 0 ; i < _iMaxSwapTimes ; i++)//将当前烙饼数组赋予最终交换数组,注意这里是最大交换次数的赋值，不是烙饼大小
{
_pSwapArr[i] = _pReverseArr[i];
}
}
return;//注意，这里要加return,否则就多搜索了无用功了。都已经超出最大次数了，显然是剪枝了
}
for(int i = 1 ; i < _iCakeSize ; i++)//递归主体,从小到下依次反转
{
reverse(0,i);
_pReverseArr[iStep] = i;//设定当前交换数组的当前步数为烙饼的下标,?
search(iStep+1);
reverse(0,i);//?为什么最后还要搞一次逆置
}
}
//int CakeSort::lowerBound(int* pArrCake,int iCakeSize)
template<typename T>
int CakeSort<T>::lowerBound(T pArrCake,int iCakeSize)
//int CakeSort::lowerBound(ptrArr pArrCake,int iCakeSize)
{
int iRet = 0;
for(int i = 1 ; i < iCakeSize ; i++)//最少的交换次数=判断相邻两个烙饼之间交换次数
{
int iDiff = pArrCake[i] - pArrCake[i-1];
if(iDiff == 1 || iDiff == -1)
{
}
else
{
++iRet;
}
}
return iRet;
}
//bool CakeSort::isSorted(int* pArrCake,int iCakeSize)
template<typename T>
bool CakeSort<T>::isSorted(T pArrCake,int iCakeSize)
//bool CakeSort::isSorted(ptrArr pArrCake,int iCakeSize)
{
for(int i = 1 ; i < iCakeSize ; i++)
{
if(pArrCake[i-1] > pArrCake[i])//上面大于下面
{
return false;
}
}
return true;
}
template<typename T>
void CakeSort<T>::output()//输出具体反转次数
//void CakeSort::output()
{
for(int i = 0 ; i < _iMaxSwapTimes ; i++)
{
printf("%d ",_pSwapArr[i]);
}
printf("\nSearch Times:%d\n",_iSearchTimes);
printf("Swap Times:%d\n",_iMaxSwapTimes);
}
template<typename T>
void CakeSort<T>::reverse(int iBeg,int iEnd)
//void CakeSort::reverse(int iBeg,int iEnd)
{
assert(iBeg < iEnd);//注意，逆置数组的时候要注意判定开始位置要小于结束位置
int i ,j , iTemp ;//注意，操纵的数组是当前烙饼数组,也就是所谓的反转之前当前的烙饼数组
for(i = iBeg , j = iEnd ; i < j ; i++,j--)
{
iTemp = _pCurCakeArr[i];
_pCurCakeArr[i] = _pCurCakeArr[j];
_pCurCakeArr[j] = iTemp;
}
}
void process()
{
int n;
while(EOF != scanf("%d",&n))
{
int iArr[MAXSIZE];
for(int i = 0 ; i < n ; i++)
{
scanf("%d",&iArr[i]);
}
CakeSort<ptrArr> cakeSort;
cakeSort.run(iArr,n);
cakeSort.output();
}
}
int main(int argc,char* argv[])
{
process();
getchar();
return 0;
}