`

编程之美-烙饼排序

 
阅读更多
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));
	}
	
}


0
0
分享到:
评论

相关推荐

    华为oj烙饼排序

    【华为OJ烙饼排序】是华为在线测评平台(OpenJudge)上的一道高级编程题目,主要考察的是排序算法的应用和实现。烙饼排序(Flipping Sorting),也称为煎饼排序,是一种基于比较的排序算法,它的灵感来源于煎饼翻转...

    翻转烙饼排序问题(C语言源码)

    然而,翻转烙饼排序因其独特的解决思路和算法设计,仍然是学习算法设计原则和优化技巧的重要案例之一。 ### 结论 翻转烙饼排序问题不仅考验了算法设计的能力,也体现了对数据结构和排序算法原理的深刻理解。通过...

    烙饼排序算法和买书问题源码

    《程序之美-C语言:烙饼排序算法与买书问题源码》 在计算机科学的世界里,算法是解决问题的关键。本文将深入探讨两个编程问题:烙饼排序算法和买书问题,这两个问题都涉及到C语言的高效实现。我们将通过源代码分析...

    经典算法,当然是经典了

    标签中的“烙饼问题”是一种经典的排序问题,也被称为煎饼排序。在这个问题中,想象一个平底锅可以同时煎两张饼,而我们要对多张饼进行排序,每次只能翻转一张或两张饼。烙饼问题展示了如何在有限的操作下达到目标...

    oj软件课设(C语言版本代码)

    "烙饼排序"可能是对一种特定排序算法的形象化描述,它可能涉及到比较和交换元素,优化排序效率。 3. **连连看死锁判断**:连连看游戏中的死锁问题可能涉及到图论和状态空间搜索。死锁是并发系统中的一种现象,当两...

Global site tag (gtag.js) - Google Analytics