问题描述: 有一摞烙饼,因为一只手端着盘子,所以只能用另外一只手来给烙饼排序,将烙饼由大到小排好序。这样就要求我们在给烙饼排序的时候总是将最上面的N个烙饼一起翻转。如果最下面的烙饼是最大的,那么只需要解决上面的N-1个烙饼,同理可以最后到解决两个烙饼的排序。
简单的排序方法:先找到最大的烙饼,将其和其以上的烙饼一起翻转,这样最大的烙饼就在盘子的最上面了,然后翻转所有的烙饼,这样最大的烙饼就在盘子的最下面了。同样的,处理剩下的N-1个烙饼,知道最后所有的烙饼都排好序。可以知道我们最多需要进行2*(N-1)次翻转就可以将所有的烙饼排好序。
问题? 如果减少烙饼的反转次数,达到一个最优的解。 加入这堆老兵中有几个不同的部分相对有序,凭直接来猜测,可以把笑一下的烙饼进行翻转,每次考虑翻转烙饼的时候总是把相邻的烙饼尽可能的放到一起。
解决方法: 通过穷举法来找所有可能方案中的最优方案,自然会用到动态规划或者递归的方法来实现。可以从不同的翻转策略开始,比如第一次先翻最小的,然后递归的把所有的可能都全部翻转一次。
既然2(N-1)是一个最多的翻转次数,就可以得知,如果算法中的翻转次数超过了2(N-1),我们就应该放弃这个算法。
我们总是希望UpperBound越小越好,而LowerBound则越大越好,这样就可以尽可能的减少搜索的次数,是算法的性能更好。
代码如下:(代码可能需要仔细的阅读,才能明白算法的含义)
#pragma once class CPrefixSorting { public: ~CPrefixSorting(void); CPrefixSorting() { m_nCakeCnt=0; m_nMaxSwap=0; } // 计算烙饼翻转信息 // @param // 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++) { printf("%d",m_SwapArray[i]); } printf("\n |Search Times|:%d\n",m_nSearch); printf("Total Swap times=%d\n",m_nMaxSwap); } 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; // 当前搜索次数信息 // 初始化数组信息 // @param // pCakeArray 存储烙饼索引数组 // nCakeCnt 烙饼个数 // void Init(int* pCakeArray,int nCakeCnt) { m_nCakeCnt=nCakeCnt; // 初始化烙饼数组 m_CakeArray=new int[m_nCakeCnt]; for(int i=0;i<m_nCakeCnt;i++) { m_CakeArray[i]=pCakeArray[i]; } // 设置最多交换次数信息 m_nMaxSwap=UpperBound(m_nCakeCnt); // 初始化交换结果数组 m_SwapArray=new int[m_nMaxSwap+1]; // 初始化中间交换结果信息 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 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;// 修改最大的翻转次数,让m_nMaxSwap记录最小的翻转次数 for(i=0;i<m_nMaxSwap;i++) { m_SwapArray[i]=m_ReverseCakeArraySwap[i]; } } return; } // 递归进行翻转 for(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) { 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; } } };
// CPrefixSorting.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "iostream" #include "PrefixSorting.h" using namespace std; int _tmain(int argc, _TCHAR* argv[]) { cout<<"--->begin"<<endl; CPrefixSorting panCakeSort; int panCake[5]={3,5,1,4,2}; panCakeSort.Run(panCake,5); panCakeSort.Output(); return 0; }
// CPrefixSorting.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "iostream" #include "PrefixSorting.h" using namespace std; int _tmain(int argc, _TCHAR* argv[]) { cout<<"--->begin"<<endl; CPrefixSorting panCakeSort; int panCake[5]={3,5,1,4,2}; panCakeSort.Run(panCake,5); panCakeSort.Output(); return 0; }
输出的结果为:
--->begin 32423 |Search Times|:2189 Total Swap times=5 请按任意键继续. . .