浅析分治法

1、分治法思想：

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

2.分治法特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

3.分治法的基本步骤

分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

合并：将各个子问题的解合并为原问题的解。

4.例题分析

（1）归并排序

     分析：将要排序的序列每次折半分解。当只有一个元素时，这个元素显然是有序的，这时返回，然后把各个子问题合并，排序完成。对数列进行分治时一般采用折半分解和选取阀值（比这个值小的放左边，大的放右边）分解，传入的参数是第一个元素和最后一个元素的下标。

     代码：

//分解

void resolve(int* a,int low,int high)

{

    int mid;

    if(low==high)

       return;

    mid=(low+high)/2;

    resolve(a,low,mid);//分解左边

    resolve(a,mid+1,high);//分解右边

    merge(a,low,mid,high);//合并

}

（2）选择第K小元素

     分析：这个题目跟快速排序的思路差不多，选取一个阀值（我选的是第一个元素）进行分解，比这个值小的是左半部分，大的是右半部分。然后比较K和这个值的下标，若相等，则这个值是第k小元素，若k更大，则第k小元素在右半部分，k更小在左半部分。当然这个题目跟快速排序的题目一样，不需要进行合并。

   代码：

//同样用分治法选择第K小元素

int indexMin(int *a,int low,int high,int k)

{

         int i=low,j=high,index=low;

         int temp,dir=0;

         //选择一个元素为临界值，把比这个数小的放左边，比它大的放右边

         while(i<=j){

                   if(!dir)

                       if(a[j]<a[index]){

                            temp=a[j];

                                a[j]=a[index];

                                a[index]=temp;

                                index=j;

                                     dir=1;

                            }else

                                     j--;

                   if(dir)

                       if(a[i]>a[index]){

                            temp=a[i];

                                a[i]=a[index];

                                a[index]=temp;

                                index=i;

                                     dir=0;

                            }else

                                     i++;

         }

         //分三种情况

         if(index==k)

                   return a[index];

         else if(k<index)

        return indexMin(a,low,index-1,k);

         else

        return indexMin(a,index+1,high,k);

}

（3）求一串数列（存放在a数组里面）的最大子段和

分析：进行折半分解。存在三种情况：1.最大字段和在左半部分2.最大字段和在右半部分3.最大字段由左半部分的部分元素和右半部分的部分元素组合而成。对这三种情况进行合并。

代码：

//求一串数列（存放在a数组里面）的最大子段和

int maxSum(int* a,int low,int high)

{

         int i,temp=0;

         int maxLeft,maxRight,maxLR;

         int mid=(low+high)/2;

         //当只有两个数时，最大字段和要么是第一个数，或是第二个数，或者是两者之和

         if(high-low<=1){

                   if(a[low]+a[high]>a[low] && a[low]+a[high]>a[high])

                            return a[low]+a[high];

                   else

                            return a[high]>a[low]?a[high]:a[low];

         }

 

         //分解

    maxLeft=maxSum(a,low,mid);//1.求左边的最大字段和

         maxRight=maxSum(a,mid+1,high);//2.求右边的最大字段和

   

         //3.当最大字段和是左边和右边的某一部分数合并而成时的最大字段和

         maxLR=a[mid];

         for(i=mid;i>=low;i--){

             temp+=a[i];

                   maxLR=maxLR>temp?maxLR:temp;

         }

         temp=maxLR;

         for(i=mid+1;i<=high;i++){

        temp+=a[i];

             maxLR=maxLR>temp?maxLR:temp;

         }

 

         //合并，返回三种情况中求出的最大字段和中的最大值

         if(maxLR>maxRight && maxLR>maxLeft)

                   return maxLR;

         else

                   return maxRight>maxLeft?maxRight:maxLeft;

}

（4）其他题目

     棋盘覆盖：将棋盘进行分解，每分解一次就有四个子棋盘，其中有一个子棋盘中有特殊方格，用一个L型骨牌覆盖无特殊方格的三个棋盘的结合处，这样四个子棋盘都有特殊方格。再对每一个子棋盘进行分解，重复上述步骤。直到分解为2*2的棋盘则返回。

 

循环日程赛：把参赛选手分为两部分，当只有两个人时，只进行一场比赛。

 

求一列数中的最大值

 

快速排序

/*
 * 归并法进行排序(分治法)
 */

#include<stdio.h>

//合并
void merge(int *a,int low,int mid,int high)
{
	//把a中的两个子数组有序的合并到b数组中（[low,mid]和[mid+1,high]两个数组）
	int b[10];
	int k=low;
	int i=low,j=mid+1;//i指向第一个数组，j指向第二个数组
	while(i<=mid && j<=high){
		if(a[i]<a[j])
			b[k++]=a[i++];
		else
			b[k++]=a[j++];
	}
	if(i<=mid)
		while(i<=mid)
			b[k++]=a[i++];
	else if(j<=high)
		while(j<=high)
			b[k++]=a[j++];
	//把排好序的数组b复制回a数组中对应的元素
	for(i=low;i<=high;i++)
		a[i]=b[i];
}


//分解
void resolve(int* a,int low,int high)
{
	int mid;
	if(low==high)
		return;
	mid=(low+high)/2;
	resolve(a,low,mid);//分解左边
	resolve(a,mid+1,high);//分解右边
	merge(a,low,mid,high);//合并
}

void main()
{
	int i;
	int a[10]={4,5,14,-5,-8,2,0,3,3,1};
	resolve(a,0,9);
    for(i=0;i<10;i++)
		printf("%-5d",*(a+i));
	printf("\n");
}

 

 

 

/*
 * 最大子段和问题（分治法）
 * 数组中的最大值（分治法）
 * 选择第k小元素（分治法）
 */

#include<stdio.h>

//求一串数列（存放在a数组里面）的最大子段和
int maxSum(int* a,int low,int high)
{
	int i,temp=0;
	int maxLeft,maxRight,maxLR;
	int mid=(low+high)/2;
	//当只有两个数时，最大字段和要么是第一个数，或者是第二个数，或者是两者之和
	if(high-low<=1){
		if(a[low]+a[high]>a[low] && a[low]+a[high]>a[high])
			return a[low]+a[high];
		else
			return a[high]>a[low]?a[high]:a[low];
	}

	//分解
    maxLeft=maxSum(a,low,mid);//1.求左边的最大字段和
	maxRight=maxSum(a,mid+1,high);//2.求右边的最大字段和
    
	//3.当最大字段和是左边和右边的某一部分数合并而成时的最大字段和
	maxLR=a[mid];
	for(i=mid;i>=low;i--){
	    temp+=a[i];
		maxLR=maxLR>temp?maxLR:temp;
	}
	temp=maxLR;
	for(i=mid+1;i<=high;i++){
        temp+=a[i];
	    maxLR=maxLR>temp?maxLR:temp;
	}

	//合并，返回三种情况中求出的最大字段和中的最大值
	if(maxLR>maxRight && maxLR>maxLeft)
		return maxLR;
	else
		return maxRight>maxLeft?maxRight:maxLeft;
}

//同样用分治法可以求出这个数组中的最大值
int max(int* a,int low,int high)
{
	int maxLeft,maxRight;
	//当小于两个元素时，直接返回较大的那个元素
	if(high-low<=1)
		return a[low]>a[high]?a[low]:a[high];
	//分解
	maxLeft=max(a,low,(low+high)/2);
	maxRight=max(a,(low+high)/2+1,high);
	//合并
	return maxLeft>maxRight?maxLeft:maxRight;
}


//同样用分治法选择第K小元素
int indexMin(int *a,int low,int high,int k)
{
	int i=low,j=high,index=low;
	int temp,dir=0;
	//选择一个元素为临界值，把比这个数小的放左边，比它大的放右边
	while(i<=j){
		if(!dir)
    		if(a[j]<a[index]){
	       		temp=a[j];
	    		a[j]=a[index];
		    	a[index]=temp;
		    	index=j;
				dir=1;
			}else
				j--;
		if(dir)
    		if(a[i]>a[index]){
	       		temp=a[i];
	    		a[i]=a[index];
		    	a[index]=temp;
		    	index=i;
				dir=0;
			}else
				i++;
	}
	//分三种情况
	if(index==k)
		return a[index];
	else if(k<index)
        return indexMin(a,low,index-1,k);
	else
        return indexMin(a,index+1,high,k);
}

void main()
{
	int a[10]={-20,11,-4,13,-5,-2};
	printf("max sub sum : %d\n",maxSum(a,0,6));
	printf("max value : %d\n",max(a,0,6));
	printf("第2小元素时 : %d\n",indexMin(a,0,6,1));
}