递归与分治策略（3）

棋盘覆盖

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

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

分析

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

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

算法复杂度

实现

/* 主题：棋盘覆盖* 作者：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;}

线性时间选择

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

思想

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

template

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个中位数中较大的一个。以这个元素作为划分基准。

分析

伪代码

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);

}

算法复杂度分析

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

实现

/* 主题：线性时间查找问题* 作者：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;}

循环赛日程表

题目表述：

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

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

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

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

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

实现

/* 主题：循环赛日程表* 作者：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;}

Gray码问题

实现

/* 主题：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;}

归并排序

实现

/* 主题：归并排序* 作者：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;}

参考资料 《算法分析与设计（第二版）》王晓东编著

授课教师 张阳教授

原文链接: https://www.cnblogs.com/chinazhangjie/archive/2010/10/13/1850583.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍