本文主要是介绍编程之美：一摞烙饼的排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
有一摞大小不等的烙饼，处理方法如下：只能拿最上面的一个或n个烙饼，然后上下颠倒，问最小需要颠倒几次，才能使得烙饼从上到下有序
代码有些许错误，已改正：
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
/*烙饼排序
*/
class cakeSort{
public:cakeSort(){m_cnt=0;m_maxSwap=0;}//n个烙饼的排序执行void run(vector<int> cakeArray,int N){Init(cakeArray,N);m_Search=0;Search(0);}void Print(){for_each(m_arrSwap.begin(),m_arrSwap.end(),[](int i){cout<<i<<" ";});cout<<endl<<"递归执行次数"<<m_Search<<endl;cout<<"最少交换次数"<<m_maxSwap<<endl;;}
private:void Search(int step){m_Search++;//估计这次搜索所需最小的交换次数int estimate=LowerBound(m_reverseCakeArray,m_cnt);//剪枝if(step + estimate >= m_maxSwap)return;if(IsSorted(m_reverseCakeArray,m_cnt)){if(step<m_maxSwap){m_maxSwap=step;m_arrSwap.assign(m_reverseCakeArraySwap.begin(),m_reverseCakeArraySwap.end());}return;}for(int i=1;i<m_cnt;i++){Revert(0,i);m_reverseCakeArraySwap[step]=i;Search(step+1);Revert(0,i);}}void Init(vector<int> cakeArray,int N){m_cnt=N;m_cakeArray.assign(cakeArray.begin(),cakeArray.end());m_maxSwap=UpBound(m_cnt);//交换次数最多2nm_reverseCakeArray.assign(cakeArray.begin(),cakeArray.end());m_reverseCakeArraySwap.resize(m_maxSwap);//交换过后的临时结果m_arrSwap.resize(m_maxSwap);//所有交换结束取其最小次数的最终结果}//当前翻转的上界int UpBound(int cnt){return cnt*2;}//当前翻转的下界int LowerBound(vector<int> cakeArray,int cnt){int t,res=0;for(int i=1;i<cnt;i++){t=cakeArray[i]-cakeArray[i-1];if((t==1)||(t==-1)){}else res++;}return res;}bool IsSorted(vector<int> cakeArray,int cnt){for(int i=1;i<cnt;i++)if(cakeArray[i-1]>cakeArray[i])return false;return true;}//翻转void Revert(int begin,int end){for(int i=begin,j=end;i<j;i++,j--){swap(m_reverseCakeArray[i],m_reverseCakeArray[j]);}}private:vector<int> m_cakeArray;//烙饼int m_cnt;//烙饼个数int m_maxSwap;//最多交换次数vector<int> m_reverseCakeArray;//当前翻转烙饼信息数组vector<int> m_reverseCakeArraySwap;//当前翻转交换结果数组int m_Search;//当前搜索次数vector<int> m_arrSwap;//最终结果
};
int main(){cakeSort c;int a[]={10,9,8,7,6,5,4,3,2,1};vector<int> cake(a,a+10);c.run(cake,10);c.Print();return 0;
}这篇关于编程之美：一摞烙饼的排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
