2022年算法竞赛入门经典授课教案第7章暴力求解法 .pdf

《2022年算法竞赛入门经典授课教案第7章暴力求解法 .pdf》由会员分享，可在线阅读，更多相关《2022年算法竞赛入门经典授课教案第7章暴力求解法 .pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 7 章暴力求解法【教学内容相关章节】7.1 简单枚举 7.2枚举排列 7.3子集生成7.4 回溯法 7.5隐式图搜索【教学目标 】（1）掌握整数、子串等简单对象的枚举方法；（2）熟练掌握排列生成的递归方法；（3）熟练掌握用“下一个排列”枚举全排列的方法；（4）理解解答树，并能估算典型解答树的结点数；（5）熟练掌握子集生成的增量法、位向量法和二进制法；（6）熟练掌握回溯法框架，并能理解为什么它往往比生成- 测试法高效；（7）熟练掌握解答树的宽度优先搜索和迭代加深搜索；（8）理解倒水问题的状态图与八皇后问题的解答树的本质区别；（9）熟练掌握八数码问题的BFS实现；（10）熟练掌握集合的两种典型

2、实现hash 表和 STL集合。【教学要求 】掌握整数、 子串等简单对象的枚举方法；熟练掌握排列生成的递归方法；熟练掌握用 “下一个排列” 枚举全排列的方法；理解子集树和排列树；熟练掌握回溯法框架；熟练掌握解答树的宽度优先搜索和迭代搜索；熟练掌握集合的两种典型实现hash 表和 STL集合。【教学内容提要】本章主要讨论暴力法（也叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。介绍了排列生成的递归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法的基本框架；介绍了集合的两种典型实现hash 表和 STL集

3、合。【教学重点、难点】教学重点：（1）熟练掌握排列生成的递归方法；（2）理解解答树，并能估算典型解答树的结点数；（3）熟练掌握子集生成的增量法、位向量法和二进制法；（4）熟练掌握回溯法框架，并能理解为什么它往往比生成- 测试法高效；（5）熟练掌握解答树的宽度优先搜索和迭代搜索；（6）熟练掌握集合的两种典型实现hash 表和 STL集合。教学难点：（1）熟练掌握子集生成的增量法、位向量法和二进制法；（2）熟练掌握回溯法框架，并能理解为什么它往往比生成- 测试法高效；（3）熟练掌握解答树的宽度优先搜索和迭代搜索；（4）熟练掌握集合的两种典型实现hash 表和 STL集合。【课时安排 】7.1 简单

4、枚举 7.2枚举排列 7.3子集生成7.4 回溯法 7.5隐式图搜索精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 23 页 - - - - - - - - - - 引言暴力法也称为穷举法、蛮力法， 它要求调设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。暴力法也是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。暴力法不是一个最好的算法，但当我们想不出更好的办法时，它也是一种有效的解决问题的方法。暴力法的优点是逻辑清晰，编写程序简洁。在

5、程序设计竞赛时，时间紧张，相对于高效的、巧妙的算法，暴力法编写的程序简单，能更快地解决问题。同时蛮力法也是很多算法的基础，可以在蛮力法的基础上加以优化，得到更高效的算法。而且， 某些情况下， 算法规模不大，使用优化的算法没有必要，而且某些优化算法本身较复杂，在规模不在时可能因为复杂的算法浪费时间，反而不如简单的暴力搜索。使用暴力法常用如下几种情况：（1）搜索所有的解空间；（2）搜索所有的路径；（3）直接计算；（4）模拟和仿真。7.1 简单枚举在枚举复杂对象之前，先尝试着枚举一些相对简单的东西，如整数、子串等。暴力枚举对问题进行一定的分析往往会让算法更加简洁、高效。7.1.1 除法输入正整数n，

6、按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中aj恰好为数字09 的一个排列， 2 n79。样例输入：62 样例输出：79546/01283=62 94736/01528=62 【分析】只需要枚举fghij就可以计算出abcde，然后判断是否所有数字都不相同即可。不仅程序简单，而枚举量也从10!=3628800 降低至不到1万。由此可见，即使采用暴力枚举，也是需要认真分析问题。完整的程序如下：#include using namespace std; bool test(int i,int j) /用数组 t 存放 i ，j 的各位数字 int t10=0; /初始化数组

7、t ，使得各位数字为0，好处是使得fghij10000时 f 位置为 0 int ia = 0; while(i) /取 i 中各位数字存放在数组t 中 tia+ = i % 10; i = i / 10; while(j) /取 j 中各位数字存放在数组t 中 tia+ = j % 10; j = j / 10; / 判断 aj 是否恰好为数字的09 的一个排列精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 23 页 - - - - - - - - - - for(int m = 0; m

8、10; +m) for(int n = m+1; n n & n =2 & n = 79) k = 1234; while(k = 98765) int j = k * n; if(j 100000) /若 fghij10000，满足题目的条件，f 位置输出0 if(test(j,k) cout j / ; if(k 10000) cout 0; cout k = n endl; +k; return 0; 7.1.2 最大乘积输入 n 个元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正整，应输出-1 （表示无解） 。1n18，-10 Si10。样例输入：3 2

9、4 -3 5 2 5 -1 2 -1 样例输出：8 20 【分析】连续子序列有两个要素：起点和终点， 因此只需要枚举起点和终点即可。由于每个元素的绝对值不超过10，一共又不超过18 个元素，最大可能的乘积示会超过1018，可以用 long long 存下。完整的程序如下：#include int main() int a20; /存放输入序列的每一个元素 _int64 ans = 0; /存放最大的乘积 int n; /输入元素的个数_int64 tmp； /存放乘积的中间结果 while(scanf(%d,&n)!=EOF) /输入序列中元素的个数n for(int i = 0;i n; i

10、+) /输入序列中的元素 scanf(%d,&ai); for(i = 0; i n; i+) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 23 页 - - - - - - - - - - / 从序列中的第0 个元素开始，枚举最大连续乘积，并用ans 存储 tmp = 1; for(int j = i; j ans) ans = tmp; if(ans0) printf(%I64dn,ans); else printf(%dn,-1); return 0; 7.1.3 分数拆分输入正整数k

11、，找到所有的正整数xy，使得111kxy。样例输入：2 12 样例输出：2 1/2=1/6+1/3 1/2=1/4+1/4 8 1/12=1/156+1/13 1/12=1/84+1/14 1/12=1/60+1/15 1/12=1/48+1/16 1/12=1/36+1/18 1/12=1/30+1/20 1/12=1/28+1/21 1/12=1/24+1/24 【分析】找出所有有x，y，枚举完成了就行了。但是从1/12=1/156+1/13可以看出， x 可以比 y大很多。由于xy，有11xy，因此111kyy，即 y2k。这样，只需要在2k 范围内枚举 y，然后根据y 尝试计算出x 即

12、可。完整的程序如下：#include int main() int k; int x, y, count = 0;/变量 count 统计等式的个数 while(scanf(%d, &k) != EOF) for(y = k+1;y = 2 * k; y+) /判断 1/k=1/x+1/y等式的个数， x=(k * y) / (y - k); if(x * (y-k) = k * y) count+; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 23 页 - - - - - - - - -

13、 - printf(%dn,count); /输出满足条件的等式的个数 for(y = k+1; y = 2 * k; y+) /输出满足条件的等式 x=(k * y) / (y - k); if(x * (y - k) = k * y) printf(1/%d=1/%d+1/%dn,k,x,y); return 0; 7.1.4 双基回文数如果一个正整数n 至少有两个不同的进位制b1 和 b2 下都是回文数 （2b1,b210） ，则称 n 是双基回文数（注意，回文数不以包含前导零）。输入正整数S106，输出比S大的最小双基回文数。样例输入： 1600000 样例输出： 1632995 【分

14、析】最自然的想法是：从 n+1 开始依次判断每个数是否为双基回文数，而在判断时要枚举所有可能的基数（210） 。意外的是：对于S106的“小规模数据”来说是足够快的双基回文数太多太密。完整的程序如下：#include using namespace std; bool huiwen(int n) int i,j,a30,s; int total = 0; /存放数 s 是回文数的基数个数 for(int base = 2; base = 10; base+) i = 1; s = n; while(s) ai = s % base; s = s / base; i+; i-; for(j =

15、1; j i/2) total+; /数 s 在基 base 下是回文数，则total+ if(total = 2) return true; return false; int main() int s; while(scanf(%d,&s) = 1) for(s = s+1; ; s+) if(huiwen(s) cout s endl; break; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 23 页 - - - - - - - - - - return 0; 7.2 枚举排列输入

16、整数 n，按字典序从大到小的顺序输出前n 个数的所有排列。两个序列的字典序大小关系等价于从头开始第一个不相同位置处的大小关系。例如，(1,3,2)(2,1,3)，字典序最小的排列是 (1,2,3,4,n) ，最大的排列是(n,n-1,n-2, ,1) 。n=3 时，所有排列的排序结果是： (1,2,3)、(1,3,2)、(2,1,3)、(2,3,1)、 (3,1,2)、(3,2,1) 7.2.1 生成 1n 的排列对此问题用递归的思想解决：先输出所有以1 开头的排列（递归调用），然后输出以2开头的排列（递归调用） ，接着以 3 开头的排列，最后才是以n 开头的排列。以 1 开头的排列的特点是：

17、第一位是1，后面是按字典序的29 的排列。所以在设计递归函数需要以下参数：（1）已经确定的“前缀”序列，以便输出；（2）需要进行全排列的元素集合，以便依次选做第一个元素。这样，写出以下的伪代码：void print_permutation(序列 A，集合 S) if(S为空 ) 输出序列A; else 按照从小到大顺序依次考虑 S的每个元素v print_permutation(在 A的末尾填加v 后得到的新序列，S-v); 上面的递归函数中递归边界是S为空的情形，可以直接输出序列A；若 S不为空，则按从小到大的顺序考虑S中的每个元素，每次递归调用以A开头。下面考虑程序的实现。用数组表示序列A

18、，集合 S可以由序列A完全确定 A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法得到数组的元素个数，所以需要传一个已经填好的位置个数，或者当前需要确定的元素位置cur 。声明一个足够大的数组A，然后调用print_permutation(n,A,0)，即可按字典序输出1n 的所有排列。完整的程序如下：#include int A100; / 输出 1n 的全排列的递归函数void print_permutation(int n, int* A, int cur) int i, j; if(cur = n) / 递归边界 for(i = 0; i n; i+) printf(%d

19、, Ai); printf(n); else for(i = 1; i = n; i+) / 尝试在 Acur 中填各种整数i int ok = 1; for(j = 0; j cur; j+) if(Aj = i) ok = 0; / 如果 i 已经在 A0 Acur-1出现过，则不能再选 if(ok) Acur = i; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 23 页 - - - - - - - - - - print_permutation(n, A, cur+1); / 递归

20、调用 int main() print_permutation(4, A, 0); return 0; 在递归函数print_permutation中循环变量i 是当前考虑的Acur 。为了检查元素i是否已经用过， 还用到了一个标志变量ok，初始值为 1（真） ，如果发现有某个Aj=i时，则改为 0（假） 。如果最终ok 仍为 1，则说明 i 没有在序列中出现过，把它添加到序列末尾（Acur=i）后递归调用。7.2.2 生成可重集的排列如果把问题改成：输入数组A，并按字典序输出数组A各元素的所有全排列，则需要对上述递归函数print_permutation修改把P加到 print_permut

21、ation的参数列表中， 然后把代码中的if(Aj=i)和 Acur=i分别改成 if(Aj=Pi)和 Acur=Pi。 只有把 P的所有元素按从小到大的顺序排序，然后调用print_permutation(n,P,A,0)即可。但是上述递归函数print_permutation中，禁止 A数组中出现重复，而在 P中可能就有重复元素时，所以输出数组A时就会出现问题。解决方法是统计A0 Acur-1中 Pi的出现次数c1， 以及 P数组中 Pi的出现次数c2。只要 c1c2，就能递归调用。枚举的下标i 应不重复、不遗漏地取遍所有Pi 值。由于P数组已经排过序，所以只需检查 P的第一个元素和所有“

22、与前一个元素不相同”的元素， 即只需在 for(i=0;in;i+)和其后的花括号之前加上if(!i|Pi!=Pi-1)即可。完整的程序如下：#include int P100, A100; / 输出数组 P中元素的全排列。数组P中可能有重复元素void print_permutation(int n, int* P, int* A, int cur) int i, j; if(cur = n) for(i = 0; i n; i+) printf(%d , Ai); printf(n); else for(i = 0; i n; i+) if(!i | Pi != Pi-1) int c1

23、= 0, c2 = 0; for(j = 0; j cur; j+) if(Aj = Pi) c1+; for(j = 0; j n; j+) if(Pi = Pj) c2+; if(c1 c2) Acur = Pi; print_permutation(n, P, A, cur+1); int main() int i, n; scanf(%d, &n); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 23 页 - - - - - - - - - - for(i = 0; i n; i+)

24、 scanf(%d, &Pi); print_permutation(n, P, A, 0); return 0; 7.2.3 解答树假设 n=4，序列为 1,2,3,4，如图 7-1 所示的树显示出了递归函数的调用过程。其中，结点内部的序列表示为A，位置 cur 用高亮表示， 另外，由于从该处开始的元素和算法无关，因此用星号表示。图 7-1 排列生成算法的解答树从图 7-1 可以看出，它是一棵二叉树。第0 层（根）结点有n 个儿子，第1 层结点各有n-1 个儿子，第2 层结点各有n-2 个儿子，第3 层结点各n-3 个儿子，第n 层结点都没有儿子（即都是叶子） ，而每个叶子对应于一个排列，共

25、有n! 个叶子。由于这棵树展示的是逐步生成完整解的过程，因此将其称为解答树。提示 7-1 ：如果某问题的解可以由多个步骤得到，而每个步骤都有若干种选择（这些候选方案集可能会依赖于先前作出的选择），且可以用递归枚举法实现，则它的工作方式可以用解答树描述。通过逐层查看，第0 层有 1 个结点，第1 层有 n 个结点，第2 层有 n*(n-1)个结点，第3 层有 n*(n-1)*(n-2)个结点，第n 层有 n*(n-1)*(n-2)*2*1=n! 个。为了推导方便，把n*(n-1)*(n-2)*(n-k)写成 n!/(n-k-1)!，则所有结点之和为：111000!11( )!(1)!(1)!nn

26、nkkknT nnnnknkk根据高等数学中的泰勒展开公式，101lim!nxkek，因此 T(n)n! e=O(n!) 。由于叶子有 n! 个，倒数第二层也有n! 个结点，因此上面的各层全部来源于最后一两层，所以上面的结点数可以忽略不计。7.2.4 下一个排列枚举所有排列的另一个方法是从字典序最小排列开始，不停调用 “求下一个排列”的过程，在 C+ 的 STL中提供了一个库函数next_permutation。完整的程序如下：#include #include using namespace std; int main() int n, p10; scanf(%d, &n); for(int

27、 i = 0; i n; i+) scanf(%d, &pi); sort(p, p+n); / 排序，得到 p 的最小排列 do for(int i = 0; i n; i+) printf(%d , pi); / 输出排列p printf(n); while(next_permutation(p, p+n); / 求下一个排列 return 0; 说明： （1）STL里面有个 sort函数，可以直接对数组进行随机化快速排序，复杂度为n*log2n，效率高。使用这个函数，需要包含头文件：#include using namespace std; 它的函数原型如下：精品资料 - - - 欢迎下

28、载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 23 页 - - - - - - - - - - template void sort(RandomAccessIterator first, RandomAccessIterator last); 这个 sort函数可以传两个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是a,b) 。简单来说， 有一个数组int a100 ，要对从 a0 到 a99 的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序

29、。如果需要对数组t 的第 0 到 len-1的元素排序，就写sort(t,t+len);，对向量v( 定义vector v;)进行排序，写成sort(v.begin(),v.end(); ，排序的数据类型不局限于整数，只要是定义了小于运算的类型都可以，比如字符串类string。template void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp); 这个 sort函数可以传三个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是

30、a,b) 。简单来说， 有一个数组int a100 ，要对从 a0 到 a99 的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。如果是没有定义小于运算的数据类型，或者想改变排序的顺序，就要用到第三参数比较函数。比较函数是一个自己定义的函数，返回值是bool 型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数cmp bool cmp(int a,int b) return ab; 排序的时候就写sort(a,a+100,cmp);。（2）在 C+的 STL中定义的next_permutation和 prev_permutati

31、on函数则是非常灵活且高效的方法，它被广泛的应用于为指定序列生成不同的排列。next_permutation和prev_permutation函数需要包含algorithm.h头文件。需要注意的是“如果要走遍所有的排列，必须先将元素排序”。（3）按照 STL文档的描述， next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止。 prev_permutation函数与之相反，是生成给定序列的上一个较小的排列（前一个排列）。二者原理相同，仅遍历顺序相反。这两个函数据可以对整型数组或字符数组操作。（4）next_permutation函数原型temp

32、late bool next_permutation(BidIt first, BidIt last); template bool next_permutation(BidIt first, BidIt last, Compare comp); next_permutation函数取由 first,last)标记的排列， 并将其重新排序为下一个排列。如果不存在下一个排列，则返回false ；否则，返回true 。第一个版本（）使用底层类型的小于操作符来确定下一个排列，第二个版本（）根据comp对元素进行排序。如果原始字 符 串 是 排 过 序 的 ， 则 连 续 调 用next_permut

33、ation函 数 会 生 成 整 个 排 列 集 合 。prev_permutation函数原型与next_permutation函数型类似。7.3 子集生成本节介绍子集生成算法：给定一个集合， 枚举它所有可能的子集。为了简单起见， 本节讨论的集合中没有重复元素。7.3.1 增量构造法第一种思路是一次选出一个元素放到集合中，完整程序如下：#include void print_subset(int n, int* A, int cur) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 23 页

34、 - - - - - - - - - - int i; for(i = 0; i cur; i+) printf(%d , Ai); / 打印当前集合 printf(n); int s = cur ? Acur-1+1 : 0; / 确定当前元素的最小可能值 for(i = s; i n; i+) Acur = i; print_subset(n, A, cur+1); / 递归构造子集 int A10; int main() print_subset(5, A, 0); return 0; 注意： 由于 A中的元素个数不确定，每次递归调用都要输出当前集合。另外，递归边界也不需要显式确定如果无

35、法继续添加元素，自然不会再递归了。上面的代码用到了定序的技巧：规定集合 A中所有元素的编号从小到大排列，就不会把集合 1,2 按照 1,2 和2,1 输出两次了。这棵解答树上有1024 个结点，由于每个可能的A都对应一个结点，而n 元素集合恰好有 2n个子集， 210=1024。7.3.2 位向量法第二种思路是构造一个位向量Bi，而不是直接构造子集A本身，其中 Bi=1当且仅当 i 在子集 A中。完整程序如下：#include void print_subset(int n, int* B, int cur) if(cur = n) for(int i = 0; i cur; i+) if(B

36、i) printf(%d , i); / 打印当前集合 printf(n); return; Bcur = 1; / 选第 cur 个元素 print_subset(n, B, cur+1); Bcur = 0; / 不选第 cur 个元素 print_subset(n, B, cur+1); int B10; int main() print_subset(5, B, 0); return 0; 必须当“所有元素是否选择”全部确定完毕后才是一个完整的子集，因此当 if(cur=n)成立时才输出。所有部分解（不完整的解）也对应着解答树上的结点。这是一棵 n+1 层的二叉树（ cur 从 0n）

37、 ，第 0 层有 1 个结点，第1 层有 2 个结点，第2 层有 4 个结点，第3 层有 8 个结点，第i 层有 2i个结点，总数为1+2+4+2n=2n+1-1 。图 7-2 就是这棵解答树。最后几层结点数占整棵树的绝大多数。图 7-2 位向量法的解答树精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 23 页 - - - - - - - - - - 7.3.3 二进制法用二进制来表示0,1,2,n-1的子集 S：从右往左第i 位（各位从0 开始编号）表示元素 i 是否在集合S中。 用图 7

38、-3 展示了二进制010001100011011 是如何表示集合0,1,2,4, 5,9,10,14的。图 7-3 用二进制表示子集注意： 为了处理方便，最右边那个位总是对应元素0，而不是元素1。提示 7-2 ：可以用二进制表示子集，其中从右往左第i 位（从 0 开始编号）表示元素i是否在集合中（1 表示“在”，0 表示“不在” ） 。不仅要表示集合，还在对集合进行操作。对集合的运算都可以用位运算符简单实现。最常见的二元运算是与（&） 、或（ | ） 、非 (!) 、异或（） 。“异或（ XOR ） ”运算符，它的规则是“如果A和 B不相同，则AB为 1，否则为 0” 。异或运算最重要的性质就

39、是“开关性”异或两次以后相当于没有异或，即ABB=A 。由于 A&B 、 A|B、 AB分别对应着集合的交、 并和对称差。 另外，空集为 0， 全集 0,1,2, n-1 的二进制为n 个 1，即十进制的2n-1。在程序中把全集定义为ALL_BITS=(1n)-1 ，则A的补集为 ALL_BITSA。也可以直接用整数减法ALL_BITS-A 表示，但速度比位运算慢。提示 7-3 ：当用二进制表示子集时，位运算中的按位与、或、异或对应集合的交、并和对称差。输出子集 S对应的各个元素的完整程序如下：#include void print_subset(int n, int s) / 打印 0, 1

40、, 2, ., n-1的子集 S for(int i = 0; i n; i+) if(s&(1i) printf(%d , i); / 这里利用了C语言“非0 值都为真”的规定 printf(n); int main() int n = 5; for(int i = 0; i (1n); i+) / 枚举各子集所对应的编码 0, 1, 2, ., 2n-1 print_subset(n, i); return 0; 7.4 回溯法无论是排列生成还是子集枚举，两种思路： 递归构造和直接遍历。直接遍历的优点是思路和程序都很简单，缺点在于无法简便地减少枚举量必须生成（generate ）所有可能的

41、解，然后一一检查（test ） 。另一方面， 在递归构造中， 生成和检查过程可以有机结合起来，从而减少不必要的枚举，这就是本节的主题回溯法（backtracking） 。回溯法是一种系统的搜索问题的解的方法。它的基本思想是： 从一条路前行， 能进则进，不能进则退回来，换一条路再试。回溯法是一种通用的解题方法。应用回溯法的时候，首先明确定义问题的解空间。解空间至少应该包含问题的一个解。确定了解空间后，回溯法从开始结点出发，以深度优先的方法搜索整个解空间。对于回溯法一般可以采用递归方式来实现。7.4.1 八皇后问题在棋盘上放置8 个皇后， 使得它们互不攻击，此时每个皇后的攻击范围为同行同列和对角线

42、，要求找出所有解，如图7-4 所示。Q Q 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 23 页 - - - - - - - - - - Q Q Q Q Q Q Q (a) 皇后的攻击范围 (b)一个可行解图 7-4 八皇后问题【分析】思路一：把问题转化为“从64 个格子中选一个子集” ，使得“子集中恰好有8 个格子，且任意两个选出的格子都不在同一行、同一列或同一个对角线上”。这是子集枚举问题，不是一个好的模型。思路二： 把问题转化为 “从 64 个格子中选8 个格子”，这是组合生成问题

43、。比思路一好，但是仍然不是很好。思路三：由分析可得，恰好每行每列各放置一个皇后。如果用Cx 表示第 x 行皇后的列编号，则问题变成了全排列生成问题。提示 7-4 ：在编写递归枚举程序之前，需要深入分析问题，对模型精雕细琢。一般还应对解答树的结点数有一个粗略的估计，作为评价模型的重要依据，如图 7-5 的所示。图 7-5 在四皇后问题的解答树图 7-5 中给出了四皇后问题的完整解答树。它只有18 个结点，比4!=24 小。原因是有些结点无法继续扩展。在各种情况下， 递归函数将不再递归调用本身，而是返回上一层调用，称这种现象为回溯（ backtracking） 。提示 7-5 ：当把问题分成若干步

44、骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。正是因为这个原因，递归枚举算法常称为回溯法，它的应用十分普遍。在主程序中读入n，并为 tot清 0，然后调用search(0)，即可得到解的个数tot 。当n=8，则 tot=92,状态空间结点数nc=2057。完整的程序如下：#include int C50, tot = 0, n, nc = 0; void search(int cur) int i, j; nc+; /nc状态空间结点数 if(cur = n) tot+; /递归边界。只要走到了这里，所有皇后必然不冲突 else for(i = 0;

45、 i n; i+) int ok = 1; Ccur = i; /尝试把 cur 行的皇后放在第i 列 for(j = 0; j cur; j+) /检查是否和前面的皇后冲突 if(Ccur = Cj | cur-Ccur = j-Cj | cur+Ccur = j+Cj) ok = 0; break; if(ok) search(cur+1); /如果合法，则继续递归 int main() scanf(%d,&n); search(0); printf(%dn, tot); printf(%dn, nc); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载

46、 名师归纳 - - - - - - - - - -第 12 页，共 23 页 - - - - - - - - - - return 0; 注意： 既然是逐行放置的，则皇后肯定不会横向攻击，因此只需检查是否纵向和斜向攻击即可。条件cur-Ccur = j-Cj | cur+Ccur = j+Cj用来判断皇后 (cur,Ccur)和(j,Cj)是否在同一条对角线上。其原理可以用图7-26 说明。0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 1 2 3 4 5 6 7 8 -2 -1 0 1 2 3 4 5 2 3 4 5 6 7 8 9 -3 -

47、2 -1 0 1 2 3 4 3 4 5 6 7 8 9 10 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 -5 -4 -3 -2 -1 0 1 2 5 6 7 8 9 10 11 12 -6 -5 -4 -3 -2 -1 0 1 6 7 8 9 10 11 12 13 -7 -6 -5 -4 -3 -2 -1 0 7 8 9 10 11 12 13 14 (a) 格子 (x,y)的 y-x 值标识了主对角线 (b)格子 (x,y)的 x+y 值标识了副对角线图 7-6 棋盘中的对角线标识上面的程序还可改进：利用二维数组vist2直接判断当前尝试的皇后所在的列和

48、两个对角线是否已有其他皇后。注意到主对角线标识y-x 可能为负，存取时要加上n。完整的程序如下：Include int C50, vis350, tot = 0, n, nc = 0; void search(int cur) int i, j; nc+; if(cur = n) tot+; else for(i = 0; i n; i+) if(!vis0i & !vis1cur+i & !vis2cur-i+n) / 利用二维数组直接判断 Ccur = i; /如果不打印解，整个C数组都可以省略 vis0i = vis1cur+i = vis2cur-i+n = 1; /修改全局变量 se

49、arch(cur+1); vis0i = vis1cur+i = vis2cur-i+n = 0; /切记！一定要改回来 int main() scanf(%d,&n); memset(vis, 0, sizeof(vis); search(0); printf(%dn, tot); printf(%dn, nc); return 0; 上面的程序关键的地方是vis 数组的使用。 vis 数组表示已经放置的皇后占据了哪些列、主对角线和副对角线。将来放置的皇后不应该修改这些值。一般地， 如果要回溯法中修改了辅助的全局变量，则一定要及进把它们恢复原状（除非故意保留修改）。另外，千万不要忘记在调试之

50、前把vis 数组清空。提示 7-6 ：如果在回溯法中使用了辅助的全局变量，则一定要及时把它们恢复原状。例如，若函数有多个出口，则需在每个出口处恢复被修改的值。7.4.2 素数环精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 23 页 - - - - - - - - - - 输入正整数n，把整数1,2,3,n 组成一个环，使得相邻两个整数之和均为素数。输出时从整数1 开始逆时针排列。同一个环应恰好输出一次。n16。样例输入：6 样例输出：1 4 3 2 5 6 1 6 5 2 3 4 【分析】