当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程之美-烙饼排序

发表于: 2012-06-17   作者:bylijinnan   来源:转载   浏览:
摘要: package beautyOfCoding; import java.util.Arrays; /* *《编程之美》的思路是:搜索+剪枝。有点像是写下棋程序:当前情况下,把所有可能的下一步都做一遍;在这每一遍操作里面,计算出如果按这一步走的话,能不能赢(得出最优结果)。 *《编程之美》上代码有很多错误,且每个变量的含义令人费解。因此我按我的理解写了以下代码: */
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

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
问题描述: 这是前缀翻转排序问题,书上的内容这里不详述,给个电子版下载地址 本文源码编译环境:c
一摞烙饼问题其实是一个很有意思的问题,它的描述是让一摞随机顺序的烙饼通过单手翻转的方式进行排
《编程之美》读书笔记三:烙饼问题与搜索树 薛笛 EMail:jxuedi#gmail.com 前面已经写了一些关于烙饼
《编程之美》读书笔记三:烙饼问题与搜索树 薛笛 EMail:jxuedi#gmail.com 前面已经写了一些关于烙饼
3、题目:能否快速找出一个数组(简单起见,数组中元素值各不一样)中的两个数字,让这两个数字之和
今天开始看编程之美 。第一个问题是CPU的使用率控制,微软的问题果然高大上,我一看就傻了,啥也不
第一章 软件架构是什么 软件架构应该... asoftware architect that the system should be friendly
给定一个前序和中序变量的结果,写一个算法重建这棵树:如: 前序: a b d c e f 中序: d b a e c f
还好看到了,这个以前好早见到过。 用得是辗转相除法。 k =x/y b=x%y 则 x = ky+b 如果一个整数能够
题目:编写一个函数,把一个char组成的字符串循环右移n位。例如:原来是”abcdefghi”,如果n = 2,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号