程式設計之美-1.3-烙餅排序問題

問題描述：

烙餅問題可以簡化為對一段由n個無重複的整數組成的無序數組a[n]進行排序。排序要求每次隻能對a[0]~a[i]部分的數組進行翻轉（0 < i < n），最終完成排序。

輸入：數組大小n；n個整數。

輸出：最小遞歸查找次數m；每次翻轉位置j0j1…jm-1。

問題思考：

烙餅排序這部分，主要考量的是對遞歸函數的使用。

而搜尋上界與搜尋下界則可以一定程度上提高代碼的運作效率，減少搜尋次數。

遞歸流程如下：

①首先進行0~i的翻轉

②記錄第step步翻轉位置i

③然後進行下一層翻轉

④調用遞歸傳回之後，再進行一次0~i的翻轉，保持數組進入本次循環時的順序

①i++，進行0~i+1的翻轉

…

for (int i = 1; i < m_nCakeCnt; i++)
{
	Revert(0, i);
	m_ReverseCakeArraySwap[step] = i;
	Search(step + 1);
	Revert(0, i);
}
           

稍微修改代碼之後可以發現，最小翻轉的解并不是唯一的。

測試輸入：10，{ 5, 9, 4, 1, 2, 0, 8, 7, 6, 3 }

輸出有效最優解：

14849278

15183931

15218393

15839312

19385312

19465853

19484278

19615285

|Search Times| : 159193

Total Swap times = 8

完整代碼如下：

#include <stdio.h>
#include "stdafx.h"
#include "afx.h"

class CPrefixsorting
{
public:

	CPrefixsorting()
	{
		m_nCakeCnt = 0;
		m_nMaxSwap = 0;
	}

	void Run(int* pCakeArray, int nCakeCnt)
	{
		Init(pCakeArray, nCakeCnt);

		m_nSearch = 0;
		Search(0);
	}

	//輸出烙餅具體翻轉的次數
	void Output()
	{
		for (int i = 0; i < m_nCakeCnt; i++)
		{
			printf("%d", m_ReverseCakeArray[i]);
		}
		printf("\n");
		for (int i = 0; i < m_nMaxSwap; i++)
		{
			printf("%d", m_SwapArray[i]);
			printf("\n");
			Revert(0, m_SwapArray[i]);
			for (int i = 0; i < m_nCakeCnt; i++)
			{
				printf("%d", m_ReverseCakeArray[i]);
			}
			printf("\n");
		}

		printf("\n |Search Times| : %d\n", m_nSearch);
		printf("Total Swap times = %d\n", m_nMaxSwap);
	}
private:
	//初始化數組資訊
	void Init(int* pCakeArray, int nCakeCnt)
	{
		ASSERT(pCakeArray != NULL);
		ASSERT(nCakeCnt > 0);

		m_nCakeCnt = nCakeCnt;

		//初始化烙餅數組
		m_CkaeArray = new int[m_nCakeCnt];
		ASSERT(m_CkaeArray != NULL);
		for (int i = 0; i < m_nCakeCnt; i++)
		{
			m_CkaeArray[i] = pCakeArray[i];
		}

		//設定最多交換次數資訊
		m_nMaxSwap = upBound(m_nCakeCnt);

		//初始化交換結果數組
		m_SwapArray = new int[m_nMaxSwap];
		ASSERT(m_SwapArray != NULL);

		//初始化中間交換結果資訊
		m_ReverseCakeArray = new int[m_nCakeCnt];
		for (int i = 0; i < m_nCakeCnt; i++)
		{
			m_ReverseCakeArray[i] = m_CkaeArray[i];
		}
		m_ReverseCakeArraySwap = new int[m_nMaxSwap];
	}

	//尋找翻轉上界
	int upBound(int nCakeCnt)
	{
		return nCakeCnt * 2;
	}

	//尋找翻轉下界
	int LowerBound(int* pCakeArray, int nCakeCnt)
	{
		int t, ret = 0;

		//根據目前數組的排序資訊情況來判斷至少需要交換多少次
		for (int i = 1; i < nCakeCnt; i++)
		{
			//判斷位置相鄰的兩個烙餅，是否為尺寸排序上相鄰的
			t = pCakeArray[i] - pCakeArray[i - 1];
			if ((t == 1) || (t == -1))
			{
			}
			else
			{
				ret++;
			}
		}
		return ret;
	}

	//排序主函數
	void Search(int step)
	{
		int i, nEstimate;

		m_nSearch++;

		//估算這次搜算所需要的最小交換次數
		nEstimate = LowerBound(m_ReverseCakeArray, m_nCakeCnt);
		if (step + nEstimate > m_nMaxSwap)
		{
			return;
		}

		//如果已經排好序，即翻轉完成，輸出結果
		if (IsSorted(m_ReverseCakeArray, m_nCakeCnt))
		{
			if (step <= m_nMaxSwap)
			{
				m_nMaxSwap = step;
				for (i = 0; i < m_nMaxSwap; i++)
				{
					m_SwapArray[i] = m_ReverseCakeArraySwap[i];
					printf("%d", m_SwapArray[i]);
				}
				printf("\n");
			}
			return;
		}

		//遞歸進行翻轉
		for (int i = 1; i < m_nCakeCnt; i++)
		{
			Revert(0, i);
			m_ReverseCakeArraySwap[step] = i;
			Search(step + 1);
			Revert(0, i);
		}
	}

	bool IsSorted(int* pCakeArray, int nCakeCnt)
	{
		for (int i = 1; i < nCakeCnt; i++)
		{
			if (pCakeArray[i - 1] > pCakeArray[i])
			{
				return false;
			}
		}
		return true;
	}

	//翻轉烙餅資訊
	void Revert(int nBegin, int nEnd)
	{
		ASSERT(nEnd > nBegin);
		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;
		}
	}
private:
	int* m_CkaeArray;				//烙餅資訊數組
	int	 m_nCakeCnt;				//烙餅個數
	int  m_nMaxSwap;				//最多交換次數，根據前面的推斷，這裡最多為m_NCakeCnt*2
	int* m_SwapArray;				//交換結果數組
	int* m_ReverseCakeArray;		//目前翻轉烙餅資訊數組
	int* m_ReverseCakeArraySwap;	//目前翻轉烙餅交換結果數組
	int  m_nSearch;					//目前搜尋次數資訊
};

int main()
{
	CPrefixsorting x;
	int array[10] = { 5, 9, 4, 1, 2, 0, 8, 7, 6, 3 };
	x.Run(array, 10);
	x.Output();

	getchar();
	return 0;
}