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

编程之美-光影切割问题

发表于: 2012-06-19   作者:bylijinnan   来源:转载   浏览:
摘要: package a; public class DisorderCount { /**《编程之美》“光影切割问题” * 主要是两个问题: * 1.数学公式(设定没有三条以上的直线交于同一点): * 两条直线最多一个交点,将平面分成了4个区域; * 三条直线最多三个交点,将平面分成了7个区域; * 可以推出:N条直线 M个交点,区域数为N+M+1。
package a;

public class DisorderCount {

	/**《编程之美》“光影切割问题”
	 * 主要是两个问题:
	 * 1.数学公式(设定没有三条以上的直线交于同一点):
	 * 两条直线最多一个交点,将平面分成了4个区域;
	 * 三条直线最多三个交点,将平面分成了7个区域;
	 * 可以推出:N条直线 M个交点,区域数为N+M+1。
	 * 2.逆序数的分治求法:
	 * 交点M的个数就是逆序数对的对数。
	 * 例如左边的光线顺序是(1,2,3),右边是(3,2,1)。那么(3,1)(3,2)(2,1)共三个逆序数对,说明有三个交点。
	 * 归并排序来求逆序数。假设以下数据a1.a2.a3.a4分为两段,此时需要计算它们的逆序数,前半部分a1.a2,后半部分a3.a4.
	 * (这两个部分都是已经排好序的)。如果当前a1>a3,那么可以知道a2>a3,那么当前的逆序为2.即index(a2)-index(a1)+1.
	 * 将两个数组合并的时候,注意一下左边的数组有多少个数比右边的数组的多少数值要大
	 */

	private int count=0;
	
	public static void main(String[] args) {
		int[][] array={
				{4,3,2,1},
				{4,2,3,1},
				{1,2,3,4},
				{3,1,2},
				{2},
		};
		for(int[] each:array){
			DisorderCount test=new DisorderCount();
			int count=test.disorderCount(each);
			System.out.println(count);
		}
		
	}

	public int disorderCount(int[] array){
		if(array==null){
			return -1;
		}
		if(array.length<2){
			return 0;
		}
		disorderCountHelp(array,0,array.length-1);
		return count;
	}
	
	public void disorderCountHelp(int[] array,int start,int end){
		if(start<end){
			int mid=start+(end-start)/2;
			disorderCountHelp(array,start,mid);
			disorderCountHelp(array,mid+1,end);
			merge(array,start,mid,end);
		}
	}
	
	public void merge(int[] array,int start,int mid,int end){
		int i=start;
		int j=mid+1;
		int len=end-start+1;
		int[] tmp=new int[len];
		int k=0;
		while(i<=mid&&j<=end){
			if(array[i]<=array[j]){
				tmp[k++]=array[i++];
			}else{
				tmp[k++]=array[j++];
				count+=mid-i+1;//Each part is sorted.It means the data from a[i] to a[mid] is bigger than a[j].
			}
		}
		while(i<=mid){  
            tmp[k++]=array[i++]; 
        }  
        while(j<=end){  
            tmp[k++]=array[j++];  
        }  
        for(int m=0;m<k;m++){
        	array[start+m]=tmp[m];
        }
	}
}

编程之美-光影切割问题

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
“光影切割问题”是游戏场景中经常出现的,例如一些房屋场景里面,在里面上会因为阳光从屋顶的漏洞
最近在看微软研究院出版的《编程之美》一书,对于该书中提到的一些问题,特别感觉兴趣,比如下面这
最近在看微软研究院出版的《编程之美》一书,对于该书中提到的一些问题,特别感觉兴趣,比如下面这
问题描述   假设在中国象棋中只剩下将帅两个棋子,国人都知道基本规则:将帅不能出九宫格,只能上
下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中,许多
题目: 下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中
from: http://www.cnblogs.com/python27/archive/2012/04/08/2438009.html 题目描述 现在有一架飞机
问题描述 在中国象棋里将和帅是不能碰面的,如下图所示,当将位于d10时,帅就不能在d1,、d2、d3。请
中国象棋中,将帅相隔遥远,并且不能照面,假设棋盘上只有将和帅两字,如下图所示(A表示将,B表示
编程之美 1.2 中国象棋将帅问题 版权所有, 禁止转载, 如有需要, 请站内联系. 本文地址: http://blog
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号