首页 > 专题系列 > 算法分析 > 递归与分治策略(3)
2013
12-26

递归与分治策略(3)

棋盘覆盖

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

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

 

分析

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

算法复杂度

实现

 

/* 主题:棋盘覆盖
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言: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个元素和一个整数k1 ≤ k ≤ n,要求找出这n个元素中第k小的元素。

思想

// 在数组apr区间内找到第k小的元素

template<class Type>

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

{

if (p == r)

return a[p]; // 如果pr相等,第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=εn0<ε<1。这是使T(n)=O(n)的关键之处。当然,除了575之外,还有其他选择。

实现

/* 主题:线性时间查找问题
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言: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
* 邮箱:[email protected]
* 开发语言: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码问题
实现

<

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

>/* 主题:gray码
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言: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
* 邮箱:[email protected]
* 开发语言: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;
}

 

 

参考资料 《算法分析与设计(第二版)》王晓东编著
授课教师 张阳教授

转自:http://www.cnblogs.com/chinazhangjie/archive/2010/10/13/1850583.html


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。