递归与分治

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

　　将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。递归的概念　　直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。　　由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 示例： 例1  阶乘函数

阶乘函数可递归地定义为：

n! = 1  　　　　n = 0  (边界条件)n! = n(n-1)!  　n > 0  (递归方程)

边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

实现：

 

/* 主题：阶乘使用递归和非递归实现
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：C++
* 开发环境：Code::Blocks 10.05
* 时间: 2010.10.05
*/

#include <iostream>
using namespace std;

// factorial implement by recursive
long factorial_recursive(long n)
{
if (n == 0)
return 1;
return n * factorial_recursive(n-1);
}

// factorial implement by loop
long factorial_loop(long n)
{
long result = 1;
for (int i = n; i > 0; -- i)
result *= i;
return result;
}

int main()
{
for (int i = 0; i < 10; i ++ ) {
cout << i << "!" << " = "
<< factorial_recursive(i)
<< ","
<< factorial_loop(i)
<< endl;
}
return 0;
}

 

 

例2  Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：F(n) = 1        　　　　　　　　n = 0 (边界条件)F(n) = 1 　　　　　　　　　　 n = 1 (递归方程)F(n) = F(n - 1) + F(n - 2)      n > 2 (递归方程)

实现：

/* 主题：fibonacci数列使用递归和非递归实现
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：C++
* 开发环境：Code::Blocks 10.05
* 时间: 2010.10.05
*/

#include <iostream>
using namespace std;

// fibonacci implement by recursive
long fibonacci_recursive(long n)
{
if (n <= 1 )
return 1;

return fibonacci_recursive(n - 1)
+ fibonacci_recursive(n - 2);
}

// fibonacci implement by loop
long fibonacci_loop(long n)
{
if (n == 0 || n == 1)
return 1;

long f1 = 1;
long f2 = 1;
long result = 0;
for (long i = 1; i < n ; ++ i) {
result = f1 + f2;
f1 = f2;
f2 = result;
}
return result;
}

int main()
{
cout << "fibonacci implement by recursive: " << endl;
for (long i = 0; i <= 20; ++ i)
cout << fibonacci_recursive(i) << " " ;
cout << endl << endl;

cout << "fibonacci implement by loop: " << endl;
for (long i = 0; i <= 20; ++ i)
cout << fibonacci_loop(i) << " " ;
cout << endl;
return 0;
}

例3  Ackerman函数

当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。

Ackerman函数A(n，m)定义如下：

A(1,0) = 2

A(0,m) = 1 　　　　　　　　　　m >= 0

A(n,0) = n + 2 　　　　　　　　n >= 2

A(n,m) = A(A(n-1,m),m-1)  　 n,m >= 1

 

前2例中的函数都可以找到相应的非递归方式定义：

n! = 1 * 2 * 3 * ... * (n - 1) * n

本例中的Ackerman

函数却无法找到非递归的定义。

 

A(n，m)的自变量m的每一个值都定义了一个单变量函数：

M = 0时，A(n,0)=n+2

M = 1时，A(n,1)=A(A(n-1,1),0) = A(n-1,1)+2，和 A(1,1)=2故A(n,1)=2*n

M = 2时，A(n,2) = A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。

M = 3时，类似的可以推出

M = 4时，A(n,4)

的增长速度非常快，以至于没有适当的数

学式子来表示这一函数。

实现：

 

/* 主题：ackerman函数使用递归实现
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：C++
* 开发环境：Code::Blocks 10.05
* 时间: 2010.10.05
*/

#include <iostream>
using namespace std;

// ackerman implement
long ackerman(long n,long m)
{
if (n == 1 && m == 0)
return (long)2;
if (n == 0)
return 1;
if (m == 0)
return n + 2;

return ackerman( ackerman(n-1,m) , m-1);
}

int main()
{
cout << "m = 0 : " << endl;
cout << "ackerman(1,0) = " << ackerman(1,0) << endl;
cout << "ackerman(2,0) = " << ackerman(2,0) << endl;
cout << "ackerman(3,0) = " << ackerman(3,0) << endl;
cout << "ackerman(4,0) = " << ackerman(4,0) << endl;

cout << "m = 1 : " << endl;
cout << "ackerman(1,1) = " << ackerman(1,1) << endl;
cout << "ackerman(2,1) = " << ackerman(2,1) << endl;
cout << "ackerman(3,1) = " << ackerman(3,1) << endl;
cout << "ackerman(4,1) = " << ackerman(4,1) << endl;

cout << "m = 2 : " << endl;
cout << "ackerman(1,2) = " << ackerman(1,2) << endl;
cout << "ackerman(2,2) = " << ackerman(2,2) << endl;
cout << "ackerman(3,2) = " << ackerman(3,2) << endl;
cout << "ackerman(4,2) = " << ackerman(4,2) << endl;

cout << "m = 3 : " << endl;
cout << "ackerman(1,3) = " << ackerman(1,3) << endl;
cout << "ackerman(2,3) = " << ackerman(2,3) << endl;
cout << "ackerman(3,3) = " << ackerman(3,3) << endl;
cout << "ackerman(4,3) = " << ackerman(4,3) << endl;

return 0;
}

 

 

例4  排列问题

设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。

设R={r1,r2,…,rn}是要进行排列的n个元素，

Ri=R-{ri}

。

集合X中元素的全排列记为perm(X)。

(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 

当n=1时，perm(R)=(r)，其中r是集合R

中唯一的元素；

 

当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

/* 主题：全排列使用递归和非递归实现
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：C++
* 开发环境：Code::Blocks 10.05
* 时间: 2010.10.07
*/
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;


/* 使用递归实现
* 递归产生所有前缀是list[0:k-1]，
* 且后缀是list[k,m]的全排列的所有排列
* 调用算法perm(list,0,n-1)则产生list[0:n-1]的全排列
*/
template <class T>
void perm_recursion(T list[],int k,int m)
{
// 产生list[k:m]的所有排列
if (k == m) {
for (int i = 0; i <= m; i ++)
cout << list[i] << " ";
cout << endl;
}
else {
// 还有多个元素，递归产生排列
for (int i = k; i <= m; ++ i) {
swap(list[k],list[i]);
perm_recursion(list,k+1,m);
swap(list[k],list[i]);
}
}
}

// 非递归实现（可参照STL next_permutation源码）
template <class T>
void perm_loop(T list[],int len)
{
int i,j;
vector<int> v_temp(len);

// 初始排列
for(i = 0; i < len ; i ++)
v_temp[i] = i;

while (true) {
for (i = 0; i < len; i ++ )
cout << list[v_temp[i]] << " ";
cout << endl;

// 从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。
for(i = len - 1;i > 0 && v_temp[i] < v_temp[i-1] ; i--);
if (i == 0)
break;
// 从后查到i，查找大于 v_temp[i-1]的最小的数，记入j
for(j = len - 1 ; j > i && v_temp[j] < v_temp[i-1] ; j--);
// 交换 v_temp[i-1] 和 v_temp[j]
swap(v_temp[i-1],v_temp[j]);

// 倒置v_temp[i]到v_temp[n-1]
for(i = i,j = len - 1 ; i < j;i ++,j --) {
swap(v_temp[i],v_temp[j]);
}
}
}


int main()
{
int list[] = {0,1,2};
cout << "permutation implement by recursion: " << endl;
perm_recursion(list,0,2);
cout << endl;

cout << "permutation implement by loop: " << endl;
perm_loop(list,3);
cout << endl;
return 0;
}

例5  整数划分问题 

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记作p(n)。

例如正整数6有如下11种不同的划分，所以p(6) = 11：

    6；

    5+1；

    4+2，4+1+1；

    3+3，3+2+1，3+1+1+1；

    2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。

前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。

在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

(1) q(n,1)=1,n >= 1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，

即n = 1 + 1 + 1 + … +1.

(2) q(n,m) = q(n,n),m >= n; 最大加数n1实际上不能大于n。因此，q(1,m)=1。(3) q(n,n)=1 + q(n,n-1); 正整数n的划分由n1=n的划分和n1 ≤ n-1的划分组成。

(4) q(n,m)=q(n,m-1)+q(n-m,m),n > m >1;正整数n的最大加数n1不大于m的划分由 n1 = m的划分和n1 ≤ m-1  的划分组成。

前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。

在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

q(n,m) = 1                  n = 1, m = 1

q(n,m) = q(n,n)                n = 1, m = 1

q(n,m) = 1 + q(n,n-1)         n = m

q(n,m) = q(n,m-1) + q(n-m,m)  n > m > 1

正整数n的划分数p(n) = q(n,n)。

实现：

 

/* 主题：整数划分使用递归实现
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：C++
* 开发环境：Code::Blocks 10.05
* 时间: 2010.10.07
*/
#include <iostream>
using namespace std;

//
int __int_partition(int n,int m)
{
if (n < 1 || m < 1)
return 0;
if (n == 1 || m == 1)
return 1;
if (n < m)
return __int_partition(n,n);
if (n == m)
return __int_partition(n,m - 1) + 1;
return __int_partition(n,m - 1) + __int_partition(n - m,m);
}
int integer_partition(int n)
{
return __int_partition(n,n);
}

int main()
{
for (int i = 1; i < 7; ++ i) {
cout << "integer_patition("
<< i
<< ") = "
<< integer_partition(i)
<< endl;
}
return 0;
}

 

例6       Hanoi塔问题

设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则1：每次只能移动1个圆盘；

规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

实现：

 

/* 主题：hanoi使用递归实现
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：C++
* 开发环境：Code::Blocks 10.05
* 时间: 2010.10.07
*/

#include <iostream>
using namespace std;


void __move(char t1,char t2)
{
cout << t1 << " -> " << t2 << endl;
}
// 把n个圆盘，从t1塔移至t2塔通过t3塔
void hanoi(int n,char t1,char t2,char t3)
{
if (n > 0) {
hanoi(n-1,t1,t3,t2);
__move(t1,t2);
hanoi(n-1,t3,t2,t1);
}
}

int main()
{
cout << "hanoi(1,'a','b','c'): " << endl;
hanoi(1,'a','b','c');
cout << endl;

cout << "hanoi(1,'a','b','c'): " << endl;
hanoi(2,'a','b','c');
cout << endl;

cout << "hanoi(3,'a','b','c'): " << endl;
hanoi(3,'a','b','c');
cout << endl;

return 0;
}

递归小结

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

解决方法：在递归算法中消除递归调用，使其转化为非递归算法。

1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

2、用递推来实现递归函数。

3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

分治法的适用条件

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

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的问题所需的计算时间，则有：

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

二分搜索技术

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

分析：

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

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

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

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

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

二分搜索实现：

 

/* 主题：二分搜索
* 作者：chinazhangjie
* 邮箱：[e-mail]
* 开发语言：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;
}

 

算法复杂度分析：

每执行一次算法的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]定义为

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

分治法:

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

由此可得：

算法复杂度分析

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

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

T(n) = O(n^3)

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

算法复杂度分析

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)

是否能找到O(n^2)的算法？

 

棋盘覆盖在一个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
* 邮箱：[e-mail]
* 开发语言：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
* 邮箱：[e-mail]
* 开发语言：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
* 邮箱：[e-mail]
* 开发语言：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
* 邮箱：[e-mail]
* 开发语言：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
* 邮箱：[e-mail]
* 开发语言：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;
}