数据结构与算法之分治法

前言

分治法首先需要明白递归的概念:

递归： 是指子程序直接调用自己或者通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。递归的两个基本要素：
1.边界条件:也就是递归终止调用的条件。
2.递归出口:递归表达式，大问题分解为小问题。

分治算法的一般有几个步骤：

1. 分解 ：分析原来的问题，将原问题分解成一系列子问题。
2. 求解：递归求解各个子问题。若子问题足够小，则直接求解。
3. 合并：将子问题的解合并成原问题的解。

以下将分析几个典型例子。

1.递归解决阶乘函数

阶乘函数的定义大家都知道。
1）边界条件 n=0,n!=1
2) 递归体 n>0,n!=n*(n-1)

C语言代码：

/**
 1. 阶乘的算法
 2. @param n
 3. @return
 */
int Fac(int n){
    if(n==0)
        return 1;
    else
        return n* Fac(n-1);
}

2.归并排序算法

2.1 归并排序的概念

归并排序是将待排序的元素分成两个大致相同的两个子序列，分别对子序列进行排序，最终将排好序的子序列合并为排序的序列。

2.2 分治法的三步曲

大致分为以下几步：

1. 分解。将n个元素分成n/2个元素的子序列。
2. 求解。用归并排序对两个子序列递归排序。
3. 合并。合并两个排序好的子序列得到排序结果。

2.3 归并排序的动画

2.4 归并排序算法(C语言代码)

/**
 * 归并排序
 * @param a 待排序的数组
 * @param l 左边的
 * @param r 右端
 */
void MergeSort(int a[],int l, int r){
    //计算分组的中间位置
    int m;
    if (l < r){
        //计算中间的位置
        m = (l+r)/2;
        //递归左边
        MergeSort(a,l,m);
        //递归右边
        MergeSort(a,m+1,r);
        //合并结果
        Merge(a,l,m,r);
    }
}
/**
 * 合并排序的结果
 * @param a
 * @param l
 * @param m
 * @param r
 */
void Merge(int a[], int l, int m, int r) {
    //左边的长度，定义右边的长度
    int lLen=m-l+1 ,rLen=r-m;
    //定义临时数组存放左边的排序结果以及右边的排序结果
    int L[50],R[50];
    //取出左边的元素
    for(int i=0 ; i < lLen ; i++){
       L[i]=a[l+i];
    }
    //取出右边的元素
    for(int j = 0 ; j < rLen; j++){
        R[j]=a[m+j+1];
    }
    //很关键，这个值一定要设置为最大
    L[lLen] = INT_MAX;
    R[rLen] = INT_MAX;
    //开始比较大小
    int i=0,j=0;
    for(int k = l; k < r+1 ; k++){
        if(L[i] < R[j]){
            a[k]=L[i];
            i++;
        }else{
            a[k]=R[j];
            j++;
        }
    }
}

测试代码：

3.最大子序列和问题

3.1 问题的定义

给定n个整型数组组成的蓄力A1,A2,…An,求该序列中子序列的字段和的最大值，当所有序列所有的整型均为负数整数时，其最大字段和为0。
example:
当序号为[-2,6,-4,8,-5,3]时，最大子序列的和为10=6+(-4)+8。

3.2 分治的思路

普通的计算，只有循环遍历所有的子段求和进行比较求解，这样的时间复杂度比较高，这种也就是暴力算法解题的思路，第一遍单个元素作为和比较，得出最大和为8，第二次遍历两个连续元素的组合，第三次遍历三个元素的组合，第四次组合…比较简单，这里不在代码。

1. 分解。将序列拆分为n个子序列，最大值分为三种情况，所有序列的和分为三种情况。
   (1) 所有序列的的最大字段和在序列的1/2序列左边的和相同。
   (2) 所有序列的的最大字段和在序列的1/2序列右边的和相同。
   (3) 所有序列的的最大字段和在序列的1/2序列左和右边的和相同。

2. 求解。
   递归分段求解1/2字段和。由于序列是连续的，此问题的关键在于求和的时候从1/2向两边扩展求和，这样就能包含前两种情况，第三种情况是从中间1/2处左右两边子序列和的最大值。

3. 合并。最终的结果就是三个情况的和最大结果。

3.3 简单的分解下代码的结果

以序列[-2,6,-4,8,-5,3]为例。

此处写比较费劲，看代码输出。

3.4 算法代码

/**
 * 打印数组
 * @param a
 * @param left
 * @param right
 */
void printArr(int *a,int left,int right){
    for (int i = left; i <= right ; ++i) {
        printf("%d,",a[i]);
    }
    printf("\n");
}
/**
 * 求解最大的字段序列和
 * @param a
 * @param left
 * @param right
 * @return
 */
int MaxSubSeqSum(int * a,int left,int right){
    int sum = 0 ;
    int i;
    //遍历到单个元素
    if(left == right){
        if(a[left]>0)  sum=a[left];
        else sum=0;
    }else{
        //循环遍历
        int med=(left+right)/2;
        int leftSum= MaxSubSeqSum(a,left,med);
        int rightSum= MaxSubSeqSum(a,med+1,right);
        //计算左边的序列的字段和
        int subLeftSum=0,s1=0;
        printArr(a,left,med);

        for ( i = med; i >=left ; i--) {
            subLeftSum+=a[i];
            if (subLeftSum > s1) s1=subLeftSum;
        }
        printf("the left sum is %d",subLeftSum);
        printf("\n");
        //计算右边的序列的字段和
        printArr(a,med,right);
        int subRightSum=0,s2=0;
        for (i = med+1; i <= right  ; i++) {
            subRightSum+=a[i];
            if (subRightSum > s2) s2=subRightSum;
        }
        printf("the right sum is %d",subRightSum);
        printf("\n");
        //左右两边之和
        sum=s1+s2;
        if(sum < leftSum) sum=leftSum;
        if(sum < rightSum) sum=rightSum;
    }
    return sum;
}

3.5 测试结果

int main(){
    int a[] = {-2,6,-4,8,-5,3};
    int result= MaxSubSeqSum(a,0,5);
    printf("the final result is :%d",result);
}

代码执行递归过程。

-2,
the left sum is -2 
-2,6,
the right sum is 6 
-2,6,
the left sum is 4  
6,-4,
the right sum is -4
8,
the left sum is 8  
8,-5,
the right sum is -5
8,-5,
the left sum is 3  
-5,3,
the right sum is 3 
-2,6,-4,
the left sum is 0 
-4,8,-5,3,        
the right sum is 6
the final result is :10