分治算法

使用分治算法设计程序时,一般可以按以下步骤进行:

? ? ? ?(1)分解:将要求的问题划分成若干规模较小的同类问题;

? ? ? ?(2)求解:当子问题划分的足够小时,用较简单的方法解决;

? ? ? ?(3)合并:按求解问题的要求,将子问题的解逐层合并,即可构成最终的解.

实例:乒乓球比赛赛程安排

?

?

根据分治算法的思想,我们应该将问题进行拆分成规模较小的同类问题.

?

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 循环赛日程4人

?

?

? ? ? ? ? ? ? ? ? ? ? 循环赛日程2人

?

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?循环赛日程4人

?这样就可以通过解决小规模的问题来一步步实现整体
?Java代码描述:

?

public class Test {
	static int[][] is = null;
	static int m = 0;
	static{
		System.out.println("请输入参赛选手人数:");
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		is = new int[m+1][m+1];
	}
	
	public static void main(String[] args) {
		int i,j;
		j = 2;
		for(i=2;i<8;i++){
			j=j*2;
			if(j==m){
				break;
			}
		}
		if(i>=8){
			System.out.println("参赛选手人数必须为2的整数次幂,且不超过64!");
			return;
		}
		gamecal(1, m);
		System.out.print("NUM\t");
		for(i=2;i<=m;i++){
			System.out.print("第"+(i-1)+"天 \t");
		}
		System.out.println();
		for(i = 1;i<=m;i++){
			for(j=1;j<=m;j++){
				System.out.print(is[i][j]+"\t");
			}
			System.out.println();
		}
	}
	public static void gamecal(int k,int n){
		int i = 0 ,j = 0;
		if(n==2){
			is[k][1] = k;		//参赛选手编号
			is[k][2] = k+1;		//对阵选手编号
			is[k+1][1] = k+1;	//参赛选手编号
			is[k+1][2] = k;		//对阵选手编号
		}else{
			gamecal(k,n/2);
			gamecal(k+n/2,n/2);
			for(i=k;i<k+n/2;i++){	//填充右上角
				for(j=n/2+1;j<=n;j++){
					is[i][j] = is[i+n/2][j-n/2];
				}
			}
			for(i=k+n/2;i<k+n;i++){	//填充左下角
				for(j=n/2+1;j<=n;j++){
					is[i][j] = is[i-n/2][j-n/2];
				}
			}
		}
	}
	
}

?运行结果:

?

?

分治算法

原文：http://bbllmyd.iteye.com/blog/2302275