学步园

1.3_pancake.cpp

//1.3_pancake.cpp by flyinghearts#qq.com<br /> #include<iostream><br /> #include<iomanip><br /> #include<vector><br /> #include<algorithm><br /> using namespace std;</p> <p>class Pancake{<br /> vector<int> cake; //当前各个烙饼的状态<br /> vector<int> cake_swap; //每次翻转的烙饼位置<br /> vector<int> result; //最优解中，每次翻转的烙饼位置<br /> vector<int> cake_order; //第step+1次翻转时，翻转位置的优先顺序<br /> int max_size; //预分配数组大小<br /> int min_swap; //最优解的翻转次数<br /> int min_swap_init; //最优解的翻转次数初始值<br /> int count_search; //search_cake被调用次数<br /> int count_reverse; //reverse_cake被调用次数<br /> int cake_size; //要处理的烙饼数组大小<br /> const int *cake_old; //要处理的原烙饼数组<br /> bool not_turn_back; //是否允许翻回上一个状态</p> <p> void search_cake(int size, int step, int least_swap_old);<br /> void reverse_cake(int index); //翻转0到index间的烙饼<br /> Pancake(const Pancake&);<br /> Pancake& operator=(const Pancake&);</p> <p>public:<br /> Pancake(int size=0):max_size(0) { init(size); }<br /> void init(int size=0);<br /> void print();<br /> void process(); //显示最优解，翻转过程<br /> int run(const int cake_arr[], int size, bool not_turn_back_=1, bool show=1);<br /> };</p> <p>void Pancake::init(int size)<br /> {<br /> if (size<=0) size=16;<br /> if (size>max_size){<br /> max_size=size;<br /> cake.reserve(size);<br /> cake_swap.reserve(size*2);<br /> result.reserve(size*2);<br /> cake_order.reserve(size*size*2);<br /> }<br /> min_swap=0;<br /> min_swap_init=0;<br /> count_search=0;<br /> count_reverse=0;<br /> cake_size=0;<br /> cake_old=NULL;<br /> not_turn_back=true;<br /> }</p> <p>void Pancake::print()<br /> {<br /> if (min_swap>0){<br /> if (not_turn_back) cout<< "turn back to last state: disallowed./n";<br /> else cout<< "turn back to last state: allowed./n";<br /> cout<< "minimal_swap initial: "<< min_swap_init<< " final: "<< min_swap<br /> << "/nsearch/reverse function was called: "<< count_search<br /> << "/"<< count_reverse<< " times/nsolution: ";<br /> for (int i=0;i<min_swap; ++i) cout<< result[i]<< " ";<br /> cout<< "/n/n";<br /> }<br /> }</p> <p>void Pancake::process()<br /> {<br /> if (min_swap>0 && cake_size>0 && cake_old != NULL){<br /> cake.assign(cake_old, cake_old+cake_size);<br /> int i,j;<br /> const int WIDTH=3;<br /> cout<< "old: ";<br /> for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< cake[j]<<" ";<br /> cout<<"/n";<br /> for (i=0; i<min_swap; ++i){<br /> reverse_cake(result[i]);<br /> cout<< setw(WIDTH)<< i+1<< "-"<< setw(WIDTH)<< result[i]<<": ";<br /> for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< cake[j]<<" ";<br /> cout<<"/n";<br /> }<br /> cout<<"/n/n";<br /> }<br /> }</p> <p>void Pancake::reverse_cake(int index)<br /> {<br /> ++count_reverse;<br /> int *beg=&cake[0], *end=&cake[0]+index;<br /> int tmp;<br /> while(beg<end){<br /> tmp = *beg;<br /> *beg++ = *end;<br /> *end-- = tmp;<br /> }<br /> }</p> <p>int Pancake::run(const int cake_arr[], int size, bool not_turn_back_, bool show)<br /> {<br /> count_search=0;<br /> count_reverse=0;<br /> min_swap=0;<br /> not_turn_back = not_turn_back_;<br /> cake_size=0;<br /> cake_old=NULL;<br /> if (cake_arr==NULL || size<=1) return 0;<br /> while (size>1 && size-1==cake_arr[size-1]) --size; //去除末尾已就位的烙饼<br /> if (size<=1) return 0;</p> <p> if (size>max_size) init(size+16);<br /> cake.assign(cake_arr,cake_arr+size);<br /> cake_size=size;<br /> cake_old=cake_arr;</p> <p> int i, least_swap=0, sz=size-1, *p=&result[0];<br /> while (sz>0){ //先计算一个可能解<br /> for (i=0; i<=sz; ++i)<br /> if (cake[i]==sz) break;<br /> if (i!=0){<br /> reverse_cake(i);<br /> *p++=i; //result.push_back(i);<br /> ++min_swap;<br /> }<br /> reverse_cake(sz);<br /> *p++=sz--; //result.push_back(sz);<br /> ++min_swap;<br /> while(sz>0 && sz==cake[sz]) --sz;<br /> }</p> <p> cake.assign(cake_arr,cake_arr+size); //恢复原来的数组<br /> cake.push_back(size); //多放一个烙饼，避免后面的边界判断<br /> cake_swap[0]=0; //为方便起见，假设第0步翻转的烙饼编号为0<br /> for (i=0,least_swap=0; i<size; ++i)<br /> if (cake[i]-cake[i+1]+1u >2) least_swap++;<br /> //等同于if (cake[i]-cake[i+1]>1 || cake[i]-cake[i+1]<-1) least_swap++;<br /> min_swap_init=min_swap;<br /> if (least_swap != min_swap)<br /> search_cake(size,0,least_swap);<br /> if (show) print();<br /> return min_swap;<br /> }</p> <p>void Pancake::search_cake(int size, int step, int least_swap_old)<br /> {<br /> ++count_search;<br /> while (size>1 && size-1==cake[size-1]) --size; //去除末尾已就位的烙饼<br /> int least_swap=least_swap_old;</p> <p> for (int pos=1, last_swap=cake_swap[step++]; pos<size; ++pos){<br /> if (not_turn_back && pos==last_swap) continue; //是否翻回上个状态<br /> least_swap = least_swap_old ;<br /> if (cake[pos]-cake[pos+1]+1u<=2) ++least_swap;<br /> if (cake[0]-cake[pos+1]+1u<=2) --least_swap;<br /> if (least_swap+step >= min_swap) continue;<br /> cake_swap[step]=pos;<br /> if (least_swap == 0){<br /> result.assign(&cake_swap[1],&cake_swap[1]+step+1);<br /> min_swap= step;<br /> return;<br /> }<br /> reverse_cake(pos);<br /> search_cake(size,step,least_swap);<br /> reverse_cake(pos);<br /> }<br /> }</p> <p>int main()<br /> {<br /> int aa[10]={3,2,1,6,5,4,9,8,7,0};<br /> Pancake cake(16);<br /> cake.run(aa,10);<br /> cake.run(aa,10,0);<br /> cake.process();</p> <p> //遍历求第n个烙饼数<br /> const int N=8;<br /> int i,j,max=0,tmp;<br /> int arr[N];<br /> for (j=1;j<=N;++j){<br /> for (i=0; i<j; ++i) arr[i]=i;<br /> max=0;<br /> while(next_permutation(arr,arr+j)){<br /> tmp=cake.run(arr,j,1,0);<br /> if (tmp>max) max=tmp;<br /> }<br /> cout<<j<<" "<<max<<endl;<br /> }<br /> }</p> <p>

 1.3_pancake_final.cpp

//1.3_pancake_final.cpp by flyinghearts#qq.com<br /> #include<iostream><br /> #include<iomanip><br /> #include<vector><br /> #include<algorithm><br /> using namespace std;</p> <p>class Pancake{<br /> vector<int> cake; //当前各个烙饼的状态<br /> vector<int> cake_swap; //每次翻转的烙饼位置<br /> vector<int> result; //最优解中，每次翻转的烙饼位置<br /> vector<int> cake_order; //第step+1次翻转时，翻转位置的优先顺序<br /> int max_size; //预分配数组大小<br /> int min_swap; //最优解的翻转次数<br /> int min_swap_init; //最优解的翻转次数初始值<br /> int count_search; //search_cake被调用次数<br /> int count_reverse; //reverse_cake被调用次数<br /> int cake_size; //要处理的烙饼数组大小<br /> const int *cake_old; //要处理的原烙饼数组</p> <p> void search_cake(int size, int step, int least_swap_old);<br /> void reverse_cake(int index); //翻转0到index间的烙饼<br /> Pancake(const Pancake&);<br /> Pancake& operator=(const Pancake&);</p> <p>public:<br /> Pancake(int size=0):max_size(0) { init(size); }<br /> void init(int size=0);<br /> void print();<br /> void process(); //显示最优解，翻转过程<br /> int run(const int cake_arr[], int size, bool show=1);<br /> };</p> <p>void Pancake::init(int size)<br /> {<br /> if (size<=0) size=16;<br /> if (size>max_size){<br /> max_size=size;<br /> cake.reserve(size);<br /> cake_swap.reserve(size*2);<br /> result.reserve(size*2);<br /> cake_order.reserve(size*size*2);<br /> }<br /> min_swap=0;<br /> min_swap_init=0;<br /> count_search=0;<br /> count_reverse=0;<br /> cake_size=0;<br /> cake_old=NULL;<br /> }</p> <p>void Pancake::print()<br /> {<br /> if (min_swap>0){<br /> cout<< "minimal_swap initial: "<< min_swap_init<< " final: "<< min_swap<br /> << "/nsearch/reverse function was called: "<< count_search<br /> << "/"<< count_reverse<< " times/nsolution: ";<br /> for (int i=0;i<min_swap; ++i) cout<< result[i]<< " ";<br /> cout<< "/n/n";<br /> }<br /> }</p> <p>void Pancake::process()<br /> {<br /> if (min_swap>0 && cake_size>0 && cake_old != NULL){<br /> cake.assign(cake_old, cake_old+cake_size);<br /> int i,j;<br /> const int WIDTH=3;<br /> cout<< "old: ";<br /> for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< cake[j]<<" ";<br /> cout<<"/n";<br /> for (i=0; i<min_swap; ++i){<br /> reverse_cake(result[i]);<br /> cout<< setw(WIDTH)<< i+1<< "-"<< setw(WIDTH)<< result[i]<<": ";<br /> for (j=0; j<cake_size; ++j) cout<< setw(WIDTH)<< cake[j]<<" ";<br /> cout<<"/n";<br /> }<br /> cout<<"/n/n";<br /> }<br /> }</p> <p>void Pancake::reverse_cake(int index)<br /> {<br /> ++count_reverse;<br /> int *beg=&cake[0], *end=&cake[0]+index;<br /> int tmp;<br /> while(beg<end){<br /> tmp = *beg;<br /> *beg++ = *end;<br /> *end-- = tmp;<br /> }<br /> }</p> <p>int Pancake::run(const int cake_arr[], int size, bool show)<br /> {<br /> count_search=0;<br /> count_reverse=0;<br /> min_swap=0;<br /> cake_size=0;<br /> cake_old=NULL;<br /> if (cake_arr==NULL || size<=1) return 0;<br /> while (size>1 && size-1==cake_arr[size-1]) --size; //去除末尾已就位的烙饼<br /> if (size<=1) return 0;</p> <p> if (size>max_size) init(size+16);<br /> cake.assign(cake_arr,cake_arr+size);<br /> cake_size=size;<br /> cake_old=cake_arr;</p> <p> int i, least_swap=0, sz=size-1, *p=&result[0];<br /> while (sz>0){ //先计算一个可能解<br /> for (i=0; i<=sz; ++i)<br /> if (cake[i]==sz) break;<br /> if (i!=0){<br /> reverse_cake(i);<br /> *p++=i; //result.push_back(i);<br /> ++min_swap;<br /> }<br /> reverse_cake(sz);<br /> *p++=sz--; //result.push_back(sz);<br /> ++min_swap;<br /> while(sz>0 && sz==cake[sz]) --sz;<br /> }</p> <p> cake.assign(cake_arr,cake_arr+size); //恢复原来的数组<br /> cake.push_back(size); //多放一个烙饼，避免后面的边界判断<br /> cake_swap[0]=0; //为方便起见，假设第0步翻转的烙饼编号为0<br /> for (i=0,least_swap=0; i<size; ++i)<br /> if (cake[i]-cake[i+1]+1u >2) least_swap++;<br /> //等同于if (cake[i]-cake[i+1]>1 || cake[i]-cake[i+1]<-1) least_swap++;<br /> min_swap_init=min_swap;<br /> if (least_swap != min_swap)<br /> search_cake(size,0,least_swap);<br /> if (show) print();<br /> return min_swap;<br /> }</p> <p>void Pancake::search_cake(int size, int step, int least_swap_old)<br /> {<br /> ++count_search;<br /> while (size>1 && size-1==cake[size-1]) --size; //去除末尾已就位的烙饼</p> <p> int *first=&cake_order[0]+step*cake_size;<br /> int *last=first+size, *low=first, *high=last, *p=first;<br /> int least_swap=least_swap_old;</p> <p> for (int pos=1, last_swap=cake_swap[step++]; pos<size; ++pos){<br /> if (pos==last_swap) continue;<br /> least_swap = least_swap_old ;<br /> if (cake[pos]-cake[pos+1]+1u<=2) ++least_swap;<br /> if (cake[0]-cake[pos+1]+1u<=2) --least_swap;</p> <p> if (least_swap+step >= min_swap) continue;<br /> if (least_swap == 0){<br /> cake_swap[step]=pos;<br /> result.assign(&cake_swap[1],&cake_swap[1]+step+1);<br /> min_swap= step;<br /> return;<br /> }</p> <p> if (least_swap==least_swap_old) *low++ =pos;<br /> else if (least_swap>least_swap_old) *--high =pos;<br /> else{ //先处理使least_swap_old减小1的翻转<br /> cake_swap[step] = pos;<br /> reverse_cake(pos);<br /> search_cake(size,step,least_swap);<br /> reverse_cake(pos);<br /> }<br /> }</p> <p> //再处理使least_swap_old不变的翻转<br /> for(least_swap=least_swap_old,p=first; p<low; p++){<br /> if (least_swap+step >= min_swap) return;<br /> cake_swap[step] = *p;<br /> reverse_cake(*p);<br /> search_cake(size,step,least_swap);<br /> reverse_cake(*p);<br /> }</p> <p> //最后处理使least_swap_old增加1的翻转<br /> for(++least_swap, p=high; p<last; p++){<br /> if (least_swap+step >= min_swap) return;<br /> cake_swap[step] = *p;<br /> reverse_cake(*p);<br /> search_cake(size,step,least_swap);<br /> reverse_cake(*p);<br /> }</p> <p>}</p> <p>int main()<br /> {<br /> int aa[10]={3,2,1,6,5,4,9,8,7,0};<br /> Pancake cake(16);<br /> cake.run(aa,10);<br /> cake.process();</p> <p> //遍历求第n个烙饼数<br /> const int N=8;<br /> int i,j,max=0,tmp;<br /> int arr[N];<br /> for (j=1;j<=N;++j){<br /> for (i=0; i<j; ++i) arr[i]=i;<br /> max=0;<br /> while(next_permutation(arr,arr+j)){<br /> tmp=cake.run(arr,j,0);<br /> if (tmp>max) max=tmp;<br /> }<br /> cout<<j<<" "<<max<<endl;<br /> }<br /> }</p> <p>