2024年5月2日发(作者：)
第7章 暴力求解法
第7章 暴力求解法
【教学内容相关章节】
7.1简单枚举 7.2枚举排列 7.3子集生成
7.4回溯法 7.5隐式图搜索
【教学目标】
（1）掌握整数、子串等简单对象的枚举方法；
（2）熟练掌握排列生成的递归方法；
（3）熟练掌握用“下一个排列”枚举全排列的方法；
（4）理解解答树，并能估算典型解答树的结点数；
（5）熟练掌握子集生成的增量法、位向量法和二进制法；
（6）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效；
（7）熟练掌握解答树的宽度优先搜索和迭代加深搜索；
（8）理解倒水问题的状态图与八皇后问题的解答树的本质区别；
（9）熟练掌握八数码问题的BFS实现；
（10）熟练掌握集合的两种典型实现——hash表和STL集合。
【教学要求】
掌握整数、子串等简单对象的枚举方法；熟练掌握排列生成的递归方法；熟练掌握用“下
一个排列”枚举全排列的方法；理解子集树和排列树；熟练掌握回溯法框架；熟练掌握解答
树的宽度优先搜索和迭代搜索；熟练掌握集合的两种典型实现——hash表和STL集合。
【教学内容提要】
本章主要讨论暴力法（也叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，
然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。介绍了排列生成的递
归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法的基
本框架；介绍了集合的两种典型实现——hash表和STL集合。
【教学重点、难点】
教学重点：
（1）熟练掌握排列生成的递归方法；
（2）理解解答树，并能估算典型解答树的结点数；
（3）熟练掌握子集生成的增量法、位向量法和二进制法；
（4）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效；
（5）熟练掌握解答树的宽度优先搜索和迭代搜索；
（6）熟练掌握集合的两种典型实现——hash表和STL集合。
教学难点：
（1）熟练掌握子集生成的增量法、位向量法和二进制法；
（2）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效；
（3）熟练掌握解答树的宽度优先搜索和迭代搜索；
（4）熟练掌握集合的两种典型实现——hash表和STL集合。
【课时安排】
7.1简单枚举 7.2枚举排列 7.3子集生成
7.4回溯法 7.5隐式图搜索
第 199 页
第7章 暴力求解法
引 言
暴力法也称为穷举法、蛮力法，它要求调设计者找出所有可能的方法，然后选择其中的
一种方法，若该方法不可行则试探下一种可能的方法。
暴力法也是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。
暴力法不是一个最好的算法，但当我们想不出更好的办法时，它也是一种有效的解决问
题的方法。
暴力法的优点是逻辑清晰，编写程序简洁。在程序设计竞赛时，时间紧张，相对于高效
的、巧妙的算法，暴力法编写的程序简单，能更快地解决问题。同时蛮力法也是很多算法的
基础，可以在蛮力法的基础上加以优化，得到更高效的算法。
而且，某些情况下，算法规模不大，使用优化的算法没有必要，而且某些优化算法本身
较复杂，在规模不在时可能因为复杂的算法浪费时间，反而不如简单的暴力搜索。
使用暴力法常用如下几种情况：
（1）搜索所有的解空间；
（2）搜索所有的路径；
（3）直接计算；
（4）模拟和仿真。
7.1 简 单 枚 举
在枚举复杂对象之前，先尝试着枚举一些相对简单的东西，如整数、子串等。暴力枚举
对问题进行一定的分析往往会让算法更加简洁、高效。
7.1.1 除法
输入正整数n，按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中a～j
恰好为数字0～9的一个排列，2≤n≤79。
样例输入：
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 t[10]={0}; //初始化数组t，使得各位数字为0，好处是使得fghij<10000
时f位置为0
int ia = 0;
while(i) { //取i中各位数字存放在数组t中
t[ia++] = i % 10;
i = i / 10;
}
while(j) { //取j中各位数字存放在数组t中
t[ia++] = j % 10;
j = j / 10;
}
//判断a～j是否恰好为数字的0～9的一个排列
第 200 页
发布者：admin，转转请注明出处：http://www.yc00.com/web/1714611523a2480275.html
评论列表（0条）