2.算法设计与分析__递归与分治策略

与递归分治策略

任何一个可以用计算机求解的问题所需的计算时间都与其规模n有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 如果原问题可分割成k个子问题（1＜k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

1.递归算法

程序直接或间接调用自身的编程技巧称为递归算法（Recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归需要有边界条件、递归前进段和递归返回段。 当边界条件不满足时，递归前进； 当边界条件满足时，递归返回。 注意：在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁）。 递归的缺点： 递归算法解题的运行效率较低。 在递归调用过程中，系统为每一层的返回点、局部变量等开辟了堆栈来存储。递归次数过多容易造成堆栈溢出等。

1.1 Fibonacci数列

算法3.1 Fibonacci数列的递归算法 int fib(int n) { if (n<=1) return 1; return fib(n-1)+fib(n-2); } 该算法的效率非常低，因为重复递归的次数太多。

算法3.2 Fibonacci数列的递推算法 int fib[50]; //采用数组保存中间结果 void fibonacci(int n) { fib[0] = 1; fib[1] = 1; for (int i=2; i<=n; i++) fib[i] = fib[i-1]+fib[i-2]; }

1.2 集合的全排列问题

//产生从元素k～m的全排列，作为前k—1个元素的后缀 void Perm(int list[], int k, int m) { //构成了一次全排列，输出结果 if(k==m) { for(int i=0;i<=m;i++) cout<<list[i]<<" "; cout<<endl; } else //在数组list中，产生从元素k～m的全排列 for(int j=k;j<=m;j++) { swap(list[k],list[j]); Perm(list,k+1,m); swap(list[k],list[j]); } }

1.3 整数划分问题 整数划分问题是算法中的一个经典命题之一。把一个正整数n表示成一系列正整数之和：

正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记作 。 正整数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

2 分治策略

分治策略是对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同。 递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

2.1 分治法的基本步骤 分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。

根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。 在用分治法设计算法时，最好使子问题的规模大致相同。如分成大小相等的k个子问题，许多问题可以取k＝2。 这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。 2.3 二分搜索技术 给定n个元素a[0：n－1]，需要在这n个元素中找出一个特定元素x。 首先对n个元素进行排序，可以使用C++标准模板库函数sort()。 比较容易想到的是用顺序搜索方法，逐个比较a[0：n－1]中的元素，直至找到元素x或搜索遍整个数组后确定x不在其中。 因此在最坏的情况下，顺序搜索方法需要 O(n)次比较。 二分搜索技术充分利用了n个元素已排好序的条件，采用分治策略的思想，在最坏情况下用O(log n) 时间完成搜索任务。

二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。 如果x＝a[n/2]，则找到x，算法终止。 如果x＜a[n/2]，则我们只要在数组a的左半部分继续搜索x。 如果x＞a[n/2]，则我们只要在数组a的右半部分继续搜索x。

2.4循环赛日程表 问题描述：设有n＝2k个运动员要进行网球循环赛。 现要设计一个满足以下要求的比赛日程表： 每个选手必须与其他n－1个选手各赛一次； 每个选手一天只能参赛一次； 循环赛在n－1天内结束。 请按此要求将比赛日程表设计成有n行和n－1列的一个表。 在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n，1≤j≤n－1。

void Table(int k)
{	
	int i, r;
	int n = 1 << k;	
	//构造正方形表格的第一行数据
	for (i=0; i<n; i++)
		a[0][i] = i + 1;
	//采用分治算法，构造整个循环赛日程表
	for (r=1; r<n; r<<=1)
		for (i=0; i<n; i+=2*r)
		{ 
			Copy(r, r + i, 0, i, r);		//①
			Copy(r, i, 0, r + i, r);		//②
		}
}

实现方阵的拷贝
//源方阵的左上角顶点坐标（fromx, fromy），行列数为r
//目标方阵的左上角顶点坐标（tox, toy），行列数为r
void Copy(int tox, int toy, int fromx, int fromy, int r)
{
	for (int i=0; i<r; i++)
		for (int j=0; j<r; j++)  
			a[tox+i][toy+j] = a[fromx+i][fromy+j];
}

2.5 棋盘覆盖问题 在一个 2k×2k个方格组成的棋盘中，若恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘（Defective Chessboard）。 特殊方格在棋盘中出现的位置有 4k种情形，就有4k种不同的棋盘。 图中的特殊棋盘是当 k＝2时16个特殊棋盘中一个。在棋盘覆盖问题中，要求用图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。在任何一个个 2k×2k的棋盘覆盖中，用到的L型骨牌个数为 （4k-1)/3。

用分治策略，可以设计解棋盘覆盖问题的一个简捷算法。分治的技巧在于如何划分棋盘，使划分后的子棋盘大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。 当k>0时，将2k×2k的棋盘划分为4个2k-1×2k-1子棋盘。 原棋盘只有一个特殊方格，则其余3个子棋盘中没有特殊方格。 用一个L型骨牌覆盖这3个较小棋盘的会合处。从而将原问题转化为4个较小规模的棋盘覆盖问题，以便采用递归方法求解。 递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。

采用分治算法解决棋盘覆盖问题的数据结构 令size=2k ，表示棋盘的规格。 棋盘：使用二维数组表示： int board[1025][1025]; 为了方便递归调用，将数组board设为全局变量。board[0][0]是棋盘的左上角方格。 子棋盘：由棋盘左上角的坐标tr，tc和棋盘大小s表示。 特殊方格：在二维数组中的坐标位置是（dr，dc）。 L型骨牌：用到的L型骨牌个数为（4k-1)/3 ，将所有L型骨牌从1开始连续编号，用一个全局变量表示： static int tile=1;

棋盘覆盖问题的分治算法

2.6 选择问题 对于给定的n个元素的数组a[0：n—1]，要求从中找出第k小的元素。 输入 输入有多组测试例。 对每一个测试例有2行，第一行是整数n和k（1≤k＜n≤1000），第二行是n个整数。 输出 第k小的元素。

一种简单的解决方法就是对全部数据进行排序，于是得到问题的解。 但即使用较好的排序方法，算法的复杂性也为nlogn 。 快速排序算法是分治策略的典型应用，不过不是对问题进行等份分解（二分法），而是通过分界数据（支点）将问题分解成独立的子问题。 首先选第一个数作为分界数据，将比它小的数据存储在它的左边，比它大的数据存储在它的右边，它存储在左、右两个子集之间。这样左、右子集就是原问题分解后的独立子问题。 再用同样的方法，继续解决这些子问题，直到每个子集只有一个数据，就完成了全部数据的排序工作。利用快速排序算法的思想，来解决选择问题。 记一趟快速排序后，分解出左子集中元素个数为 nleft,则选择问题可能是以下几种情况之一： nleft ＝k﹣1，则分界数据就是选择问题的答案。 nleft ＞k﹣1，则选择问题的答案继续在左子集中找，问题规模变小了。 nleft ＜k﹣1，则选择问题的答案继续在右子集中找，问题变为选择第k-nleft-1 小的数，问题的规模变小了。

算法3.9 采用分治策略找出第k小元素的算法

2.7输油管道问题 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经（或南或北）与主管道相连。 如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？ 给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。 输入 第1行是一个整数n，表示油井的数量（1≤n≤10 000）。 接下来n行是油井的位置，每行两个整数x和y （﹣10 000≤x，y≤10 000）。 输出 各油井到主管道之间的输油管道最小长度总和。

2.8 半数集问题 给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。 (1) n set(n)； (2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。 例如，set(6)={6，16，26，126，36，136}。 半数集set(6)中有6个元素。 注意半数集是多重集。 对于给定的自然数n，编程计算半数集set(n)中的元素个数。

2.9 整数因子分解 大于1的正整数n可以分解为：

当n=12时，共有8种不同的分解式： 对于给定的正整数n，编程计算n共有多少种不同的分解式。 输入 数据有多行，给出正整数n （1≤n≤2000000000）。 输出 每个数据输出1行，是正整数n的不同的分解式数量。

2.10取余运算 输入三个正整数a，p，k ，求ap%k 的值。 输入 输入有多组测试例。 对每组测试例，有三个正整数a，p，k （0＜a，p，k2 ＜232）。 输出 对每组测试例输出1行，是ap%k 的值。

.

3.3 Big String

设A＝“__”（4个字符），B＝“T.T”（3个字符），然后以AB为基础，构造无限长的字符串。 重复规则如下： 把A接在B的后面构成新的字符串C。 例如，A＝“__”，B＝“T.T”，则C＝BA＝“T.T__”。 令A＝B，B＝C，如上例所示，则A＝“T.T”，B＝“T.T__”。 编程任务：给出此无限长字符串中的第n个字符。

输入 输入有多组测试例。 每个测试例只有一个整数N（1≤N≤263－1）。 输出 对每个测试例输出一行，是此无限长字符串中的第N个字符（序号从1开始）。

（2）算法优化 由于n最大可达263—1，对于输入的每个n，都去计算小于n的最大斐波纳契数，显然是非常浪费时间的。 解决的办法是预先把在263—1范围内的所有斐波纳契数求出来，放到一个数组中。 经过测算，该斐波纳契数列最多为86项，第86项的斐波纳契数约是6.02×1018，而263—1约是9.22×1018。