首页 > 代码库 > 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一摞烙饼的问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。