分治策略

ゝ一世哀愁。 2022-06-09 09:15 179阅读 0赞

分治法基本思想：问题分解（分解成k个规模大致相同的子问题）、子问题递归求解、合并各个子问题的解。

###   对k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 ###

![2010100711281920.png][]

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

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

递归的概念

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

**分治法的适用条件**

分治法所能解决的问题一般具有以下几个特征：

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

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

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

4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。(这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。)

**分治法的基本步骤**

divide-and-conquer(P)

if (|P| <= n0) adhoc(P);   // 解决小规模的问题

divide P into smaller subinstances P1,P2,...,Pk；//分解问题

for (i=1,i<=k,i++)

yi=divide-and-conquer(Pi);  //递归的解各子问题

return merge(y1,...,yk);  //将各子问题的解合并为原问题的解

人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法的复杂性分析

一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P| = n的问题所需的计算时间，则有：

![2010100716272830.jpg][]

通过迭代法求得方程的解:

![2010100716280093.jpg][]

二分搜索技术

给定已按升序排好序的n个元素a\[0:n-1\]，现要在这n个元素中找出一特定元素x。

分析：

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

2、该问题可以分解为若干个规模较小的相同问题;

3、分解出的子问题的解可以合并为原问题的解；

4、分解出的各个子问题是相互独立的。

很显然此问题分解出的子问题相互独立，即在a\[i\]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。

二分搜索实现：

![复制代码][copycode.gif]

/*
       
        主题：二分搜索 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.07 
       
        */
       
        #include 
       
        <
       
        iostream
       
        >
       
        
       
        using
       
        
       
        namespace
       
        std; 
       
        //
       
        查找成功返回value索引，查找失败返回-1
       
        
       
        template 
       
        <
       
        class
       
        T
       
        >
       
        
       
        int
       
        binary_search(T array[],
       
        const
       
        T
       
        &
       
        value,
       
        int
       
        left,
       
        int
       
        right) { 
       
        while
       
        (right 
       
        >=
       
        left) { 
       
        int
       
        m 
       
        =
       
        (left 
       
        +
       
        right) 
       
        /
       
        
       
        2
       
        ; 
       
        if
       
        (value 
       
        ==
       
        array[m]) 
       
        return
       
        m; 
       
        if
       
        (value 
       
        <
       
        array[m]) right 
       
        =
       
        m 
       
        -
       
        
       
        1
       
        ; 
       
        else
       
        left 
       
        =
       
        m 
       
        +
       
        
       
        1
       
        ; } 
       
        return
       
        
       
        -
       
        1
       
        ; } 
       
        int
       
        main() { 
       
        int
       
        array[] 
       
        =
       
        { 
       
        0
       
        ,
       
        1
       
        ,
       
        2
       
        ,
       
        3
       
        ,
       
        4
       
        ,
       
        5
       
        ,
       
        6
       
        ,
       
        7
       
        ,
       
        8
       
        ,
       
        9
       
        }; cout 
       
        <<
       
        
       
        "
       
        0 in array position: 
       
        "
       
        
       
        <<
       
        binary_search(array,
       
        0
       
        ,
       
        0
       
        ,
       
        9
       
        ) 
       
        <<
       
        endl; cout 
       
        <<
       
        
       
        "
       
        9 in array position: 
       
        "
       
        
       
        <<
       
        binary_search(array,
       
        9
       
        ,
       
        0
       
        ,
       
        9
       
        ) 
       
        <<
       
        endl; cout 
       
        <<
       
        
       
        "
       
        2 in array position: 
       
        "
       
        
       
        <<
       
        binary_search(array,
       
        2
       
        ,
       
        0
       
        ,
       
        9
       
        ) 
       
        <<
       
        endl; cout 
       
        <<
       
        
       
        "
       
        6 in array position: 
       
        "
       
        
       
        <<
       
        binary_search(array,
       
        6
       
        ,
       
        0
       
        ,
       
        9
       
        ) 
       
        <<
       
        endl; cout 
       
        <<
       
        
       
        "
       
        10 in array position: 
       
        "
       
        
       
        <<
       
        binary_search(array,
       
        10
       
        ,
       
        0
       
        ,
       
        9
       
        ) 
       
        <<
       
        endl; 
       
        return
       
        
       
        0
       
        ; }

![复制代码][copycode.gif]

算法复杂度分析：

每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。

大整数的乘法

请设计一个有效的算法，可以进行两个n位大整数的乘法运算

小学的方法：O(n^2) 效率太低

分治法:

X = a b;

Y = c d;

X = a\*2^(n/2) + b    Y = c\*2^(n/2) + d

X\*Y = a\*c\*2^n + (a\*d + b\*c)\*2^(n/2) + b\*d

算法复杂度分析：

T(n) = O(1) n = 1

T(n) = 4T(n/2) + O(n) n > 1

T(n) = O(n^2)     没有改进

为了降低时间复杂度，必须减少乘法的次数

(1)X\*Y = a\*c\*2^n + ((a-b)(d-c)+ac+bd)\*2^(n/2) + b\*d

(2)X\*Y = a\*c\*2^n + ((a+b)(d+c)-ac-bd)\*2^(n/2) + bd

细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+b,d+c可能得到n+1位的结果，使问题的规模变大，故不选择第2种方案。

算法复杂度分析：

T(n) = O(1) n = 1

T(n) = 3T(n/2) + O(n) n > 1

T(n) = O(n^log3)  = O(n^1.59)  较大的改进

小学的方法：O(n^2)            效率太低

分治法: O(n^1.59)             较大的改进

更快的方法?? 如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。

Strassen矩阵乘法

对于两个n\*n的矩阵A,B，求其乘积

传统方法：O(n^3)

A和B的乘积矩阵C中的元素C\[i,j\]定义为![2010100716314153.jpg][]

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C\[i\]\[j\]，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n^3)

分治法:

使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：

![2010100716322732.jpg][]

由此可得：

![2010100716325049.jpg][]

算法复杂度分析

T(n) = O(1) n = 2

T(n) = 8T(n/2) + O(n^2) n > 2

T(n) = O(n^3)

为了降低时间复杂度，必须减少乘法的次数。

![2010100716334057.jpg][]

算法复杂度分析

T(n) = O(1) n = 2

T(n) = 7\*T(n/2) + O(n^2) n > 2

T(n) = O(n^log7) = O(n^2.81) 较大的改进

更快的方法??

Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。

在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n^2.376)

### 棋盘覆盖 ###

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

棋盘示例(k = 2)和四种L型骨牌示例：

![2010101321262812.jpg][]

### 分析 ###

当k>0时，将2^k×2^k棋盘分割为4个2^(k-1)×2^(k-1)子棋盘所示。

特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

![2010101321301748.jpg][]

### 算法复杂度 ###

![2010101321304163.jpg][]

### 实现 ###

![复制代码][copycode.gif]

/*
       
        主题：棋盘覆盖 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.10 
       
        */
       
        #include 
       
        <
       
        iostream
       
        >
       
        #include 
       
        <
       
        vector
       
        >
       
        #include 
       
        <
       
        cmath
       
        >
       
        #include 
       
        <
       
        iterator
       
        >
       
        
       
        using
       
        
       
        namespace
       
        std; 
       
        void
       
        __chessboard_cover(vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >&
       
        cheb, 
       
        int
       
        tx,
       
        int
       
        ty, 
       
        int
       
        dx,
       
        int
       
        dy, 
       
        int
       
        size, 
       
        int
       
        &
       
        tile); 
       
        /*
       
        棋盘覆盖主函数 * cheb: 棋盘数组 * dx: 特殊方格的横坐标 * dy: 特殊方格的纵坐标 
       
        */
       
        
       
        void
       
        chessboard_cover(vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >&
       
        cheb,
       
        int
       
        dx,
       
        int
       
        dy) { 
       
        int
       
        tile 
       
        =
       
        
       
        1
       
        ; __chessboard_cover(cheb,
       
        0
       
        ,
       
        0
       
        ,dx,dy,cheb.size(),tile); } 
       
        /*
       
        棋盘覆盖辅助函数 * cheb: 棋盘数组 * tx: 起始横坐标 * ty: 起始纵坐标 * dx: 特殊方格的横坐标 * dy: 特殊方格的横坐标 * size: 棋盘大小 * tile: 骨牌编号 
       
        */
       
        
       
        void
       
        __chessboard_cover(vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >&
       
        cheb, 
       
        int
       
        tx,
       
        int
       
        ty, 
       
        int
       
        dx,
       
        int
       
        dy, 
       
        int
       
        size, 
       
        int
       
        &
       
        tile) { 
       
        if
       
        (size 
       
        ==
       
        
       
        1
       
        ) 
       
        return
       
        ; 
       
        int
       
        t 
       
        =
       
        tile 
       
        ++
       
        ; 
       
        //
       
        L骨牌号
       
        
       
        
       
        int
       
        s 
       
        =
       
        size 
       
        /
       
        
       
        2
       
        ; 
       
        //
       
        分割棋盘 
       
        //
       
        覆盖左上角子棋盘
       
        
       
        
       
        if
       
        (dx 
       
        <
       
        tx 
       
        +
       
        s 
       
        &&
       
        dy 
       
        <
       
        ty 
       
        +
       
        s) { 
       
        //
       
        特殊方格在此子棋盘中
       
        
       
        __chessboard_cover(cheb,tx,ty,dx,dy,s,tile); } 
       
        else
       
        { 
       
        //
       
        此棋盘中无特殊方格,用t号骨牌覆盖下角方格
       
        
       
        cheb[tx 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ][ty 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ] 
       
        =
       
        t; 
       
        //
       
        覆盖其余方格
       
        
       
        __chessboard_cover(cheb,tx,ty,tx 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        , ty 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ,s,tile); } 
       
        //
       
        覆盖右上角子棋盘
       
        
       
        
       
        if
       
        (dx 
       
        >=
       
        tx 
       
        +
       
        s 
       
        &&
       
        dy 
       
        <
       
        ty 
       
        +
       
        s) { 
       
        //
       
        特殊方格在此棋盘中
       
        
       
        __chessboard_cover(cheb,tx 
       
        +
       
        s,ty,dx,dy,s,tile); } 
       
        else
       
        { 
       
        //
       
        用t号L型骨牌覆盖左下角
       
        
       
        cheb[tx 
       
        +
       
        s][ty 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ] 
       
        =
       
        t; __chessboard_cover(cheb,tx 
       
        +
       
        s,ty,tx 
       
        +
       
        s,ty 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ,s,tile); } 
       
        //
       
        覆盖左下角子棋盘
       
        
       
        
       
        if
       
        (dx 
       
        <
       
        tx 
       
        +
       
        s 
       
        &&
       
        dy 
       
        >=
       
        ty 
       
        +
       
        s) { 
       
        //
       
        特殊方格在此棋盘中
       
        
       
        __chessboard_cover(cheb,tx,ty 
       
        +
       
        s,dx,dy,s,tile); } 
       
        else
       
        { 
       
        //
       
        用t号L型骨牌覆盖右上角
       
        
       
        cheb[tx 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ][ty 
       
        +
       
        s] 
       
        =
       
        t; __chessboard_cover(cheb,tx,ty 
       
        +
       
        s,tx 
       
        +
       
        s 
       
        -
       
        
       
        1
       
        ,ty 
       
        +
       
        s,s,tile); } 
       
        //
       
        覆盖右下角子棋盘
       
        
       
        
       
        if
       
        (dx 
       
        >=
       
        tx 
       
        +
       
        s 
       
        &&
       
        dy 
       
        >=
       
        ty 
       
        +
       
        s) { 
       
        //
       
        特殊方格在此棋盘中
       
        
       
        __chessboard_cover(cheb,tx 
       
        +
       
        s,ty 
       
        +
       
        s,dx,dy,s,tile); } 
       
        else
       
        { 
       
        //
       
        用t号L型骨牌覆盖左上角
       
        
       
        cheb[tx 
       
        +
       
        s][ty 
       
        +
       
        s] 
       
        =
       
        t; __chessboard_cover(cheb,tx 
       
        +
       
        s,ty 
       
        +
       
        s,tx 
       
        +
       
        s,ty 
       
        +
       
        s,s,tile); } } 
       
        int
       
        main() { 
       
        int
       
        k 
       
        =
       
        
       
        2
       
        ; 
       
        int
       
        size 
       
        =
       
        pow (
       
        2
       
        ,k); vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >
       
        cheb(size); 
       
        for
       
        (size_t i
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        cheb.size(); 
       
        ++
       
        i) { cheb[i].resize(size); } 
       
        for
       
        (
       
        int
       
        i 
       
        =
       
        
       
        0
       
        ; i 
       
        <
       
        size; 
       
        ++
       
        i) { 
       
        for
       
        (
       
        int
       
        j 
       
        =
       
        
       
        0
       
        ;j 
       
        <
       
        size; 
       
        ++
       
        j) { 
       
        int
       
        dx 
       
        =
       
        i; 
       
        int
       
        dy 
       
        =
       
        j; cout 
       
        <<
       
        
       
        "
       
        dx = 
       
        "
       
        
       
        <<
       
        dx 
       
        <<
       
        
       
        "
       
        , dy = 
       
        "
       
        
       
        <<
       
        dy 
       
        <<
       
        endl; cheb[dx][dy] 
       
        =
       
        
       
        0
       
        ; chessboard_cover(cheb,dx,dy); 
       
        for
       
        (size_t i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        cheb.size(); 
       
        ++
       
        i) { copy(cheb[i].begin(),cheb[i].end(),ostream_iterator
       
        <
       
        int
       
        >
       
        (cout,
       
        "
       
        
       
        "
       
        )); cout 
       
        <<
       
        endl; } cout 
       
        <<
       
        endl; } } 
       
        return
       
        
       
        0
       
        ; }

![复制代码][copycode.gif]

## 线性时间选择 ##

给定线性序集中n个元素和一个整数k，1 ≤ k ≤ n，要求找出这n个元素中第k小的元素。

### 思想 ###

// 在数组a的p到r区间内找到第k小的元素

template<class Type>

Type RandomizedSelect(Type a\[\],int p,int r,int k)

if (p == r)

return a\[p\]; // 如果p，r相等，第n小都是a\[p\]

// 数组a\[p:r\]被随机分成两个部分，a\[p:i\]和a\[i+1:r\]，

// 使得a\[p:i\]中的元素都小于a\[i+1:r\]中的元素。

int i = RandomizedPartition(a,p,r);

j = i - p + 1;

if (k <= j)

return RandomizedSelect(a,p,i,k);

else

return RandomizedSelect(a,i+1,r,k-j);

在最坏情况下，算法randomizedSelect需要O(n^2)计算时间(在找最小元素的时候，总在最大元素处划分)，但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。

如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至多为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。

例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。

### 步骤 ###

第一步，将n个输入元素划分成én/5ù个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共én/5ù个。

第二步，递归调用select来找出这én/5ù个元素的中位数。如果én/5ù是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。

### 分析 ###

### ![2010101321353681.jpg][] ###

### 伪代码 ###

Type Select(Type a\[\], int p, int r, int k)

if (r - p < 75) \{

// 问题的规模足够小，用某个简单排序算法对数组a\[p:r\]排序;

return a\[p + k - 1\];

for (int i = 0; i <= ( r - p - 4 ) / 5 ; i ++ ) \{

将a\[p + 5 \* i\]至a\[p + 5 \* i + 4\]的第3小元素与a\[p+i\]交换位置;

// 找中位数的中位数，r - p - 4即上面所说的n - 5

Type x = Select(a, p, p + (r - p - 4 ) / 5, (r - p - 4) / 10);

// 数据n根据x划分开来

int i = Partition(a,p,r,x);

j = i - p + 1;

if (k <= j)

return Select(a,p,i,k);

else

return Select(a,i+1,r,k-j);

### 算法复杂度分析 ###

![2010101321364034.jpg][]

上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。

### 实现 ###

### ![复制代码][copycode.gif]  /\*  主题：线性时间查找问题   \* 作者：chinazhangjie   \* 邮箱：chinajiezhang@gmail.com   \* 开发语言：C++   \* 开发环境：Code::Blocks 10.05   \* 时间: 2010.10.13    \*/    \#include  < iostream >    \#include  < vector >    \#include  < algorithm >    \#include  < iterator >     using  namespace  std;       /\*  线性时间查找   \* arr: 数据存储数组   \* start:开始查找点   \* end: 结束查找点   \* n: 查找第n小(n = 1,2,3,...,end-start+1)    \*/    template  < class  T >    T linear\_time\_select(vector < T >&  arr, int  start, int  end, int  n)   \{    if  (end  \-  start  <  75 ) \{   sort (arr.begin()  \+  start,arr.begin()  \+  end  \+  1 );    return  arr\[start  \+  n  \-  1 \];   \}       for  ( int  i  =  0 ;i  <  (end  \-  start  \-  4 )  /  5 ;  \++  i) \{   sort (arr.begin()  \+  start  \+  5  \*  i,arr.begin()  \+  start  \+  5  \*  i  \+  5 );   swap ( \* (arr.begin()  \+  start  \+  5  \*  i  \+  2 ), \* (arr.begin()  \+  start  \+  i));   \}    //  找到中位数的中位数      T median  =  linear\_time\_select(arr,start,   start  \+  (end  \-  start  \-  4 )  /  5  \-  1 ,   (end  \-  start  \-  4 )  /  10  \+  1 );       //  数据 arr 根据 median 划分开来      int  middle  =  \_\_partition\_by\_median(arr,start,end,median);    int  distance  =  middle  \-  start  \+  1 ;  //  中位数的位置与start的距离      if  (n  <=  distance)    //  在前半截      return  linear\_time\_select(arr,start,middle,n);    else     //  在后半截      return  linear\_time\_select(arr,middle  \+  1 ,end,n  \-  distance);      \}       //  将arr按照值median划分开来，并返回界限的位置     template  < class  T >     int  \_\_partition\_by\_median(vector < T >  & arr, int  start, int  end,T median)   \{    while  ( true ) \{    while  ( true ) \{    if  (start  ==  end)    return  start;    else  if  (arr\[start\]  <  median)    \++  start;    else     break ;   \}    while  ( true ) \{    if  (start  ==  end)    return  end;    else  if  (arr\[end\]  >  median) \{    \--  end;   \}    else     break ;   \}   swap(arr\[start\],arr\[end\]);   \}   \}    int  main()   \{   vector < int >  arr;    const  int  c  =  2000 ;    for  ( int  i  =  0 ;i  <  c;  \++  i) \{   arr.push\_back(i);   \}    //  随机排列      random\_shuffle(arr.begin(),arr.end());       for  ( int  i  =  1 ; i  <  c \+ 1 ;  \++  i) \{   cout  <<  " find the  "  <<  i  <<  "  element,position is  "     <<  linear\_time\_select(arr, 0 ,c \- 1 ,i)  <<  endl;   \}    return  0 ;   \}     ![复制代码][copycode.gif] ###

## 循环赛日程表 ##

题目表述：

设有n = 2 ^ k 个运动员要进行网球循环赛，设计一个满足以下要求的比赛日程表：

(1)每个选手必须与其他n-1个选手各赛一次；

(2)每个选手一天只能赛一次；

(3)循环赛一共进行n-1天。

按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

![2010101321395991.jpg][]

### 实现 ###

![复制代码][copycode.gif]

/*
       
        主题：循环赛日程表 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.13 
       
        */
       
        #include 
       
        <
       
        iostream
       
        >
       
        #include 
       
        <
       
        vector
       
        >
       
        #include 
       
        <
       
        cmath
       
        >
       
        #include 
       
        <
       
        iterator
       
        >
       
        #include 
       
        <
       
        iomanip
       
        >
       
        
       
        using
       
        
       
        namespace
       
        std; 
       
        void
       
        __table(vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >&
       
        arr,
       
        int
       
        start,
       
        int
       
        end); 
       
        void
       
        round_match_table(vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >&
       
        arr) { 
       
        int
       
        count 
       
        =
       
        arr.size(); 
       
        for
       
        (
       
        int
       
        i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        count;
       
        ++
       
        i) { arr[
       
        0
       
        ][i] 
       
        =
       
        i 
       
        +
       
        
       
        1
       
        ; } __table(arr,
       
        0
       
        ,count
       
        -
       
        1
       
        ); } 
       
        void
       
        __table(vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >&
       
        arr,
       
        int
       
        start,
       
        int
       
        end) { 
       
        if
       
        (end 
       
        -
       
        start 
       
        +
       
        
       
        1
       
        
       
        ==
       
        
       
        2
       
        ) { arr[
       
        1
       
        ][start] 
       
        =
       
        arr[
       
        0
       
        ][end]; arr[
       
        1
       
        ][end] 
       
        =
       
        arr[
       
        0
       
        ][start]; 
       
        return
       
        ; } 
       
        int
       
        half 
       
        =
       
        (end 
       
        -
       
        start 
       
        +
       
        
       
        1
       
        ) 
       
        /
       
        
       
        2
       
        ; 
       
        //
       
        左上角
       
        
       
        __table(arr,start,start 
       
        +
       
        half 
       
        -
       
        1
       
        ); 
       
        //
       
        右上角
       
        
       
        __table(arr,start 
       
        +
       
        half,end); 
       
        //
       
        左下角
       
        
       
        
       
        for
       
        (
       
        int
       
        i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        half; 
       
        ++
       
        i) { 
       
        for
       
        (
       
        int
       
        j 
       
        =
       
        start; j 
       
        <=
       
        end; 
       
        ++
       
        j) { arr[i 
       
        +
       
        half][j
       
        -
       
        half] 
       
        =
       
        arr[i][j]; } } 
       
        //
       
        右下角（其实左下角和右下角可以在上一个循环中实现的， 
       
        //
       
        但是为了算法结构清晰，因此分为两个循环）
       
        
       
        
       
        for
       
        (
       
        int
       
        i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        half; 
       
        ++
       
        i) { 
       
        for
       
        (
       
        int
       
        j 
       
        =
       
        start; j 
       
        <
       
        end; 
       
        ++
       
        j) { arr[i 
       
        +
       
        half][j 
       
        +
       
        half] 
       
        =
       
        arr[i][j]; } } } 
       
        int
       
        main() { 
       
        int
       
        k 
       
        =
       
        
       
        4
       
        ; 
       
        int
       
        size 
       
        =
       
        pow(
       
        2
       
        ,k); vector
       
        <
       
        vector
       
        <
       
        int
       
        >
       
        
       
        >
       
        arr(size); 
       
        for
       
        (
       
        int
       
        i 
       
        =
       
        
       
        0
       
        ; i 
       
        <
       
        size; 
       
        ++
       
        i) { arr[i].resize(size); } round_match_table(arr); 
       
        for
       
        (
       
        int
       
        i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        size; 
       
        ++
       
        i) { 
       
        for
       
        (
       
        int
       
        j 
       
        =
       
        
       
        0
       
        ;j 
       
        <
       
        size; 
       
        ++
       
        j) { cout 
       
        <<
       
        std::setw(
       
        3
       
        ) 
       
        <<
       
        arr[i][j]; } cout 
       
        <<
       
        endl; } 
       
        return
       
        
       
        0
       
        ; }

![复制代码][copycode.gif]

Gray码问题

实现

### ![复制代码][copycode.gif]  /\*  主题：gray码   \* 作者：chinazhangjie   \* 邮箱：chinajiezhang@gmail.com   \* 开发语言：C++   \* 开发环境：Code::Blocks 10.05   \* 时间: 2010.10.15    \*/    \#include  < iostream >    \#include  < vector >    \#include  < iterator >    \#include  < cmath >     using  namespace  std;       /\*  gray code   \* rows: 行数(2^n)   \* cols: 列数(n)   \* arr: rows行，cols列的存储数组    \*/        void  gray\_code( int  rows, int  cols,vector < vector < int >  >&  arr)   \{    //  第一行，递归结束      if  (rows  ==  1 )    return  ;       //  确定第一列，前半部分为0,后半部分为1      for  ( int  i  =  0 ; i  <  rows  /  2 ;  \++  i) \{   arr\[i\]\[cols  \-  1 \]  =  0 ;   arr\[rows  \-  i  \-  1 \]\[cols  \-  1 \]  =  1 ;   \}       //  递归完成rows列数据第cols列      gray\_code(rows  /  2 , cols  \-  1 ,arr);       //  对称复制      for  ( int  k  =  rows  /  2 ; k  <  rows;  \++  k) \{    for  ( int  j  =  0 ;j  <  cols  \-  1 ;  \++  j) \{   arr\[k\]\[j\]  =  arr\[rows  \-  k  \-  1 \]\[j\];   \}   \}   \}       int  main()   \{    const  int  cols  =  3 ;    int  rows  =  pow( 2 ,cols);   vector < vector < int >  >  arr(rows);    for  (size\_t i  =  0 ;i  <  arr.size();  \++  i) \{   arr\[i\].resize(cols);   \}   gray\_code(rows,cols,arr);       //  output      for  (size\_t i  =  0 ;i  <  arr.size();  \++  i) \{   copy(arr\[i\].rbegin(),arr\[i\].rend(),ostream\_iterator < int > (cout, "  " ));   cout  <<  endl;   \}    return  0 ;   \}     ![复制代码][copycode.gif]     归并排序 ###

### 实现 ###

![复制代码][copycode.gif]

/*
       
        主题：归并排序 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.15 
       
        */
       
        #include 
       
        <
       
        iostream
       
        >
       
        #include 
       
        <
       
        vector
       
        >
       
        #include 
       
        <
       
        iterator
       
        >
       
        #include 
       
        <
       
        algorithm
       
        >
       
        #include 
       
        <
       
        cstdio
       
        >
       
        
       
        using
       
        
       
        namespace
       
        std; template 
       
        <
       
        class
       
        T
       
        >
       
        
       
        void
       
        merge(vector
       
        <
       
        T
       
        >&
       
        arr,
       
        int
       
        start ,
       
        int
       
        middle,
       
        int
       
        end) { 
       
        int
       
        n1 
       
        =
       
        middle 
       
        -
       
        start 
       
        +
       
        
       
        1
       
        ; 
       
        int
       
        n2 
       
        =
       
        end 
       
        -
       
        middle; vector
       
        <
       
        T
       
        >
       
        left(n1); vector
       
        <
       
        T
       
        >
       
        right(n2); 
       
        int
       
        i,j,k; 
       
        for
       
        (i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        n1; 
       
        ++
       
        i) left[i] 
       
        =
       
        arr[start 
       
        +
       
        i]; 
       
        for
       
        (j 
       
        =
       
        
       
        0
       
        ;j 
       
        <
       
        n2; 
       
        ++
       
        j) right[j] 
       
        =
       
        arr[middle 
       
        +
       
        j 
       
        +
       
        
       
        1
       
        ]; i 
       
        =
       
        j 
       
        =
       
        
       
        0
       
        ; k 
       
        =
       
        start; 
       
        while
       
        (i 
       
        <
       
        n1 
       
        &&
       
        j 
       
        <
       
        n2) { 
       
        if
       
        (left[i] 
       
        <
       
        right[j]) arr[k 
       
        ++
       
        ] 
       
        =
       
        left[i 
       
        ++
       
        ]; 
       
        else
       
        arr[k 
       
        ++
       
        ] 
       
        =
       
        right[j 
       
        ++
       
        ]; } 
       
        while
       
        (i 
       
        <
       
        n1) arr[k 
       
        ++
       
        ] 
       
        =
       
        left[i 
       
        ++
       
        ]; 
       
        while
       
        (j 
       
        <
       
        n2) arr[k 
       
        ++
       
        ] 
       
        =
       
        right[j 
       
        ++
       
        ]; } template 
       
        <
       
        class
       
        T
       
        >
       
        
       
        void
       
        sort(vector
       
        <
       
        T
       
        >&
       
        arr,
       
        int
       
        start,
       
        int
       
        end) { 
       
        //
       
        getchar();
       
        
       
        
       
        if
       
        (start 
       
        <
       
        end) { 
       
        int
       
        middle 
       
        =
       
        (start 
       
        +
       
        end) 
       
        /
       
        
       
        2
       
        ; sort(arr,start,middle); sort(arr,middle 
       
        +
       
        
       
        1
       
        ,end); merge(arr,start,middle,end); } } 
       
        int
       
        main() { 
       
        const
       
        
       
        int
       
        length 
       
        =
       
        
       
        20
       
        ; vector
       
        <
       
        int
       
        >
       
        arr(length); 
       
        for
       
        (size_t i 
       
        =
       
        
       
        0
       
        ;i 
       
        <
       
        arr.size(); 
       
        ++
       
        i) arr[i] 
       
        =
       
        i; random_shuffle(arr.begin(),arr.end()); copy(arr.begin(),arr.end(),ostream_iterator
       
        <
       
        int
       
        >
       
        (cout, 
       
        "
       
        
       
        "
       
        )); cout 
       
        <<
       
        endl; sort(arr,
       
        0
       
        ,length 
       
        -
       
        
       
        1
       
        ); copy(arr.begin(),arr.end(),ostream_iterator
       
        <
       
        int
       
        >
       
        (cout, 
       
        "
       
        
       
        "
       
        )); cout 
       
        <<
       
        endl; 
       
        return
       
        
       
        0
       
        ; }

[2010100711281920.png]: /images/20220609/5a4b292673cf4eb9aa306ed9851a4ccf.png
[2010100716272830.jpg]: /images/20220609/bf305bd31522439cae117b0e34c3963e.png
[2010100716280093.jpg]: /images/20220609/4dec72ffc8c84d729d1bc6589b4b0e5b.png
[copycode.gif]: /images/20220609/b4c556d19a9f46c194570f9378b37696.png
[2010100716314153.jpg]: /images/20220609/f7820cce0126456f8c0f54c843553eef.png
[2010100716322732.jpg]: /images/20220609/a2f13d31594e428bae8ebe1b1ce49fbb.png
[2010100716325049.jpg]: /images/20220609/48503ab1597e4642a31367d9387acbec.png
[2010100716334057.jpg]: /images/20220609/1b20a70fbb3d455d86335c73a4bf4084.png
[2010101321262812.jpg]: /images/20220609/0808ab59b9d645e5b09498afd4c6b753.png
[2010101321301748.jpg]: /images/20220609/e8f913a7e51a4be498e6cb018aa5c9a3.png
[2010101321304163.jpg]: /images/20220609/3892c31b901f4a28979aa45c3e716c35.png
[2010101321353681.jpg]: /images/20220609/f50dd77477014213aeacea5c783d5b77.png
[2010101321364034.jpg]: /images/20220609/f3bb6b642de8451ab4bdc450f560acc8.png
[2010101321395991.jpg]: /images/20220609/e9f0d2132c244df0bc5e62ac7aa4fa49.png