题目描述

有一摞烙饼，大小不一，编号大小表示了其大小。现在我们需要把这一摞烙饼进行排序，使得从上到下越来越大。但是排序能够进行的操作只有抓起一摞饼进行上下翻转。比如一摞饼是[1,3,5,2,0]，需要的结果是[0,1,2,3,5]。能够进行比如[5,3,1,2,0]，然后再翻转一次就是[0,2,1,3,5]。这种情况下，最多需要2(n-1)次翻转。

代码实现

#include "stdafx.h"
#include <iostream>
#include <cassert>using namespace std;class CPrefixSorting {
public:CPrefixSorting() : cakesCount(0), cakesArray(NULL), searchCount(0),curCakesArrayReverse(NULL), cakesArrayReverse(NULL), reversesCount(0) {}~CPrefixSorting();void Run(int *, int);private:void Init(int *, int);void Search(int *, int);void PrintResult(void);int UpperBound();int LowerBound(int *);bool IsSorted(int *);void Reverse(int *, int, int);private:int cakesCount;          // The number of cakes.int *cakesArray;     // The cakes array.int searchCount;     // The counter of search steps.int *curCakesArrayReverse;  // The current reverse information.int *cakesArrayReverse;  // The result reverse information.int reversesCount;          // The counter of reverses.
};CPrefixSorting::~CPrefixSorting() {if (cakesArray)  delete [] cakesArray;if (curCakesArrayReverse)  delete [] curCakesArrayReverse;if (cakesArrayReverse)     delete [] cakesArrayReverse;
}void CPrefixSorting::Init(int *pCakes, int cnt) {assert(NULL != pCakes && cnt > 0);cakesCount = cnt;cakesArray = new int[cakesCount];assert(NULL != cakesArray);for (int i = 0; i < cakesCount; ++i) {cakesArray[i] = pCakes[i];}reversesCount = UpperBound();curCakesArrayReverse = new int[reversesCount];assert(NULL != curCakesArrayReverse);cakesArrayReverse = new int[reversesCount];assert(NULL != cakesArrayReverse);searchCount = 0;
}int CPrefixSorting::UpperBound() {return 2 * cakesCount;
}int CPrefixSorting::LowerBound(int *pCakesArray) {int count = 0;for (int i = 0; i < cakesCount - 1; ++i){int diff = pCakesArray[i] - pCakesArray[i + 1];if (-1 != diff && 1 != diff){++count;}}return count;
}bool CPrefixSorting::IsSorted(int *pCakesArray)
{for (int i = 0; i < cakesCount - 1; ++i){if (pCakesArray[i] > pCakesArray[i + 1]){return false;}}return true;
}void CPrefixSorting::Reverse(int *pCakesArray, int start, int end)
{assert(start < end);while (start < end){int tmp = pCakesArray[start];pCakesArray[start] = pCakesArray[end];pCakesArray[end] = tmp;++start;--end;}
}void CPrefixSorting::Search(int *pCakesArray, int step)
{++searchCount;if (LowerBound(pCakesArray) + step >= reversesCount){return;}if (IsSorted(pCakesArray) && step < reversesCount){reversesCount = step;for (int i = 0; i < reversesCount; ++i){cakesArrayReverse[i] = curCakesArrayReverse[i];cout << curCakesArrayReverse[i] << "  ";}cout << endl;return;}for (int i = 1; i < cakesCount; ++i){int *cakesArrayTmp = new int[cakesCount];assert(NULL != cakesArrayTmp);for (int j = 0; j < cakesCount; ++j){cakesArrayTmp[j] = pCakesArray[j];}Reverse(cakesArrayTmp, 0, i);curCakesArrayReverse[step] = i;Search(cakesArrayTmp, step + 1);if (cakesArrayTmp){delete [] cakesArrayTmp;}}
}void CPrefixSorting::PrintResult()
{cout << "The search times is " << searchCount << endl;cout << "The least reverse times is " << reversesCount << endl;cout << "The reverse process is:" << endl;for (int i = 0; i < reversesCount; ++i){cout << cakesArrayReverse[i] << "  ";}cout << endl;
}void CPrefixSorting::Run(int *pCakes, int cnt)
{// 初始化 Init(pCakes, cnt);// 搜索Search(cakesArray, 0);// 打印结果PrintResult();
}int _tmain(int argc, _TCHAR* argv[])
{// 需要排列的数组int arry[] = {6, 8, 9, 5, 1, 7, 11, 10, 2, 3, 4, 12};CPrefixSorting prefixSorting;prefixSorting.Run(arry, sizeof(arry) / sizeof(arry[0]));return 0;
}

对于三个饼，一个全焦、一个半焦、一个完好。第一面是焦，那么是全焦的概率为： 2/3。

参考链接：

http://blog.csdn.net/yahohi/article/details/7448676