分治算法（divide and conquer）

目录

简介

流程

例题

循环比赛日程

---

预计阅读时间：10分钟

简介

        分治(divide and conquer)，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法（快速排序，归并排序)等等。

 

流程

✓分解
将原问题分解为若干规模较小，相互独立，与原问题相同的子问题。
✓解决
若干子问题较小而容易被解决则直接解决，否则再继续分解为更小的子问题，直到容易解决。
✓合并
将已求解的各个子问题的解，逐步合并为原问题的解。

例题

循环比赛日程

题目描述

设有 n 位选手的循环比赛，其中 n = 2^m，m 为正整数。要求每位选手要与其他 n-1 位选手都赛一次。每名选手每天比赛一次，循环赛共进行 n-1 天，要求每天没有选手轮空。下面是 8 位选手时（m = 3）的循环比赛表，表中第一行为 8 位选手的编号，下面 7 行，依次是每位选手每天的对手。

 

输入INPUT：

输入格式

输入共 1 行。 第一行 一个整数 n，表示有 n 名运动员参加循环赛 。（n≤64）

输入样例

4

输出OUTPUT：

输出格式

输出一个 n * n 表格，表示 n 名运动员及其每天比赛的日程。为使表格清晰，请采用 %4d 的输出格式。

输出样例

1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

题目分析

这样，8位选手的循环比赛表可以有四名选手的循环比赛表根据对称性“生成出来”。

同理，4位选手的循环比赛表可以由2位选手的循环比赛表根据对称性生成出来。

所以，本题的“分治”思想很明显，即不断地把一个规模为n的构造问题分成4个规模为n/2的子问题，然后，从这些子问题的解构造出整个问题的解

参考代码

#include 
using  namespace std;
int n,a[71][71];
int main()
{
    cin>>n;
    a[1][1]=1;
    for(int s=1; s2)
    {
        for(int i=1; i<=s; i++)
        {
            for(int j=1; j<=s; j++)
            {
                a[i+s][j+s]=a[i][j];
                a[i][j+s]=a[i][j]+s;
                a[i+s][j]=a[i][j]+s;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            printf("%4d",a[i][j]);
        }
        cout<
    }
    return 0;
}