分治算法总结

目录

一. 算法概述

1. 基本概念

2. 算法步骤

3. 算法条件

二. 例题分析

1. 求最大连续子序列的和

2. 归并排序

3. 逆序对问题

4.  棋盘覆盖问题

---

一. 算法概述

1. 基本概念

        分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。  

2. 算法步骤

（1） 划分问题：把问题的实例划分成一个个可以求最优解的子问题。

（2）递归求解： 递归解决子问题。

（3）合并问题：合并子问题的最优解得到原问题的解。

3. 算法条件

（1）问题规模缩小到一定程度可以比较容易的解决（体现大而化小，小而化了）

（2）问题可以分割成几个相同结构的小问题，具有最优子结构

（3）所有子问题的最优解可以合并为问题的最优解

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

        其中（1）是很多问题的共性，任何一个问题缩小到一定规模都可以很容易求出；（2）是分治法的前提，反映了递归思想的调用；（3）是使用分治法的关键，分治法的目的就是用子问题来合成最终问题答案。如果不行，那么则考虑子问题最优解的组合即贪心或者DP；（4）体现分治法效率问题，子问题相互独立可以使用同一套代码递归模式，如果子问题有包含则问题复杂了。

二. 例题分析

1. 求最大连续子序列的和

（1）划分问题： 把序列分成元素数目尽可能相等的左右两部分

（2）递归求解：分别求出位于左半或者位于右半的最大连续序列和

（3）合并问题：合并左右序列连续和的最大值

        注意：当只有一个元素时，最大连续和就是自己，将区间划分为 [x,m)和[m,y)的左闭右开区间 。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1000;
int num[maxn];
int maxnum(int *A,int x,int y)//元素数组，自区间起点，自区间终点[x,y)
{
    if(y-x==1)return A[x];//只有一个元素，返回该元素
    int m = x + (y-x)/2;//取中间划分点（划分问题）
    int maxs = max(maxnum(A,x,m),maxnum(A,m,y));//求左右区间分别的最优解（递归求解）
    int L = A[m-1],R = A[m],sum = 0;
    for(int i = m-1;m>=x;m--)L = max(L,sum+A[i]);//求从中间开始的左右区间合并最优解
    sum = 0;
    for(int j = m;j<y;j++)R = max(R,sum+A[j]);
    return max(maxs,L+R);//取最优（合并问题）
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n){
        for(int i = 0;i<n;i++){
            scanf("%d",&num[i]);
        }
        int ans = maxnum(num,0,n);
        printf("%d\n",ans);
    }
    return 0;
}

2. 归并排序

（1）划分问题：把需要排序的区间从中间划分开，当只有一个元素时排序就是自己

（2）递归求解：把两部分元素分别排序

（3）合并问题：把两个有序表和成为一个，合并时将左右两部分较小的元素分别加入到新表中。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int num[1000];
void merge_Sort(int *A,int x,int y)//排序数组，子序列起点x， 子序列终点y;
{
    if(y-x>1){//只剩一个元素时不用排序
        int m = x + (y-x)/2;//分割点（划分问题）
        merge_Sort(A,x,m);//排序左右部分（递归求解）
        merge_Sort(A,m,y);
        int p = x,q = m,i = x;
        int T[1000];//新表暂存
        while(p<m||q<y){//把排序好的左右两部分合并（合并问题）
            if(p>=m||(q<y&&A[q]<=A[p]))T[i++] = A[q++];//  ||的短路运算符特性
            else  T[i++] = A[p++];
        }
        for(int j = x;j<y;j++){//暂存T放回A里
            A[j] = T[j];
        }
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i = 0;i<n;i++){
            scanf("%d",&num[i]);
        }
        merge_Sort(num,0,n);
        for(int i = 0;i<n;i++){
            printf("%d ",num[i]);
        }
        printf("\n");
    }
    return 0;
}

3. 逆序对问题

给出一列数字序列a1,a2,a3,,,,,,,an, 求这个序列的逆序对数，即有多少个序对（ai,aj)使得i<j但ai>aj，其中n高达1e6。

        直接枚举肯定超时，这里采用分治算法，分治三步如下：

（1）划分问题：将要求解的序列划分为左右两部分，当最后只剩一个元素时没有逆序对

（2）递归求解：求出分别只位于左右两部分的逆序对的数目

（3）合并问题：求出两部分合并后的逆序对数目即统计i在左边而j在右边的逆序对数目

        注意当合并问题时即统计i在左边而j在右边且ai>aj的逆序对数目，就是统计每一个右边的aj有多少个左边的ai大于它，而执行合并时左右两边又都是由小到大排好序的。所以一旦有ai大于aj，则所有ai右边到am的元素都大于aj也就是逆序对数为m-i。

#include <iostream>
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1000000;
typedef long long LL;
int num[maxn],copyd[maxn];
int cnt;
void SortNum(int *A,int x,int y,int *T)
{
    if(y - x>1){
        int m = x+(y-x)/2;
        SortNum(A,x,m,T);//排序统计左边逆序对数目
        SortNum(A,m,y,T);//排序统计右边逆序对数目
        int p = x,q = m,i = x;
        while(p<m||q<y){//统计合并逆序对数目
            if(q>=y||(p<m&&A[p]<=A[q]))T[i++] = A[p++];
            else{
               T[i++] = A[q++];
               cnt+=m-p;//如题所述！
            }
        }
        for(int j = x;j<y;j++)A[j] = T[j];
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n){
        for(int i = 0;i<n;i++){
            scanf("%d",&num[i]);
        }
        cnt = 0;
        SortNum(num,0,n,copyd);
        for(int i = 0;i<n;i++)printf("%d",num[i]);
        printf("\n%d\n",cnt);
    }
    return 0;
}

4.  棋盘覆盖问题

在一个2^k×2^k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。画出最终覆盖棋盘，骨牌用编号表示。

        我们发现，当棋盘分割到边长仅有1时，只有特殊方格，骨牌数量为0；当棋盘分割到边长仅有2时，骨牌放一个就行了；所以`无论多大的棋盘都可以是这两种情况的组合，也就是分而治之，因此我们采用分治法。其步骤如下：

（1）划分问题：我们每次都把棋盘划分为四分之一，边长缩小两倍（但是要想实现如上分治，每一块都得有一个特殊方格，因此我们构造特殊方格，在四个分块的交际处构造一个骨牌使得每一部分都有一个“特殊快”，而构造出来的这个骨牌样子的特殊块就是我们要放置的骨牌以此类推）

（2）递归求解：求解它划分块的骨牌放置

（3）合并问题：合并所有的骨牌

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1024;
int chess[maxn][maxn];//保存最终棋盘
int k,dx,dy,num;//边长，特殊块坐标，骨牌编号
void chessBoard(int r,int c,int x,int y,int sd){//方块左上角行列位置rc，特殊块在此方块左边xy，此方块边长 
    if(sd==1)return;//边长为1退出，无骨牌
    int s = sd/2;//边长折半
    int row  = r + s;//找到方块中心位置
    int clow = c + s;
    int t = ++num;//该方块内放置骨牌的编号（增加）
    if(x<row&&y<clow)chessBoard(r,c,x,y,s);//特殊快在左上角，直接继续递归
    else{//否则，构造特殊快在交界处在右下角标号该骨牌编号为t，由此处递归（特殊块坐标(row-1,clow-1) )
        chess[row-1][clow-1] = t;
        chessBoard(r,c,row-1,clow-1,s);
    }
    if(x<row&&y>=clow)chessBoard(r,clow,x,y,s);//判断特殊块是否在右上角
    else{
        chess[row-1][clow] = t;//否则右上块左下角标号特殊块
        chessBoard(r,clow,row-1,clow,s);
    }
    if(x>=row&&y<clow)chessBoard(row,c,x,y,s);//左下块
    else{
        chess[row][clow-1] = t;
        chessBoard(row,c,row,clow-1,s);
    }
    if(x>=row&&y>=clow)chessBoard(row,clow,x,y,s);//右下块
    else{
        chess[row][clow] = t;
        chessBoard(row,clow,row,clow,s);
    }
}
int main()
{
    while(scanf("%d%d%d",&k,&dx,&dy)!=EOF){
        chess[dx][dy] = num = 0;
        chessBoard(0,0,dx,dy,k);
        printf("Use L %d\n",num);
        for(int i = 0;i<k;i++){
            for(int j = 0;j<k;j++){
                printf("%d\t",chess[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}