编程之美：一摞烙饼排序

记录自己的理解过程，防止遗忘！！

问题：

    星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？”

你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？

首先根据对题目的粗浅理解,写出的代码如下：

public class SortPie{
	public static void main(String[] args){
		int []arr={3,2,1,6,5,4,9,8,7,0};
		System.out.println(sort(arr));;
		
	}

	private static int sort(int[] arr) {
		// TODO Auto-generated method stub
		int len=arr.length;
		int max=0;
		int count=len;
		int result=0;
		while(count!=0){
			for(int i=0;i<len;i++){
				if(max<arr[i]){
					max=arr[i];
					count=i;
				}
			}
			if(count!=len&&count!=len-1)
			{	
				System.out.println(count+"and"+len);
				if(count!=0){
					conver(arr,0,count);
					print(arr);
					result++;
				}
				conver(arr,0,len-1);
				print(arr);
				result++;
				//System.out.println(result);
			}
			len--;
			count=len;
			max=0;
		}
		return result;
	}

	private static void print(int[] arr) {
		// TODO Auto-generated method stub
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}

	private static void conver(int[] arr, int i, int count) {
		// TODO Auto-generated method stub
		int temp;
		for(int j=i;j<(count+1)/2;j++){
			temp=arr[count-j];
			arr[count-j]=arr[j];
			arr[j]=temp;
		}
	}
}
           

这个代码简单的实现了寻找一个解，看了解答，发现果然是自己想少了。题目要求实现 最优解 。

而上面的代码的过程如下：

1.找到未排序数组中最大的，翻转一次（若最大的在未排序的最后的位置，则跳过）

2.未排序数组部分的翻转一次（未排序数组中最大的到了最下面，此时将该最大值划入已排序部分）

3.不断重复1,2直到全部有序

上述方法只是找到一个确定解，而要找到最优解，就要找到全部的解，从中找到最优解。那么只要穷举出所有可能的交换方案，那么一定能够从中找到最优解。

这样思考就转换为找一个翻转策略使用递归把所有的可能全部翻转一遍。

从间距为1到间距为n-1依次翻转，然后递归。

递归的退出条件：

1.烙饼已经有序；

2.递归次数超过最大翻转次数2（n-1）。

由于本题还要求要输出最优翻饼过程，因此还需记录下最优解在二叉树中的搜索路径。

举个例子：

图中两个解的路径分别为{1,2,1,2}和{2,1}

图中路径i所表示的含义为第0个到第i个元素进行翻转，因此有了路径就可以很容易的求出翻转过程。

{2,1}的翻转过程为4,1,2->2,1,4->1,2,4

根据上面的思路，程序如下：

public class BestSortPie {
	static int [] pieArr={3,2,1,6,5,4,9,8,7,0};//烙饼原始数组
	static int searchtime=0;//调用search函数的次数
	static int pieNum=pieArr.length;//烙饼个数
	static int maxSwapTime=pieNum*2;//整个过程最大交换次数
	static int [] path=new int[maxSwapTime];//保存烙饼翻转的分支路径
	
	public static int[] resultPath=new int[maxSwapTime];//保存烙饼翻转的最终分支路径
    public static int[] tempPath=new int[maxSwapTime];//保存烙饼翻转的临时分支路径
	public static void main(String [] args){
		search(0);//从初始状态开始
		System.out.println("最大的交换次数为："+maxSwapTime);
		System.out.println("搜索次数为"+searchtime);
		System.out.print("初始序列为：");
		print(pieArr);
		for(int i = 0; i < maxSwapTime; i++){
			revert(pieArr,0,resultPath[i]);//根据选择的分支路径来对烙饼ji
			System.out.print("经过"+(i+1)+"次翻转后为：");
			print(pieArr);
		}
            
	}
	private static int lowBound(int[] pieArr) {//确定下界
		// TODO Auto-generated method stub
		 int t, ret = 0;
	        for(int i = 1; i < pieArr.length; i++){
	            t = pieArr[i] - pieArr[i-1];
	            if( (t==1) || (t == -1)){//若两个数之间相邻，则不需翻转。
	            }
	            else{
	                ret ++;
	            }        
	        }
	        return ret;        
	}

	private static void search(int step) {
		// TODO Auto-generated method stub
		int i;
		int minSwapTime=lowBound(pieArr);
		searchtime++;
		if(step+minSwapTime>=maxSwapTime){//step表示已经翻转的次数，minSwapTime表示接下来最少还要翻转几次
			return;
		}
		
		if(isSorted(pieArr)){//判断是否已有序
			if(step<maxSwapTime){
				maxSwapTime=step;
				for(i = 0; i <maxSwapTime; i++)//记录解的路径
                    resultPath[i] =tempPath[i];
			}
			return;
		}
		
		for(i=1;i<pieNum;i++){
			revert(pieArr,0,i);//翻转
			tempPath[step]=i;//记录当前解的路径
			search(step+1);//递归搜索
			revert(pieArr,0,i);//翻转回上一步，相当于退回一步
		}
	}
	private static void print(int[] arr) {
		// TODO Auto-generated method stub
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	private static void revert(int[]pieArr,int i, int count) {
		// TODO Auto-generated method stub
		int temp;
		if(count>i){
			for(int j=i;j<(count+1)/2;j++){
				temp=pieArr[count-j];
				pieArr[count-j]=pieArr[j];
				pieArr[j]=temp;
			}
		}
	}

	private static boolean isSorted(int[] pieArr) {
		// TODO Auto-generated method stub
		for(int i = 1; i < pieArr.length; i++)        
            if( pieArr[i-1] > pieArr[i])
                return false;
        return true;    
	}

	
}
           

但是上述代码还存在一些问题，有很多重复搜索，效率较低。如何确定剪枝条件使得更多的搜索不必再重复进行，提高效率以最快的速度得到最优解？仍然待优化。