package beautyOfCoding;
import java.util.Arrays;
/*
*《编程之美》的思路是:搜索+剪枝。有点像是写下棋程序:当前情况下,把所有可能的下一步都做一遍;在这每一遍操作里面,计算出如果按这一步走的话,能不能赢(得出最优结果)。
*《编程之美》上代码有很多错误,且每个变量的含义令人费解。因此我按我的理解写了以下代码:
*/
public class CPrefixSorting {
private int[] cakeArray;//要排序的烙饼数组
private int[] reversingCakeArray;//对cakeArray的一份拷贝。在“搜索+剪枝”过程中,对reversingCakeArray进行操作而不影响原始的排序数组--“cakeArray”。
//事实上我认为是不必要的,因为每次reverse(0,i)之后都会再次执行reverse(0,i)将reversingCakeArray还原。
private int[] swapRecord;//记录最优解的翻转方案。例如如果swapRecord={2,4};表示第一次把0-2之间的烙饼翻转,第二次把0-4之间的烙饼翻转
private int[] swapingRecord;//记录每一次翻转方案。只有在最优解的时候,才复制到swapRecord
private int MaxSwapTimes;//翻转次数
private int searchTimes;//搜索次数,尝试的次数
public static void main(String[] args) {
int[] cakeArray={4,5,1,3,2};
CPrefixSorting cPrefixSorting=new CPrefixSorting(cakeArray);
cPrefixSorting.search(0);
cPrefixSorting.output();
cPrefixSorting.verify();//根据swapRecord记录的最优解的翻转方案,验证一下:将烙饼翻转一次,看是否是最少的操作使烙饼有序
}
public void search(int step){
searchTimes++;
int estimate=lowerBound(reversingCakeArray);
if(step+estimate>=MaxSwapTimes){//more effective than "step+estimate>MaxSwapTimes"
return;
}
if(isSorted(reversingCakeArray)){
if(step<MaxSwapTimes){
MaxSwapTimes=step;
for(int i=0;i<MaxSwapTimes;i++){
swapRecord[i]=swapingRecord[i];
}
}
return;
}
for(int i=1,len=cakeArray.length;i<len;i++){
reverse(0,i);
swapingRecord[step]=i;
search(step+1);
reverse(0,i);
}
}
public void reverse(int begin,int end){
int len=reversingCakeArray.length;
if(begin>=0&&begin<len&&end>=0&&end<len&&begin<end){
for(int i=begin,j=end;i<j;i++,j--){
int tmp=reversingCakeArray[i];
reversingCakeArray[i]=reversingCakeArray[j];
reversingCakeArray[j]=tmp;
}
}
}
public int upperBound(int n){
return 2*(n-1);
}
public int lowerBound(int[] array){
if(array==null){
return 0;
}
if(array.length<2){
return 0;
}
int swapTimes=0;
for(int i=0,len=array.length;i<len-1;i++){
int diff=array[i]-array[i+1];
if(diff==1||diff==-1){
continue;
}else{
swapTimes++;
}
}
return swapTimes;
}
public boolean isSorted(int[] array){
if(array==null){
return false;
}
if(array.length<2){
return true;
}
for(int i=0,len=array.length;i<len-1;i++){
if(array[i]>array[i+1]){
return false;
}
}
return true;
}
public CPrefixSorting(int[] cakeArray){
this.cakeArray=cakeArray;
this.reversingCakeArray=cakeArray;
this.MaxSwapTimes=upperBound(cakeArray.length);
this.swapRecord=new int[MaxSwapTimes];
this.swapingRecord=new int[MaxSwapTimes];
this.searchTimes=0;
}
public void verify(){
System.out.println("the array to be sorted is "+Arrays.toString(reversingCakeArray));
for(int i=0;i<MaxSwapTimes;i++){
reverse(0,swapRecord[i]);
System.out.println("step "+i+":"+Arrays.toString(reversingCakeArray));
}
System.out.println("the sorted array is "+Arrays.toString(reversingCakeArray));
}
public void output(){
System.out.println("MaxSwapTimes="+MaxSwapTimes);
System.out.println("searchTimes="+searchTimes);
System.out.print("swapRecord=");
for(int i=0;i<MaxSwapTimes;i++){
System.out.print(swapRecord[i]+",");
}
System.out.println();
//System.out.println("swapRecord="+Arrays.toString(swapRecord));
}
}
分享到:
相关推荐
【华为OJ烙饼排序】是华为在线测评平台(OpenJudge)上的一道高级编程题目,主要考察的是排序算法的应用和实现。烙饼排序(Flipping Sorting),也称为煎饼排序,是一种基于比较的排序算法,它的灵感来源于煎饼翻转...
然而,翻转烙饼排序因其独特的解决思路和算法设计,仍然是学习算法设计原则和优化技巧的重要案例之一。 ### 结论 翻转烙饼排序问题不仅考验了算法设计的能力,也体现了对数据结构和排序算法原理的深刻理解。通过...
《程序之美-C语言:烙饼排序算法与买书问题源码》 在计算机科学的世界里,算法是解决问题的关键。本文将深入探讨两个编程问题:烙饼排序算法和买书问题,这两个问题都涉及到C语言的高效实现。我们将通过源代码分析...
标签中的“烙饼问题”是一种经典的排序问题,也被称为煎饼排序。在这个问题中,想象一个平底锅可以同时煎两张饼,而我们要对多张饼进行排序,每次只能翻转一张或两张饼。烙饼问题展示了如何在有限的操作下达到目标...
"烙饼排序"可能是对一种特定排序算法的形象化描述,它可能涉及到比较和交换元素,优化排序效率。 3. **连连看死锁判断**:连连看游戏中的死锁问题可能涉及到图论和状态空间搜索。死锁是并发系统中的一种现象,当两...