首页 > 代码库 > 《编程之美》之一摞烙饼的排序

《编程之美》之一摞烙饼的排序

2024-07-10 10:32:45   213人阅读

星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯，程序员多喝了几杯之后谈什么呢？自然是算法

问题。有个同事说：

“我以前在餐厅打工，顾客经常点非常多的烙饼。店里的烙饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小

次序摆好---小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们

上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。我后来想，这实际上是个有趣的排序问题：假设有n块大小

不一的摞饼，那最少要翻几次，才能达到大小有序的结果呢？”

从这段描述中我们可以很容易的就把问题抽象出来：给你一个由 n 个连续整数组成的数组，数组是无序的，现在要你

对这个数组进行升序排序，但只能对数组进行一种操作，就是只能对从数组第一个元素开始到数组中任意一个元素之

间的所有元素进行翻转。只是这样的话，问题还不是很麻烦。这里还要求我们写程序输出最优的翻转过程。

#include <stdio.h>#include <stdlib.h>#include <assert.h>class CPrefixSorting{public:	int * m_SwapArray;	int * m_SwapTempArray;	int * m_PieTempArray;	int m_nPieCount;	int * m_PieArray;	int m_nMaxSwapCount;public:	CPrefixSorting()	{	}	virtual ~CPrefixSorting()	{	}public:	void OutPut()	{		for (int i = 0; i < m_nMaxSwapCount; i++)		{			printf("%d\n", m_SwapArray[i]);		}	}	/*遍历搜寻所有解法*/	bool Search(int nStep)	{		/*剪枝:如果比最普通的解法还要差劲，干脆舍弃*/  		int nMinTimes = LowerBound(m_PieTempArray, m_nPieCount);		if (nStep + nMinTimes > m_nMaxSwapCount)		{			return false;		}		if (IsSorted())		{			/*如果找到一个更优解法，则保存这个更优的解法*/			if (nStep < m_nMaxSwapCount)			{				m_nMaxSwapCount = nStep;				for (int i = 0; i < m_nMaxSwapCount; i++)				{					m_SwapArray[i] = m_SwapTempArray[i];				}			}			return true;		}		/*颠倒此次烙饼后，遍历接下来全部可能的颠倒情况*/		for (int i = 1; i < m_nPieCount; i++)		{			Reverse(0, i);			m_SwapTempArray[nStep] = i;			Search(nStep + 1);			Reverse(0, i);		}	}	bool IsSorted()	{		for (int i = 0; i < m_nPieCount - 1; i++)		{			if (m_PieTempArray[i] > m_PieTempArray[i + 1])			{				return false;			}		}		return true;	}	void Init(int* pPieArray, int nPieCount)	{		assert(NULL != pPieArray);		assert(0 < nPieCount);		m_PieArray = new int[nPieCount];		assert(NULL != m_PieArray);		m_PieTempArray = new int[nPieCount];		assert(NULL != m_PieTempArray);		m_nPieCount = nPieCount;		for (int i = 0; i < nPieCount; i++)		{			m_PieArray[i] = pPieArray[i];			m_PieTempArray[i] = pPieArray[i];		}		m_nMaxSwapCount = UpperBound(nPieCount);		m_SwapArray = new int[m_nMaxSwapCount];		assert(NULL != m_SwapArray);		m_SwapTempArray = new int[m_nMaxSwapCount];		assert(NULL != m_SwapTempArray);	}	void Reverse(int nBegin, int nEnd)	{		assert(nBegin < nEnd);		int i, j, t;		for (i = nBegin, j = nEnd; i < j; i++, j--)		{			t = m_PieTempArray[i];			m_PieTempArray[i] = m_PieTempArray[j];			m_PieTempArray[j] = t;		}	}	void Run(int* pPieArray, int nPieCount)	{		Init(pPieArray, nPieCount);		Search(0);		OutPut();	}	int UpperBound(int nPieCount)	{		return (nPieCount - 1) * 2;	}	int LowerBound(int* pPieArray, int nPieCount)	{		int ret = 0, t;		for (int i = 0; i < m_nPieCount - 1; i++)		{			t = pPieArray[i] - pPieArray[i+1];			if (t == 1 || t == -1)			{				continue;			}			ret++;		}		return ret;	}};int main(){	CPrefixSorting stSort;	int pPieArray[10] = {3,4,0,1,2,6,5,8,7,9};	stSort.Run(pPieArray, 10);	system("pause");	return 0;}

　　


联系
我们