} 习题：

1.求区间第K大值。

2.子集和问题（两个元素的和）：给定一个由n个实数构成的集合S和另一个实数X，判断S中是否有两个元素的和等于X。（提示：利用二分查找）

思考题：棋盘覆盖问题

有一个2k*2k的方格棋盘，恰有一个方格是黑色的，其他为白色。任务是用包含3个方格的L型牌覆盖所有白色方格。注：黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。L型牌的4种旋转方式如下：

分析：当k=1时，选用一块牌就够了；对于2k*2k的棋盘，可以切分为4块，每块大小为2k-1*2k-1，则对有黑格的那块可以用递归来实现；问题是其他3块呢？可以在切分边界构造黑格，进而用递归解决问题。

四、回溯法

回溯法可以看作是带优化的穷举法。它的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索。搜索过程中，每到达一个结点，则判断以该结点为根的子树是否含有问题的解，如果确定其不含问题的解，则退回到上层父结点。回溯法的应用范围：只要能把待求解的问题分成不太多的步骤，每个步骤又只有不太多的选择，都可以考虑应用回溯法。

回溯法求解步骤：

（1） 针对所给问题，定义问题的解空间；

（2） 确定易于搜索的解空间结构（子集树和排列树）；

（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜

索。 常用的剪枝函数：

（1） 用约束条件在扩展结点处剪去不满足约束的子树； （2） 用限界函数剪去得不到最优解的子树。

例1：经典回溯法解决的问题——四皇后（八皇后）问题。在4×4（8×8）棋盘上放置4（8）个皇后，使她们互不攻击（皇后的攻击范围为同行同列和同对

17

角线）。

void search(int cur) {

int i,j;

if(cur==n) tot++; else for(i=0;i

例2：子集和问题。S是一个由n个正整数组成的集合｛x1,x2,?,xn｝,c是一个正整数。子集和问题是判定是否存在一个S的子集S1，使得其中的元素之和等于c。

说明：cw为当前元素和；r为剩余元素之和；w数组记录集合中各元素值；x数组描述对应位置的元素是否选中

int backtrack(int i) //i从1开始 {

if (i>n) { }

r -= w[i]; //计算剩余大小

if (cw+w[i]<=c) //判断当前和是否小于等于c { }

x[i]=1;

//选中第i个元素

cw += w[i];

if (backtrack(i+1)) return 1; cw -= w[i];

if (cw==c) return 1; else return 0; int ok=1; C[cur]=i;

for(j=0;j

if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j]) { ok=0; break;} If(ok) search(cur+1);

18

if (cw+r >= c) //判断当前和加上剩余元素和是否能满足大于等c { }

r += w[i]; return 0;

}

注意：上述代码这种递归方式只能找出一个解，不会列出所有可能的解，因为该函数带有返回值，当找到一个解后则层层返回，不会再继续遍历下去。

习题：

1. 有5个砝码，重量为1，3，9，27，81，可以组合成1-121之间的任意整数。对于用户给定的重量，给出砝码方案。

例如：输入5

输出 9-3-1 输入19 输出 27-9+1

x[i] = 0; //不选第i个元素 if ( backtrack(i+1)) return 1;

2. 马的遍历问题。在Ｎ＊Ｍ的棋盘中，马只能走日字。马从位置(x,y)处出发，把 棋盘的每一格都走一次，且只走一次。找出所有路径。

19