编程之美:烙饼排序问题

书中的题目描述：

 

星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：

“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。

我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？

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

这个排序问题非常有意思，首先我们要弄清楚解决问题的关键操作——“单手每次抓几块饼，全部颠倒”。

 

 

 

每次我们只能选择最上方的一堆饼，一起翻转。而不能一张张地直接抽出来，然后进行插入，也不能交换任意两块饼子。这说明基本的排序办法都不太好用。那么怎么把这n个烙饼排好序呢？

由于每次操作都是针对最上面的饼，如果最底层的饼已经排序，那我们只用处理上面的n-1个烙饼。这样，我们可以再简化为n-2、n-3，直到最上面的两个饼排好序。

 

具体可见附件电子书

 

 

用javascript实现下：演示@google code

 

 

不要用ie折磨自己了，chrome最快，ff勉强

 

<script type="text/javascript">
	
	Array.prototype.clone=function(){
		return this.slice(0,this.length);
	};
	
	function FlapJack(arr){
		this._original=arr;
		
		//工作数组，会经常变化的
		this._work=arr.clone();
		
		//最终有序数组
		this._result=[];
		
		//最优翻转步鄹
		this._reverseStep=[];
		
		//记录枚举状态的中间翻转步鄹
		this._workReverseStep=[];
		
		//总共调用了多少次search操作
		this._totalSearchCount=0;
		
		//初始上限，最多2.(n-1)次翻转可以有序
		this.maxStep=2*(arr.length-1);
	}
	
	FlapJack.prototype.run=function(){
		this.search(0);
	};
	
	FlapJack.prototype.search = function(step){
		this._totalSearchCount++;
		
		//当前工作数组达到有序的最少翻转此数
		var nEstimate = this.lowerBound(this._work);
		
		//已经超过当前上限，忽略，剪枝
		if(nEstimate + step > this.maxStep || step >= this.maxStep) return;
		
		//已经完成要求有序
		if(this.isSorted(this._work)) {
			//当前步鄹为最优，记录当前步鄹详情
			if(step < this.maxStep) {
				this.maxStep = step;
				this._reverseStep=this._workReverseStep.slice(0,step);
				this._result=this._work.clone();
				return;
			}
		}
		
		
		//枚举搜索
		for(var i=1;i<this._work.length;i++) {
			//0...i 翻转
			this.reverse(this._work,0,i);
			//记录翻转步鄹
			this._workReverseStep[step]=i;
			//继续枚举搜索
			this.search(step+1);
			//还原继续搜索
			this.reverse(this._work,0,i);
		}
		
		
	};
	
	FlapJack.prototype.isSorted=function(arr) {

        for(var i = 1; i < arr.length; i++){
            if(arr[i-1] > arr[i]) {
                return false;
            }
        }
        return true;
   };
	
	//下界计算，凡是有两个位置相邻尺寸不相邻的都需要至少一次翻转将它们分开
	FlapJack.prototype.lowerBound=function(arr){
		var ret=0;
		for(var i=1;i<arr.length;i++) {
			if(Math.abs(arr[i]-arr[i-1])!=1)
				ret++;
		}
		return ret;
	};
	
	
	//
	FlapJack.prototype.reverse = function(arr,begin,end) {
		
		var i=begin,
				j=end,
				t=0;
		
		for(;i<j;i++,j--) {
			t=arr[i];
			arr[i]=arr[j];
			arr[j]=t;
		}		
	};
	
	
	if(!window['consoleH']) {
		consoleH={
			log:function(msg){
				document.writeln(msg+"<br />");
				//alert(msg);
			}
		};
	}
	
	(function main(){		
		
		var fj=new FlapJack([3, 2, 1, 6, 5, 4 ,9, 8 ,7, 0]);
		fj.run();
		
		consoleH.log("初始结果 [ "+[3, 2, 1, 6, 5, 4 ,9, 8 ,7, 0]+" ]");	
		consoleH.log("搜索次数 "+fj._totalSearchCount);
		consoleH.log("最终有序结果 [ "+fj._result+" ]");			
		consoleH.log("最优翻转次数 "+fj.maxStep);		
		consoleH.log("最优翻转步鄹 "+fj._reverseStep);	
		
	})();
	
</script>