算法设计与分析实用教程-电子教案-杨克昌第2章 枚举

《算法设计与分析实用教程-电子教案-杨克昌第2章 枚举》由会员分享，可在线阅读，更多相关《算法设计与分析实用教程-电子教案-杨克昌第2章 枚举（31页珍藏版）》请在金锄头文库上搜索。

1、教学要求 了解枚举算法的概念与枚举设计要领 应用枚举求解统计求和、整数搜索、解方程与不等式、数式、数组、数列与数阵等基本案例 本章重点 对某些枚举算法进行改进与优化 掌握枚举算法时间复杂度分析,第 2 章 枚 举,2.1 枚举概述,1. 枚举的概念 (1) 枚举法（Enumerate）也称为列举法、穷举法，是蛮力策略的体现，又称为蛮力法。 (2) 枚举是一种简单而直接地解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形 。 (3) 应用枚举时应注意对问题所涉及的有限种情形进行一一列举，既不能重复，又不能遗漏。,2. 枚举的框架描述,（1） 区间枚举 n=0; for(k=;k;k+) ;

2、 if() printf(); n+; printf();,（2） 递增枚举 k= while(1) k+; ; if() printf(); return; ,3. 枚举的实施步骤,（1）根据问题的具体情况确定枚举量（简单变量或数组）； （2）根据问题的具体实际确定枚举范围，设置枚举循环； （3）根据问题的具体要求确定筛选（约束）条件； （4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。,2.2 统计与求和,2.2.1 同码小数 s(d,n)= 0.d+0.dd+0.ddd+0.ddd w(d,n)=0.d+20.dd+30.ddd+n0.ddd （两和式为n项之和，其中第k项小数点

3、后有k个数字d，加权和第k项的权系数为k） 依次输入整数d(1d9)，n(1n10000)，计算并输出和s(d,n)与w(d,n)（四舍五入精确到小数点后6位）。,求和的精度并不高，只要设置双精实变量s,w实施累加即可。 设置j(1n)循环枚举和式的每一项，设s的当前项为t，其后一项显然为 t=t/10+0.1*d; 加权和w的每一项在t的基础上乘加权系数j，即累加t*j。,1. 枚举设计要点,2. 枚举设计描述,scanf(“%d,%d“,对于给定的同码小数的和： s(d,n)= 0.d+0.dd+0.ddd+0.ddd w(d,n)= 0.d+20.dd+30.ddd+n0.ddd 输入正

4、整数d(1d9)，n(1n10000)，试精确求和s(d,n)与w(d,n)。 同时统计：在s(d,n)与w(d,n)的n个小数位中，共有多少个小数位s与w对应位的数字相同？,3. 问题引申,（1） 枚举设计要点,设置一维数组s，sj表和的小数点后第j位，s0为和的整数部分；同理设置一维数组w，wj表加权和的小数点后第j位，w0为加权和的整数部分。 1）对应位累加求和 2） 从后向前进位 sj-1=sj-1+sj/10; sj=sj%10; 3） 按对应位比较s与w数字相同 4） 输出和s与w,（2） 枚举设计描述,for(t=0,j=n;j=1;j-) / 对S，W分位求和 t=t+j; s

5、j=(n+1-j)*d; wj=t*d; for(j=n;j=1;j-) / 从后往前逐一进位 sj-1=sj-1+sj/10; sj=sj%10; wj-1=wj-1+wj/10; wj=wj%10; m=0; for(j=1;j=n;j+) / 比较s与w数字相同的位数 if(sj=wj) m+;,2.2.2 三角网格 对指定正整数n，试求n-三角网格中所有不同三角形（大小不同或方位不同）的个数，以及所有这些三角形的面积之和。 重点： （1）分“正立”与“倒立”两类分别统计求和 （2）建立p数组简化求三角形面积之和的计算。 难点: 统计“倒立”三角形时，需对k分奇数与偶数两种情形分别总结规

6、律并实施求和。,2.3 整数搜索,2.3.1 整数对 案例提出： 设b是正整数a去掉一个数字后的正整数，对于给出的正整数n，寻求满足和式a+b=n的所有正整数对a,b。 设计要点： （1）根据给出的n设置整数a的枚举循环，对每一个a,计算b=n-a。 （2）设计条件循环，由赋值表达式d=a/(t*10)*t+a%t; 生成a的各个去数字数。 这些去数字数d逐个与b=n-a进行比较并决定取舍。,2.3.2 基于s的双和数组,把一个偶数2s分解为6个互不相等的正整数a,b,c,d,e,f，然后把这6个正整数分成(a,b,c)与(d,e,f)两个三元组，若这两组数具有以下两个相等特性： 则把数组(a

7、,b,c)与(d,e,f)称为基于s 的双和数组(约定abc,def,ad）。 输入正整数s(10s1000)，搜索并输出基于s 的所有双和数组。,1. 枚举设计要点,设置枚举a,b与d,e循环。 注意到a+b+c=s，且aa，因而d起点为a+1。,2. 枚举设计描述,scanf(“%lf“,2.4 解方程与不等式,2.4.1 佩尔方程 试求关于x,y的不定方程 （其中n为非平方正整数） 的正整数解。 佩尔（Pell）方程是关于x,y的二次不定方程。当x=1或x=-1，y=0时，显然满足方程。常把x,y中有一个为零的解称为平凡解。 佩尔方程的非平凡解很多，这里只要求出它的最小解，即x,y为满足

8、方程的最小正数的解，又称基本解。求出了基本解，其他解可由基本解推出。 对于给定的非平方正整数n，试求出佩尔方程的基本解。,递增枚举设计要点: 对y从1开始递增1取值枚举，每一个y值计算a=n*y*y后判别： 若a+1不是平方数，则y增1后再试。 若a+1为某一整数x的平方，则(x,y)即为所求方程的解。因为y是从1开始递增的，所得解是方程的基本解。 对于某些非平方数n，方程的解位数大大超过计算机语言有效数字的范围，枚举不可能给出正确的解，因此算法中加了另一个结束算法的条件“x1000000000”（此结束条件可根据具体情形而定）。,2.4.2 分数不等式 案例提出： 试解以下关于正整数n的不等

9、式 其中m为从键盘输入的正整数，式中符号为二个“+”号后一个“-”号，即分母能被3整除时符号为“-”。,（1） 设置条件循环，每三项一组累加求和： s=s+1.0/k+1.0/(k+1)-1.0/(k+2); (k=1,4,) 若累加到某一组时sm时退出循环，d=k+1, 可得区间解：nd. 因s(d+1)m，显然s(d)m； 而n=d+2时1.0/(n+3)为“+”，可得s(d+2)m; 以后各项中，“-”项小于其前面的“+”项，可知对于nd+2有s(n)m成立。 （2）在nd时是否有解，逐个求和检验确定离散解。 因而有必要回过头来，在n=1d中一项项求和，得个别离散解。这一步不能省，否则出

10、现遗解。,1. 枚举设计要点,2. 枚举改进,(1) 每三项一组（包含二正一负）累加求和： s=s+1.0/k+1.0/(k+1)-1.0/(k+2); (k=1,4,) 若累加到某一组时sm时退出循环，d=k+1, 可得区间解：nd. （2）此时s(d-1)有可能大于m.为得到s(d-1),在原s(d+1)基础上实施-1.0/d+1.0/(d+1)得s(d-1): 若s(d-1)m,合并得区间解：nd-1； 若s(d-1)m时，s(d-3)还有可能大于m. 因而在上s(d-1)的基础上实施s+1.0/(d-2)-1.0/(d-1),得s(d-3)： 若s(d-3)m, 得一个离散解：nd-3

11、； 若s(d-3)m, 没有离散解。,2.5 数式与运算,2.5.1 奇数序列运算式 要点： （1） 首先枚举区间b,c中的奇数，应用试商法确定并标记每一个奇数是否为素数。 （2） 根据相邻两项决定两项中的运算符号，完成运算式。 难点：实施运算时须实现“先乘后加减”的运算规则。,2.5.2 完美综合运算式 以下含乘方（ab即为a的b次幂）、加、减、乘、除的综合运算式（1）的右边为一位非负整数f，请把数字0,1,2,.,9这10个数字中不同于数字 f 的 9个数字不重复地填入式（1）左边的9个中,（约定数字“1”、“0”不出现在式左边的一位数中,且“0”不为首位），使得该综合运算式成立 +-=f

12、 （1） 满足上述要求的式（1）称为完美综合运算式。 输入非负整数f(0f9)，输出相应的综合运算式。,尽管式中有ab，可改进为整形处理，ab用a自乘b次实现。 同时设置a,b,c,d,e循环，所有量设置在整数范围内枚举，式右数字f从键盘输入。 把运算式变形为z=(d*e+f-ab)*c 对每一组f,a,b,c,d,e，按式（3）计算z。 检测z是否为二位数。若计算所得z非二位数，则返回。 然后分别对7个整数进行数字分离，设置g数组对7个整数分离的共10个数字进行统计，g(x)即为数字x(09)的个数。 若某一g(x)不为1，不满足数字0,1,2,.,9这10个数字都出现一次且只出现一次，标记

13、t=1. 若所有g(x)全为1，满足数字0,1,2,.,9这10个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。,按整形改进设计要点：,2.6 数列与数阵,2.6.1 H形数序列 枚举设计要点: 考察H形数列的排列规律: (1)首先按其位数m升序排列，位数少的在前，位数多的在后； (2)当位数m相同时，按高位数字a升序，a小在前，a大在后； (3)当位数m与高位数字a相同时，按中位数字b升序排列，b小在前，b大在后； (4)当位数m与数字a,b都相同时，按低位数字c升序排列，c小在前，c大在后。 难点：设置s数组按位求和，并实施进位。,2.6.2 三阶素数幻方 最小

14、三阶素数幻方欣赏并引入： 17 113 47 89 59 29 71 5 101 设计关键：数学建模 n-x n+w n-y n+z n n-z n+y n-w n+x 为枚举 n,x,y,w 提供支撑。 难点：判断幻方中9个数都为素数。,2.7 表格与图形,2.7.1 p进制乘法表 设计要点： 当p10时，因涉及数字A、B、C、D、E、F（分别对应数10、11、12、13、14、15），设置字符数组d17=“0123456789ABCDEF“。 设置两个乘数k、j的枚举循环，k：1p-1；j：1k。两个乘数相乘得积为t=k*j。 对其乘积t分为两类输出： tp时，乘积只有一位，输出字符串数组

15、第t个字符dt即可； tp时乘积为二位，输出高位为d(t/p)，低位为dt%p。,2.7.2 基于s的和积三角形 最小的基于73的和积三角形欣赏： 设计关键： 三顶角数枚举并判断； 然后实施各边中间数枚举。,2.8 枚举设计的改进与优化,选择枚举路线 阅读例2-1领会枚举路线选择的重要性。 精简枚举结构 阅读例2-2领会精简枚举结构的重要性。 优化枚举参数 阅读例2-3领会优化枚举参数的重要性。,第2章作业,习题2: 1, 2, 3, 4, 5, 6, 7, 8,第2章上机,上机通过本章例2-1, 2-2, 2-3； 上机通过习题 2-3, 2-4, 2-7, 2-8; 上机通过习题 2-9,2-10. 小组讨论：应用试商法与筛法求解“最小连续m个合数”的设计要点与效率比较。,返回,欢迎大家提出教学建议,