学步园

问题描述

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

问题。有个同事说：

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

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

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

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

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

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

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

思路：

一般遇到最优解问题我们首先想到的就是动态规划、贪心以及分支界限三种方法。书中提到了动态规划和分支界限这

两种方法，但只给出了分支界限方法的思路以及代码，所以我就以书上的方法来讲讲自己的理解吧。

书上的代码用的是递归遍历+剪枝。既然是递归，就得有个退出的条件，不然就死循环了。在这个问题中，第一个递

归退出的条件理所当然就是所有的烙饼都已经排好序了。如果只是这样的，就不涉及到剪枝了。我们知道递归的特点

是简洁，但是其效率相对来说是比较低的，如果遇到很大的问题，在现实中就不适用了，而提高递归效率的唯一方法

就是剪枝，所以我们必须想办法找到剪枝的策略。

一般来说我们都是通过去除一些不必要的遍历来进行剪枝的，分析这个问题，我们不难发现，最多要翻转的次数不会

超过2*(n-1)次，至于这个数字是怎么来的，书上已经写的很明白了，这里就不多作累赘啦。如果只是等某种翻转次数

超过2*(n-1)再来放弃这种遍历的话，显然意义不大。按照书上给出的思路，以2*(n-1)作为上界（UpperBound），表

示最差方案；而下界（LowerBound）则是动态的，下界的取值是当前排序状态下，我们至少还要翻转的次数，程序

中我们用变量 nEstimate  表示。当当前翻转次数+nEstimate>UpperBound()时，说明继续遍历下去最后的结果会超过

上界，这时我们直接对其进行剪枝。

代码：

#include<cassert>
#include<iostream>
using namespace std;

class PrefixSorting
{
	int* m_CakeArray;   //烙饼信息数组
	int m_nCakeCnt;     //烙饼个数
	int m_nMaxSwap;     //最多翻转次数，即上界

	int* m_SwapArray;   //交换结果数组，即保存最优解的每一步交换

	int* m_ReverseCakeArray;       //当前翻转烙饼信息数组
	int* m_ReverseCakeArraySwap;   //当前翻转烙饼交换结果数组
	int m_nSearch;                 //当前遍历次数信息
public:
	PrefixSorting()
	{
		m_nCakeCnt = 0;
		m_nMaxSwap = 0;
	}

	~PrefixSorting()
	{
		if (m_CakeArray != NULL)
			delete m_CakeArray;
		if (m_SwapArray != NULL)
			delete m_SwapArray;
		if (m_ReverseCakeArray != NULL)
			delete m_ReverseCakeArray;
		if (m_ReverseCakeArraySwap != NULL)
			delete m_ReverseCakeArraySwap;
	}

	/*计算烙饼翻转信息*/
	void Run(int* pCakeArray, int nCakeCnt)
	{
		Init (pCakeArray, nCakeCnt);

		m_nSearch = 0;
		Search (0);
	}

	/*输出烙饼翻转的具体信息*/
	void Output ()
	{
		for (int i = 0; i < m_nMaxSwap; i++)
			printf("%d\n", m_SwapArray[i]);

		printf("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_CakeArray = new int[m_nCakeCnt];
		assert (m_CakeArray != NULL);
		for (int i = 0; i < m_nCakeCnt; i++)
		{
			m_CakeArray[i] = pCakeArray[i];
		}

		m_nMaxSwap = UpperBound (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_CakeArray[i];
		}
		m_ReverseCakeArraySwap = new int[m_nMaxSwap];
	}

	/*计算上界*/
	int UpperBound(int nCakeCnt)
	{
		return (nCakeCnt - 1) * 2; //书上这里是 nCakeCnt * 2
	}

	/*计算下界*/
	int LowerBound(int* pCakeArray, int nCakeCnt)
	{
		int t;
		int 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];
			}
			return ;
		}

		/*递归遍历*/
		for (int i = 1; i < m_nCakeCnt; i++)
		{
			Reverse (0, i);
			m_ReverseCakeArraySwap[step] = i;
			Search (step + 1);
			Reverse (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 Reverse(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;
		}
	}
};

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

	system("pause");
	return 0;
}