算法竞赛入门经典授课教案第章暴力求解法.docx

《算法竞赛入门经典授课教案第章暴力求解法.docx》由会员分享，可在线阅读，更多相关《算法竞赛入门经典授课教案第章暴力求解法.docx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结【教学内容相关章节】第 7 章暴力求解法可编辑资料 - - - 欢迎下载精品名师归纳总结7.1 简洁枚举7.2枚举排列7.3子集生成7.4 回溯法7.5隐式图搜寻【教学目标 】（ 1）把握整数、子串等简洁对象的枚举方法。（ 2）娴熟把握排列生成的递归方法。（ 3）娴熟把握用“下一个排列”枚举全排列的方法。（ 4）懂得解答树，并能估算典型解答树的结点数。（ 5）娴熟把握子集生成的增量法、位向量法和二进制法。（ 6）娴熟把握回溯法框架，并能懂得为什么它往往比生成

2、- 测试法高效。（ 7）娴熟把握解答树的宽度优先搜寻和迭代加深搜寻。（ 8）懂得倒水问题的状态图与八皇后问题的解答树的本质区分。（ 9）娴熟把握八数码问题的BFS实现。（ 10）娴熟把握集合的两种典型实现hash 表和 STL 集合。【教学要求 】把握整数、 子串等简洁对象的枚举方法。娴熟把握排列生成的递归方法。娴熟把握用 “下一个排列” 枚举全排列的方法。懂得子集树和排列树。娴熟把握回溯法框架。娴熟把握解答树的宽度优先搜寻和迭代搜寻。娴熟把握集合的两种典型实现hash 表和 STL 集合。【教学内容提要】本章主要争论暴力法（也叫穷举法、蛮力法），它要求调设计者找出全部可能的方法，然后挑选其中

3、的一种方法，如该方法不行行就摸索下一种可能的方法。介绍了排列生成的递归方法。在求解的过程中，提出明白答树的概念（如子集树和排列树）。介绍了回溯法的基本框架。介绍了集合的两种典型实现hash 表和 STL 集合。【教学重点、难点】教学重点：（ 1）娴熟把握排列生成的递归方法。（ 2）懂得解答树，并能估算典型解答树的结点数。（ 3）娴熟把握子集生成的增量法、位向量法和二进制法。（ 4）娴熟把握回溯法框架，并能懂得为什么它往往比生成- 测试法高效。（ 5）娴熟把握解答树的宽度优先搜寻和迭代搜寻。（ 6）娴熟把握集合的两种典型实现hash 表和 STL 集合。教学难点：（ 1）娴熟把握子集生成的增量法

4、、位向量法和二进制法。（ 2）娴熟把握回溯法框架，并能懂得为什么它往往比生成- 测试法高效。（ 3）娴熟把握解答树的宽度优先搜寻和迭代搜寻。（ 4）娴熟把握集合的两种典型实现hash 表和 STL 集合。【课时支配 】7.1简洁枚举7.2枚举排列7.3子集生成7.4回溯法7.5隐式图搜寻可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -引言暴力法也称为穷举

5、法、蛮力法， 它要求调设计者找出全部可能的方法，然后挑选其中的一种方法，如该方法不行行就摸索下一种可能的方法。暴力法也是一种直接解决问题的方法，经常直接基于问题的描述和所涉及的概念定义。暴力法不是一个最好的算法，但当我们想不出更好的方法时，它也是一种有效的解决问题的方法。暴力法的优点是规律清楚，编写程序简洁。在程序设计竞赛时，时间紧急，相对于高效的、奇妙的算法，暴力法编写的程序简洁，能更快的解决问题。同时蛮力法也是许多算法的基础，可以在蛮力法的基础上加以优化，得到更高效的算法。而且， 某些情形下， 算法规模不大，使用优化的算法没有必要，而且某些优化算法本身较复杂，在规模不在时可能由于复杂的算法

6、铺张时间，反而不如简洁的暴力搜寻。使用暴力法常用如下几种情形：（ 1）搜寻全部的解空间。（ 2）搜寻全部的路径。（ 3）直接运算。（ 4）模拟和仿真。7.1简单枚举在枚举复杂对象之前，先尝试着枚举一些相对简洁的东西，如整数、子串等。暴力枚举对问题进行肯定的分析往往会让算法更加简洁、高效。7.1.1 除法输入正整数n，按从小到大的次序输出全部形如abcde/fghij=n的表达式，其中a j恰好为数字0 9 的一个排列， 2 n79。样例输入：62样例输出：79546/01283=6294736/01528=62【分析】只需要枚举fghij就可以运算出abcde，然后判定是否全部数字都不相同即可

7、。不仅程 序简洁，而枚举量也从10.=3628800降低至不到1 万。由此可见，即使采纳暴力枚举，也是需要仔细分析问题。完整的程序如下：#include using namespace std;bool testint i,int j /用数组 t 存放 i ， j 的各位数字int t10=0; /初始化数组t ，使得各位数字为0，好处是使得fghij10000时 f 位置为 0int ia = 0;whilei /取 i 中各位数字存放在数组t 中tia+ = i % 10; i = i / 10;whilej /取 j 中各位数字存放在数组t 中tia+ = j % 10; j = j

8、/ 10;/ 判定 aj 是否恰好为数字的0 9 的一个排列可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -forint m = 0; m 10; +m forint n = m+1; n n & n =2 & n = 79 k = 1234;whilek = 98765 int j = k * n;ifj 100000 /如 fghij10000，满意

9、题目的条件，f 位置输出0iftestj,kcout j / ;ifk 10000 cout 0; cout k = n endl;+k;return 0;7.1.2 最大乘积输入 n 个元素组成的序列S，你需要找出一个乘积最大的连续子序列。假如这个最大的乘积不是正整，应输出-1 （表示无解） 。1 n 18， -10 Si 10。样例输入：32 4 -352 5 -1 2 -1样例输出：820【分析】18连续子序列有两个要素：起点和终点， 因此只需要枚举起点和终点即可。由于每个元素的确定值不超过10，一共又不超过18 个元素，最大可能的乘积示会超过10 ，可以用 longlong 存下。完整

10、的程序如下：#include int mainint a20;/存放输入序列的每一个元素 int64 ans = 0; /存放最大的乘积int n;/输入元素的个数 int64 tmp。/存放乘积的中间结果whilescanf%d,&n.=EOF/输入序列中元素的个数n forint i = 0;i n; i+/输入序列中的元素scanf%d,&ai; fori = 0; i n; i+ 可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名

11、师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -/ 从序列中的第0 个元素开头，枚举最大连续乘积，并用ans 储备tmp = 1;forint j = i; j ansans = tmp;ifans0 printf%I64dn,ans;elseprintf%dn,-1;return 0;7.1.3 分数拆分输入正整数k，找到全部的正整数x y，使得 111 。kxy样例输入：212样例输出：21/2=1/6+1/31/2=1/4+1/481/12=1/156+1/131/12=1/84+1/141/12=1/60+1/151/12=1/48+1/161/12

12、=1/36+1/181/12=1/30+1/201/12=1/28+1/211/12=1/24+1/24【分析】找出全部有x，y，枚举完成了就行了。但是从1/12=1/156+1/13可以看出， x 可以比 y可编辑资料 - - - 欢迎下载精品名师归纳总结大许多。由于x y，有 11xy111，因此kyy，即 y 2k。这样，只需要在2k 范畴内枚可编辑资料 - - - 欢迎下载精品名师归纳总结举 y，然后依据y 尝试运算出x 即可。完整的程序如下：#include int mainint k;int x, y, count = 0;/变量 count统计等式的个数whilescanf%d,

13、 &k .= EOF fory = k+1;y = 2 * k; y+ /判定 1/k=1/x+1/y等式的个数，x=k * y / y - k;ifx * y-k = k * y count+;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -printf%dn,count;/输出满意条件的等式的个数fory = k+1; y = 2 * k; y+ /

14、输出满意条件的等式x=k * y / y - k;ifx * y - k = k * y printf1/%d=1/%d+1/%dn,k,x,y;return 0;7.1.4 双基回文数假如一个正整数n 至少有两个不同的进位制b1 和 b2 下都是回文数 （ 2 b1,b 2 10），就称 n 是双基回文数（留意，回文数不以包含前导零）。输入正整数S106，输出比S 大的最小双基回文数。样例输入： 1600000样例输出： 1632995【分析】最自然的想法是：从 n+1 开头依次判定每个数是否为双基回文数，而在判定时要枚举所6可编辑资料 - - - 欢迎下载精品名师归纳总结有可能的基数（2

15、10）。意外的是：对于S10回文数太多太密。完整的程序如下：#include using namespace std;的“小规模数据”来说是足够快的双基可编辑资料 - - - 欢迎下载精品名师归纳总结bool huiwenint n int i,j,a30,s;int total = 0; /存放数 s 是回文数的基数个数forint base = 2; base = 10; base+ i = 1;s = n; whiles ai = s % base; s = s / base; i+;i-;forj = 1; j i/2total+; /数 s 在基 base 下是回文数，就total+

16、 iftotal = 2 return true;return false;int main int s;whilescanf%d,&s = 1 fors = s+1; ; s+ ifhuiwens cout s endl;break;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -return 0;7.2枚举排列输入整数 n，按字典序从大到小的次序输出

17、前n 个数的全部排列。两个序列的字典序大 小关系等价于从头开头第一个不相同位置处的大小关系。例如，1,3,22,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,17.2.1 生成 1 n 的排列对此问题用递归的思想解决：先输出全部以1 开头的排列（递归调用），然后输出以2开头的排列（递归调用），接着以3 开头的排列，最终才是以n 开头的排列。以 1 开头的排列的特点是：第一位是1，后面是按字典序的2 9 的排列。所以在设计递归函数需要以下参数：（ 1

18、）已经确定的“前缀”序列，以便输出。（ 2）需要进行全排列的元素集合，以便依次选做第一个元素。这样，写出以下的伪代码：void print_permutation序列 A，集合 SifSelse为空 输出序列依据 从小到大次序A;依次考虑S 的每个元素vprint_permutation在 A 的末尾填加v 后得到的新序列，S-v;上面的递归函数中递归边界是S 为空的情形，可以直接输出序列A。如 S 不为空，就按从小到大的次序考虑S 中的每个元素，每次递归调用以A 开头。下面考虑程序的实现。用数组表示序列A，集合 S 可以由序列A 完全确定 A 中没有显现的元素都可以选。C 语言中的函数在接受

19、数组参数时无法得到数组的元素个数，所以需要传一个已经填好的位置个数，或者当前需要确定的元素位置cur 。声明一个足够大的数组A，然后调用print_permutationn,A,0，即可按字典序输出1 n 的全部排列。完整的程序如下：#include int A100;/输出 1 n 的全排列的递归函数void print_permutationint n, int* A, int cur int i, j;ifcur = n /递归边界fori = 0; i n; i+ printf%d , Ai; printfn;else fori = 1; i = n; i+ /尝试在 Acur中填各种

20、整数i int ok = 1;forj = 0; j cur; j+ifAj = i ok = 0; /假如 i 已经在 A0 Acur-1显现过，就不能再选ifok Acur = i;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -print_permutationn, A, cur+1; /递归调用int main print_permutation

21、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_permutation的参数列表中， 然后把代码中的ifAj=i和 Acur=i分别改成

22、ifAj=Pi和 Acur=Pi。只有把 P的全部元素按从小到大的次序排序，然后调用print_permutationn,P,A,0即可。但是上述递归函数print_permutation中，禁止 A 数组中显现重复，而在 P 中可能就有重复元素时，所以输出数组A 时就会显现问题。解决方法是统计A0 Acur-1中 Pi的显现次数c1，以及 P 数组中 Pi的显现次数c2。只要 c1c2 ，就能递归调用。枚举的下标i 应不重复、不遗漏的取遍全部Pi值。由于P 数组已经排过序，所以只需检查 P 的第一个元素和全部“与前一个元素不相同”的元素， 即只需在fori=0;in;i+ 和其后的花括号之前

23、加上if.i|Pi.=Pi-1即可。完整的程序如下：#include int P100, A100;/输出数组P 中元素的全排列。数组P 中可能有重复元素 void print_permutationint n, int* P, int* A, int cur int i, j;ifcur = n fori = 0; i n; i+ printf%d , Ai; printfn;else fori = 0; i n; i+if.i | Pi .= Pi-1 int c1 = 0, c2 = 0;forj = 0; j cur; j+ ifAj = Pi c1+; forj = 0; j n;

24、j+ ifPi = Pj c2+; ifc1 c2 Acur = Pi;print_permutationn, P, A, cur+1;int main int i, n;scanf%d, &n;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -fori = 0; i n; i+ scanf%d, Πprint_permutationn, P, A,

25、 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 层结点都没有儿子（即都是叶子） ，而每个叶子对应于一个排列，共有n. 个叶子。由于这棵树展现的是逐步生成完整解的过程，因此将其称为解答树。提示 7-1

26、：假如某问题的解可以由多个步骤得到，而每个步骤都有如干种挑选（这些候 选方案集可能会依靠于从前作出的挑选），且可以用递归枚举法实现，就它的工作方式可以用解答树描述。通过逐层查看，第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.，就全部结点之和为：可编辑资料 - - - 欢迎下载精品名师归纳总结n 1n .T nn 11n .n 1 1n .可编辑资料 - - - 欢迎下载精品名师归纳总结k 0 nk1.n 1k

27、0 nk11.k 0 k .可编辑资料 - - - 欢迎下载精品名师归纳总结依据高等数学中的泰勒绽开公式，limxk0 k .e ，因此 Tnn. e=On. 。由于叶子可编辑资料 - - - 欢迎下载精品名师归纳总结有 n. 个，倒数其次层也有n. 个结点，因此上面的各层全部来源于最终一两层，所以上面的结点数可以忽视不计。7.2.4 下一个排列枚举全部排列的另一个方法是从字典序最小排列开头，不停调用 “求下一个排列”的过程，在 C+的 STL 中供应了一个库函数next_permutation。完整的程序如下：#include #include using namespace std; in

28、t main int n, p10; scanf%d, &n;forint i = 0; i n; i+ scanf%d, πsortp, p+n; /排序，得到p 的最小排列do forint i = 0; i n; i+printf%d , pi; /输出排列p printfn; whilenext_permutationp, p+n; /求下一个排列return 0;说明：（ 1） STL 里面有个sort函数，可以直接对数组进行随机化快速排序，复杂度为n*log 2n，效率高。使用这个函数，需要包含头文件：#include using namespace std;它的函数原型如下

29、：可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - - templatevoidsortRandomAccessIteratorfirst,RandomAccessIteratorlast;这个 sort函数可以传两个参数。第一个参数是要排序的区间首的址，其次个参数是区间尾的址的下一的址。也就是说，排序的区间是a,b。简洁来说， 有一个数组inta100 ，

30、要对从 a0 到 a99 的元素进行排序，只要写sorta,a+100就行了，默认的排序方式是升 序。假如需要对数组t 的第 0 到 len-1的元素排序，就写sortt,t+len;，对向量v 定义 vector v;进行排序，写成sortv.begin,v.end;，排序的数据类型不局限于 整数，只要是定义了小于运算的类型都可以，比如字符串类string。template voidsortRandomAccessIteratorfirst,RandomAccessIteratorlast,StrictWeakOrderingcomp;这个 sort函数可以传三个参数。第一个参数是要排序的区

31、间首的址，其次个参数是区间尾的址的下一的址。也就是说，排序的区间是a,b。简洁来说， 有一个数组inta100 ，要对从 a0 到 a99 的元素进行排序，只要写sorta,a+100就行了，默认的排序方式是升 序。假如是没有定义小于运算的数据类型，或者想转变排序的次序，就要用到第三参数比较函数。比较函数是一个自己定义的函数，返回值是bool 型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数cmpbool cmpint a,int b return ab;排序的时候就写sorta,a+100,cmp;。（ 2）在 C+的 STL 中定义的next_pe

32、rmutation和 prev_permutation函数就是特别敏捷且高效的方法，它被广泛的应用于为指定序列生成不同的排列。next_permutation和prev_permutation函数需要包含algorithm.h头文件。需要留意的是“假如要走遍全部的排列，必需先将元素排序”。（ 3）依据 STL 文档的描述， next_permutation函数将按字母表次序生成给定序列的下一个较大的排列，直到整个序列为降序为止。prev_permutation函数与之相反，是生成给定序列的上一个较小的排列（前一个排列）。二者原理相同，仅遍历次序相反。这两个函数 据可以对整型数组或字符数组操作。

33、（ 4） next_permutation函数原型 template bool next_permutationBidIt first, BidIt last; template bool next_permutationBidIt first, BidIt last, Compare comp;next_permutation函数取由 first,last标记的排列， 并将其重新排序为下一个排列。假如不存在下一个排列，就返回false 。否就，返回true 。第一个版本（）使用底层类型 的小于操作符来确定下一个排列，其次个版本（）依据comp 对元素进行排序。假如原始 字 符 串 是 排 过

34、 序 的 ， 就 连 续 调 用next_permutation函 数 会 生 成 整 个 排 列 集 合 。prev_permutation函数原型与next_permutation函数型类似。7.3子集生成本节介绍子集生成算法：给定一个集合， 枚举它全部可能的子集。为了简洁起见， 本节争论的集合中没有重复元素。7.3.1 增量构造法第一种思路是一次选出一个元素放到集合中，完整程序如下：#include void print_subsetint n, int* A, int cur 可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第

35、9 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -int i;fori = 0; i cur; i+printf%d , Ai; /打印当前集合printfn;int s = cur . Acur-1+1 : 0;/确定当前元素的最小可能值fori = s; i n; i+ Acur = i;print_subsetn, A, cur+1;/递归构造子集int A10; int main print_subset5, A, 0;return 0;留意： 由于 A

36、中的元素个数不确定，每次递归调用都要输出当前集合。另外，递归边界也不需要显式确定假如无法连续添加元素，自然不会再递归了。上面的代码用到了定序的技巧：规定集合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_subsetint n, int* B, int cur

37、 ifcur = n forint i = 0; i cur; i+ifBi printf%d , i; /打印当前集合printfn; return;Bcur = 1;/选第 cur 个元素print_subsetn, B, cur+1;Bcur = 0;/不选第 cur 个元素print_subsetn, B, cur+1;int B10; int main print_subset5, B, 0;return 0;必需当“全部元素是否挑选”全部确定完毕后才是一个完整的子集，因此当 ifcur=n成立时才输出。全部部分解（不完整的解）也对应着解答树上的结点。这是一棵 n+1 层的二叉树（

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