编程之美之一摞烙饼.cpp.doc

/ 编程之美之一摞烙饼.cpp : 定义控制台应用程序的入口点。/ 不同的程序会得到不同的结果吗？有个程序能得到不同的结果，但后来证明他的结果是错的/该算法有点在于在于找最少的交换次数，不是在于用最少的时间进行排序，此算法的排序时间不是最少的。因为算法的查找时间太长了。#include stdafx.h#include #include #include #include using namespace std;#define N 10/7class Cakeint nCakeNum;int *nCakeArr;/有用吗？int nMaxSwap;/实际进行的最大的交换次数int *nCakeResultArr;/存放在哪里进行了交换，存放的是编号int *nCakeReverseArr;/几乎所有的操作都是对它进行操作。int *nCakeReverseResultArr;/用来记录找到的结果int nSearch;public:Cake()nCakeNum=0;nMaxSwap=0;nCakeArr=NULL;/没用吧nCakeResultArr=NULL;nCakeReverseArr=NULL;nCakeReverseResultArr=NULL;coutin construstendl;Cake()/析构函数自动运行，自动释放对象所占用的资源，不可以再用delete语句了（与编程之美书上不同）。/if(nCakeArr!=NULL) delete nCakeArr;/ if(nCakeResultArr!=NULL) delete nCakeResultArr;/ if(nCakeReverseArr!=NULL) delete nCakeReverseArr;/if(nCakeReverseResultArr!=NULL) delete nCakeReverseResultArr;void Run()/int *nCakeArr, int nCakeNum/Init(nCakeArr,nCakeNum);/nSearch=0;Search(0);void Output() constfor(int i=0;inMaxSwap;i+)coutnCakeReverseResultArri ;coutendl最大的交换次数是：nMaxSwapendl;coutsearch times are :nSearchendl;void PrintArr()for(int i=0;inCakeNum;i+)coutnCakeArri ;coutendl;void PrintReverseArr()for(int i=0;inCakeNum;i+)coutnCakeReverseArri ;coutendl;void Init(int *pCakeArr, int pCakeNum)nSearch = 0;nCakeNum = pCakeNum;nCakeArr = new intnCakeNum;assert(nCakeArr);for(int i=0;inCakeNum;i+)nCakeArri = pCakeArri;/init 有用吗？nMaxSwap = UpperBound(nCakeNum);nCakeResultArr = new intpCakeNum;assert(nCakeResultArr);nCakeReverseResultArr = new intnMaxSwap;assert(nCakeReverseResultArr);nCakeReverseArr = new intnCakeNum;assert(nCakeReverseArr);for(int i=0;inCakeNum;i+)nCakeReverseArri = pCakeArri;/initprivate:int UpperBound(int pCakeNum)return 2*(pCakeNum-2)+1;/原来是2*(pCakeNum-1) 改完这search times 由原来的715减少到589int LowerBound(int *pCakeArr, int pCakeNum)int num=1;/应该是1.因为当最后一个不在其有序时对应的位置时，还要多翻转一次，当这由0改成1后，search times 由原来的4081减少到715for(int i=1;ipCakeNum;i+)if(pCakeArri-pCakeArri-1=1)|(pCakeArri-pCakeArri-1=-1);elsenum+;return num;bool IsSorted(int *pCakeArr, int pCakeNum)for(int i=1;ipCakeNum;i+)if(pCakeArripCakeArri-1)return 0;return 1;void Reverse(int *nCakeReverseArr,int begin,int end)/ operate nCakeReverseArrint temp;assert(beginend);for(int i=begin,j=end;inMaxSwap|step=nMaxSwap) /加后面的或语句运行次数4081，不加4129return ;if(IsSorted(nCakeReverseArr,nCakeNum)if(stepnMaxSwap)/此算法找最少的翻转次数，不是最小的排序时间。解释：如果数组已经是有序的了，并且当前的步骤少于最大的翻转次数，更新当前的翻转次数，并把当前的结果记录下来。nMaxSwap = step;for(int i=0;inMaxSwap;i+)nCakeReverseResultArri=nCakeResultArri;/为什么用nCakeReverseResultArr？因为nCakeResultArr本函数返回后还会变，所以不能用其存储最后的结果/若果当前的翻转次数没有原来的少，不更新，只是返回。return ;for(int i=1;inCakeNum;i+)Reverse(nCakeReverseArr,0,i);nCakeResultArrstep=i;/保存结果，记录从哪开始翻转的Search(step+1);Reverse(nCakeReverseArr,0,i);return ;/myPizzaint _tmain(int argc, _TCHAR* argv)Cake cake1;/int arrbN=7,3,5,4,2,1,6;int arrbN=5,6,1,2,3,4,9,8,7,0;int *arr = new intN;for(int i=0;iN;i+)arri=arrbi;cake1.Init(arr,N);cake1.PrintArr();cake1.Run();cake1.PrintReverseArr();/作为 递归的数组 遍历所有的分支 到最后没有变化 只是在遍历时把符合条件的存储起来cake1.Output();/cake1.PrintArr();delete arr;/ 可以不用delete语句删除，不会报错system(pause); return 0;/*/1.3_pancake_1.cpp by flyinghearts##include#include#include#includeusing namespace std;class Pancake vector cake; /当前各个烙饼的状态 vector cake_swap; /每次翻转的烙饼位置 vector result; /最优解中，每次翻转的烙饼位置 vector cake_order; /第step+1次翻转时，翻转位置的优先顺序 int max_size; /预分配数组大小 int min_swap; /最优解的翻转次数 int min_swap_init; /最优解的翻转次数初始值 int count_search; /search_cake被调用次数 int count_reverse; /reverse_cake被调用次数 int cake_size; /要处理的烙饼数组大小 const int *cake_old; /要处理的原烙饼数组 bool not_turn_back; /是否允许翻回上一个状态 void search_cake(int size, int step, int least_swap_old); void reverse_cake(int index); /翻转0到index间的烙饼 Pancake(const Pancake&); Pancake& operator=(const Pancake&);public: Pancake(int size=0):max_size(0) init(size); void init(int size=0); void print() const; void process(); /显示最优解，翻转过程 int run(const int cake_arr, int size, bool not_turn_back_=1, bool show=1);void Pancake:init(int size) if (sizemax_size) max_size=size; cake.resize(size); cake_swap.resize(size*2); result.resize(size*2); cake_order.resize(size*size*2); min_swap=0; min_swap_init=0; count_search=0; count_reverse=0; cake_size=0; cake_old=NULL; not_turn_back=true;void Pancake:print() const if (min_swap0) if (not_turn_back) cout turn back to last state: disallowed.n; else cout turn back to last state: allowed.n; cout minimal_swap initial: min_swap_init final: min_swap nsearch/reverse function was called: count_search / count_reverse timesnsolution: ; for (int i=0;imin_swap; +i) cout resulti ; cout0 & cake_size0 & cake_old != NULL) cake.assign(cake_old, cake_old+cake_size); int i,j; const int WIDTH=3; cout old: ; for (j=0; jcake_size; +j) cout setw(WIDTH) cakej ; coutn; for (i=0; imin_swap; +i) reverse_cake(resulti); cout setw(WIDTH) i+1 - setw(WIDTH) resulti: ; for (j=0; jcake_size; +j) cout setw(WIDTH) cakej ; coutn; coutnn; void Pancake:reverse_cake(int index) +count_reverse; int *beg=&cake0, *end=&cake0+index; int tmp; while(begend) tmp = *beg; *beg+ = *end; *end- = tmp; int Pancake:run(const int cake_arr, int size, bool not_turn_back_, bool show) count_search=0; count_reverse=0; min_swap=0; not_turn_back = not_turn_back_; cake_size=0; cake_old=NULL; if (cake_arr=NULL | size1 & size-1=cake_arrsize-1) -size; /去除末尾已就位的烙饼 if (sizemax_size) init(size+16); cake.assign(cake_arr,cake_arr+size); cake_size=size; cake_old=cake_arr; int i, least_swap=0, sz=size-1, *p=&result0; while (sz0) /先计算一个可能解 for (i=0; i0 & sz=cakesz) -sz; cake.assign(cake_arr,cake_arr+size); /恢复原来的数组 cake.push_back(size); /多放一个烙饼，避免后面的边界判断 cake_swap0=0; /为方便起见，假设第0步翻转的烙饼编号为0 for (i=0,least_swap=0; i2) least_swap+; /等同于if (cakei-cakei+11 | cakei-cakei+11 & size-1=cakesize-1) -size; /去除末尾已就位的烙饼 int least_swap=least_swap_old; for (int pos=1, last_swap=cake_swapstep+; possize; +pos) if (not_turn_back & pos