• 題目描述
• 代碼實現

題目描述

有一摞烙餅，大小不一，編號大小表示了其大小。現在我們需要把這一摞烙餅進行排序，使得從上到下越來越大。但是排序能夠進行的操作只有抓起一摞餅進行上下翻轉。比如一摞餅是[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

總結

以上是生活随笔為你收集整理的一摞烙饼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。