文档介绍：第7章暴力求解法
【教学内容相关章节】
【教学目标】
(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集合。
【课时安排】
引言
暴力法也称为穷举法、蛮力法,它要求调设计者找出所有可能的方法,然后选择其中的一种方法,若该方法不可行则试探下一种可能的方法。
暴力法也是一种直接解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。
暴力法不是一个最好的算法,但当我们想不出更好的办法时,它也是一种有效的解决问题的方法。
暴力法的优点是逻辑清晰,编写程序简洁。在程序设计竞赛时,时间紧张,相对于高效的、巧妙的算法,暴力法编写的程序简单,能更快地解决问题。同时蛮力法也是很多算法的基础,可以在蛮力法的基础上加以优化,得到更高效的算法。
而且,某些情况下,算法规模不大,使用优化的算法没有必要,而且某些优化算法本身较复杂,在规模不在时可能因为复杂的算法浪费时间,反而不如简单的暴力搜索。
使用暴力法常用如下几种情况:
(1)搜索所有的解空间;
(2)搜索所有的路径;
(3)直接计算;
(4)模拟和仿真。
简单枚举
在枚举复杂对象之前,先尝试着枚举一些相对简单的东西,如整数、子串等。暴力枚举对问题进行一定的分析往往会让算法更加简洁、高效。
除法
输入正整数n,按从小到大的顺序输出所有形如abcde/fghij=n的表达式,其中a~j恰好为数字0~9的一个排列,2≤n≤79。
样例输入:
62
样例输出:
79546/01283=62
94736/01528=62
【分析】
只需要枚举fghij就可以计算出abcde,然后判断是否所有数字都不相同即可。不仅程序简单,而枚举量也从10!=3628800降低至不到1万。由此可见,即使采用暴力枚举,也是需要认真分析问题。
完整的程序如下:
#include <iostream>
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 =