算法讲解之分治算法

14天阅读挑战赛

1、分治算法是什么？

分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，然后把各部分的解组合成整个问题的解。

现实生活中也有很多这样的例子，比如举行的全国性的Python编程竞赛，如果全国一起进行比赛，那就很难组织，并且人员比较多容易造成分歧。

在这种情况下，如果我们使用分治的思想，把整个赛区分开，先让各个县进行比赛，选各县的前三名，到市里参加比赛，再选各市的前三名参加总赛。

这样就把压力分给了各个赛区，总赛区即能筛选出优秀的人员也能大大的节省时间。还可以把现场精彩的编程，展现给现场的人员和线上的观众。

2、分治算法要素

在实际应用中，什么样的问题才能使用分治算法解决呢？这样的问题需要满足以下3个条件。

• 原问题可分解为若干规模较小的相同子问题。

• 子问题相互独立。

• 子问题的解可以合并为原问题的解。

3、分治算法解题的步骤

• 分解：将想要解决的问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。

• 治理：求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，因此当子问题划分得足够小时，就可以使用较简单的方法来解决。

• 合并：按原问题的要求，将子问题的解逐层合并，构成原问题的解。

4、解决经典问题

二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔
…

5、分治算法实践

解决循环比赛日程表

5.1、问题描述

设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。

输入：M

输出：表格形式的比赛安排表

【样例输入：】http://match.in

3
1

【样例输出：】match.out

1 2 3 4 5 6 7 8

2 1 4 3 6 5 8 7

3 4 1 2 7 8 5 6

4 3 2 1 8 7 6 5

5 6 7 8 1 2 3 4

6 5 8 7 2 1 4 3

7 8 5 6 3 4 1 2

8 7 6 5 4 3 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.2、问题分析

以M=3(即N=23=8)为例，可以根据问题要求，制定出如下图所示的一种方案：

以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。

设有n个选手的循环比赛，其中n=2m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天。要求每天没有选手轮空.以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。

1 2 3 4 5 6 7 8

2 1 4 3 6 5 8 7

3 4 1 2 7 8 5 6

4 3 2 1 8 7 6 5

5 6 7 8 1 2 3 4

6 5 8 7 2 1 4 3

7 8 5 6 3 4 1 2

8 7 6 5 4 3 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.3、算法分析

从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四来看,那么左上角的44的方阵就是前四位选手的循环比赛表,而右上角的44的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,都是4个选手的循环比赛表,所不同的只是选手编号不同而已,将左上角中方阵的所有元素加上4就能得到右上角的方阵.下方的两个方阵表示前四位选手和后四位选手进行交叉循环比赛的情况,同样具有对称性,将右上角方阵复制到左下角即得到1,2,3,4四位选手和5,6,7,8四位选手的循环比赛表,根据对称性, 右下角的方阵应与左上角的方阵相同.这样,八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来.同样地, 四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来,而两名选手的循环比赛表可以说是已知的,这种程序设计方法叫做分治法,其基本思想是把一个规模为n的问题分成若干个规模较小的问题,使得从这些较小问题的解易于构造出整个问题的解。

程序中用数组matchlist记录n名选手的循环比赛表, 整个循环比赛表从最初的11的方阵按上述规则生成出22 的方阵, 再生成出4*4 的方阵,……，直到生成出整个循环比赛表为止.变量half表示当前方阵的大小,也是要生成的下一个方阵的大小的一半 。

5.4、代码实现

#include<cstdio>
const int MAXN=33,MAXM=5;
int matchlist[MAXN][MAXN];
int m;
int main()
{
    printf("Input m:");
    scanf("%d",&m);
    int n=1<<m,k=1,half=1;                              // 1<<m 相当于 2^m
    matchlist[0][0]=1;
    while (k<=m)
    {
        for (int i=0;i<half;i++)                           //构造右上方方阵
            for (int j=0;j<half;j++)
                matchlist[i][j+half]=matchlist[i][j]+half;
        for (int i=0;i<half;i++)                           //对称交换构造下半部分方阵
            for (int j=0;j<half;j++)
            {
                matchlist[i+half][j]=matchlist[i][j+half];    //左下方方阵等于右上方方阵
                matchlist[i+half][j+half]=matchlist[i][j];    //右下方方阵等于左上方方阵
            }
        half*=2;
        k++;
    }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
            printf("%4d",matchlist[i][j]);
        putchar('\n');
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

​