《程式設計之美——微軟技術面試心得》一摞烙餅的排序初體驗

《程式設計之美》讀書筆記：1.3 一摞烙餅的排序

問題：

    星期五的晚上，一幫同僚在希格瑪大廈附近的“硬碟酒吧”多喝了幾杯。程式員多喝了幾杯之後談什麼呢？自然是算法問題。有個同僚說：“我以前在餐館打工，顧客經常點非常多的烙餅。店裡的餅大小不一，我習慣在到達顧客飯桌前，把一摞餅按照大小次序擺好——小的在上面，大的在下面。由于我一隻手托着盤子，隻好用另一隻手，一次抓住最上面的幾塊餅，把它們上下颠倒個個兒，反複幾次之後，這摞烙餅就排好序了。我後來想，這實際上是個有趣的排序問題：假設有n塊大小不一的烙餅，那最少要翻幾次，才能達到最後大小有序的結果呢？”

你能否寫出一個程式，對于n塊大小不一的烙餅，輸出最優化的翻餅過程呢？

初步分析：

1、使用動态規劃來解決，然而不能很快找出狀态轉移方程，暫時放棄。 2、從上到下，從上往下确定目前序列的有序程度（升序、降序），當遇到違背有序的程度的元素的時候， 判斷該元素是否在這個有序序列區間範圍， 1）若在這個有序序列區間範圍，則将該違背有序元素和有序序列一起翻轉 2）若不在這個有序序列範圍，則将違背有序元素上面的有序序列進行翻轉 3）當該元素與序列邊界元素相同，則判斷該元素下一個元素以确定序列類型 舉例子： 輸入樣例： 5  5 2 3 7 1 樣例分析： 從上往下分析5->2目前序列是降序的，邊界範圍是[5,2]，當遇到3的時候，發現違背目前有序類型（降序），并且3在這個有序序列中，是以翻轉這個有序序列和這個元素，得出 3 2 5 7 1 從頭再次判斷該序列，評估該序列有序類型3->2（降序），邊界範圍是[3,2]，當遇到5的時候，發現違背目前有序類型（降序），因為5不在這個有序序列，是以将違背有序元素上面的有序序列進行翻轉，得出 2 3 5 7 1 從頭再次判斷該序列，評估該序列有序類型3->7（升序），邊界範圍[3,7]，當遇到1的時候，發現違背目前有序類型（降序），因為1不在這個有序序列，是以将違背有序元素上面的有序序列進行翻轉，得出 7 5 3 2 1 從頭再次判斷該序列，評估該序列有序類型7->1（降序），但是題目要求序列最終有序類型是升序，是以整個序列再次翻轉一次，得出 1 2 3 5 7

/*
把一摞餅按照大小次序擺好——從小到大，小在上，大在下
隻能用一隻手，一次抓住最上面的幾塊餅，把他們上下颠倒個個兒，
反複幾次之後，排好序
假設有n塊大小不一的烙餅，最少翻轉幾次，才能達到大小有序的結果？
*/
#define  _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printData(int val)
{
	cout << val << " ";
}
void init_bin(vector<int> &v)
{
	int n;//需要排序的餅的數目
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}
}

void sort_bin(vector<int> &v)
{
	while (1)
	{
		bool flag ;//排序标記
		int pStart = 1;//預設開始周遊的下标為2
		if (v[1] == v[0])
		{
			while (v[pStart] == v[pStart - 1] && pStart < v.size())pStart++;//若元素相同，則判斷下一個
		}
		flag = v[pStart]>v[pStart - 1];//确定目前排序類型（升序、降序）
		bool next = flag;
		for (int i = pStart + 1; i < v.size(); i++)
		{
 			while (v[i] == v[i - 1] && i < v.size())i++;
			next = v[i]>v[i - 1];//确定目前元素與上一個比較後是升序還是降序
			if (next==flag)//與原本序列違背
				continue;
 			auto _Start = &v[0];
			int *_End;
			//while (v[i] == v[0] && i < v.size())i++;
			if (flag ==v[i] > v[0]&& v[i] != v[0])
			{
				_End = &v[i];
			}
			else
			{
				_End = &v[i - 1];
			}
			reverse(_Start, _End+1);
			for_each(v.begin(), v.end(), printData); cout << endl;
			break;
		}//for
		if (next==flag&&flag)break;
		else if (next == flag&&flag == false)
		{
			reverse(v.begin(), v.end());
			for_each(v.begin(), v.end(), printData); cout << endl;
		}
	}//while
}

int main(void)
{
	vector<int> v;
	init_bin(v);
	
	sort_bin(v);
	cout << endl;
	system("pause");
	return 0;
}
           

存在問題： 隻分析上方有序程度，但是該序列其他部分有序程度并沒有分析 比如 10 3 2 1 6 5 4 9 8 7 0 這個樣例就存在着部分區域有序的現象，[3,1] [6,4] [9,7][0]，而這種情況的話，上述程式在6的時候已經分析錯誤了，要修改，請大神指教。