首页 > 代码库 > 1.3一摞烙饼的问题

1.3一摞烙饼的问题

题目是这样的:

星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说:
“我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。
我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到最后大小有序的结果呢?


思想:

书上面给出的方法是通过递归寻找出最优方案。

递归结束条件有两个:

1)递归步骤超过最大步骤数;

2)已经有序。

但由于递归过程步骤过多,需要对其进行剪枝:

1)定上界:假设每次只将最大的翻到最下面(跟冒泡类似),至多需要2次翻转,总共有n-1个需要翻转(最后一个不用翻了),那么最多需要2*(n-1)次翻转;当然,为了减少更多不必要的遍历,每次找到一个实现了有序的步骤数step,则将max更新为该step。

2)定下界:每次递归时,计算当前所在状态下至少还需要多少次翻转,设为lowerbound, 如果当前已经翻转的步骤数step+lowerbound(已经翻转步骤数+当前状态下至少还需要的步骤数)超过了上界,则可以结束该次递归了。


代码:

class CPrefixSorting {
public:
	CPrefixSorting() {
		m_nCakeCnt = 0;
		m_nMaxSwap = 0;
	} 

	~CPrefixSorting() {
		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;
	}
	
	//pCakeArray  存储烙饼索引数组
	//nCakeCnt    烙饼个数
	void Run(int *pCakeArray, int nCakeCnt) {
		Init(pCakeArray, nCakeCnt);
		m_nSearch = 0;
		Search(0);
	}

	// 输出烙饼具体翻转的次数
	void Output() {
		for(int i = 0; i < m_nMaxSwap; ++i) cout << m_SwapArray[i] << " ";
		cout << "Search times: " << m_nSearch;
		cout << "Total swap times: " << m_nMaxSwap;
	}

private:
	
	//pCakeArray  存储烙饼索引数组
	//nCakeCnt    烙饼个数
	void Init(int* pCakeArray, int nCakeCnt) {
		assert( pCakeArray != NULL );
		assert( nCakeCnt > 0 );
		m_nCakeCnt = nCakeCnt;

		//初始化烙饼数组
		m_CakeArray = new int[nCakeCnt];
		assert( m_CakeArray != NULL );
		for(int i = 0; i < nCakeCnt; ++i) m_CakeArray[i] = pCakeArray[i];

		//设置最多交换次数信息
		m_nMaxSwap = UpperBound(m_nCakeCnt);

		//初始化交换结果数组
		m_SwapArray = new int[m_nMaxSwap + 1];
		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 * 2; }
	
	//寻找当前翻转的下界
	int LowerBound(int* pCakeArray, int nCakeCnt) {
		int ret = 0;

		//根据当前数组的排序信息情况来判断最少需要交换多少次
		for(int i = 1; i < nCakeCnt; ++i) {

			//判断位置相邻的两个烙饼,是否为尺寸排序上相邻的
			int t = pCakeArray[i] - pCakeArray[i-1];
			if(t == 1 || t == -1) { }
			else ++ret;
		}
		return ret;
	}

	void Search(int step) {
		m_nSearch++;

		//估算这次搜索所需要的最小交换次数
		int 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(int 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( nBegin < nEnd );

		//翻转烙饼信息
		for(int i = nBegin, j = nEnd; i < j; ++i, --j) {
			int temp = m_ReverseCakeArray[i];
			m_ReverseCakeArray[i] = m_ReverseCakeArray[j];
			m_ReverseCakeArray[j] = temp;
		}
	}

private:
	int* m_CakeArray;   //烙饼信息数组
	int m_nCakeCnt;		//烙饼个数
	int m_nMaxSwap;		//最多交换次数,根据前面的推断,这里最多为m_nCakeCnt*2
	int* m_SwapArray;   //交换结果数组
	int* m_ReverseCakeArray;   //当前翻转烙饼信息数组
	int* m_ReverseCakeArraySwap;  //当前翻转烙饼交换结果数组
	int m_nSearch;  //当前搜索次数信息
};



1.3一摞烙饼的问题