第 2 章 枚 举 教学要求 本章重点 了解枚举算法的概念与枚举设计要领 应用枚举求解统计求和与求最值等基本案例

Presentation on theme: "第 2 章 枚 举 教学要求 本章重点 了解枚举算法的概念与枚举设计要领 应用枚举求解统计求和与求最值等基本案例"— Presentation transcript:

1 第 2 章 枚 举 教学要求 本章重点 了解枚举算法的概念与枚举设计要领 应用枚举求解统计求和与求最值等基本案例
第 2 章 枚 举 教学要求 了解枚举算法的概念与枚举设计要领 应用枚举求解统计求和与求最值等基本案例 本章重点 对某些枚举算法进行改进与优化 掌握枚举算法时间复杂度分析

2 2.1 枚举概述 1. 枚举的概念 (1) 枚举法（Enumerate）也称为列举法、穷举法，是蛮力策略的体现，又称为蛮力法。
2.1 枚举概述 1. 枚举的概念 (1) 枚举法（Enumerate）也称为列举法、穷举法，是蛮力策略的体现，又称为蛮力法。 (2) 枚举是一种简单而直接地解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形 。 (3) 应用枚举时应注意对问题所涉及的有限种情形进行一一列举，既不能重复，又不能遗漏。

3 2. 枚举的框架描述 n=0; for(k=<区间下限>;k<=<区间上限>;k++) // 控制枚举范围
2. 枚举的框架描述 n=0; for(k=<区间下限>;k<=<区间上限>;k++) // 控制枚举范围 if(<约束条件>) // 根据约束条件实施筛选 { printf(<满足要求的解>); // 输出解 n++; // 统计解的个数 }

4 3. 枚举的实施步骤 （1）根据问题的具体情况确定枚举量（简单变量或数组）； （2）根据问题的具体实际确定枚举范围，设置枚举循环；
3. 枚举的实施步骤 （1）根据问题的具体情况确定枚举量（简单变量或数组）； （2）根据问题的具体实际确定枚举范围，设置枚举循环； （3）根据问题的具体要求确定筛选（约束）条件； （4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。

5 2.2 统计与求和 2.2.1 指定特殊整数 案例提出： 试求含有数字7且不能被7整除的5位整数的个 数，并求这些整数的和。
2.2 统计与求和 指定特殊整数 案例提出： 试求含有数字7且不能被7整除的5位整数的个 数，并求这些整数的和。 同时，求这些整数中恰含2个数字7的整数的个 数，以及这些整数的和。

6 1. 枚举设计要点 一般地，设m，n为一位正整数，含有数字m且不能被m整除的n位整数的个数为g1，这些整数的和为s1。其中恰含2个数字m的整数的个数g2及其和s2。 (1) 设置k循环，循环n-1次相乘求出最小的n位整数t。 然后设置k从t至10*t-1循环，枚举所有n位整数。 (2) 每个n位整数k赋给d(为了保持k不变)。然后通过n次求余先后分离出k的数字c，并通过f(c)=f(c)+1统计数字c 的个数。 例如f(7)=2，说明k中恰含2个数字7；若f(3)>0，说明k中含有数字3。 (3) 据f(m)>0 && k%m>0检测含有数字m且不能被m整除，g1与s1作统计求和。 (4) 据f(m)＝2 && k%m>0检测恰含2个m且不能被m整除，g2与s2作统计求和。

7 2. 枚举设计描述 for(k=t;k<=10*t-1;k++) // 枚举每一个n位数 { d=k; for(j=0;j<=9;j++) f[j]=0; for(j=1;j<=n;j++) { c=d%10; f[c]+=1; d=d/10; } if(f[m]>0 && k%m>0) {g1++;s1+=k;} if(f[m]==2 && k%m>0) {g2++;s2+=k;} }

8 2.3 解方程 2.3.1 解佩尔方程 案例提出： 佩尔(Pell)方程是关于x,y的二次不定方程 （其中n为非平方正整数）
2.3 解方程 解佩尔方程 案例提出： 佩尔(Pell)方程是关于x,y的二次不定方程 （其中n为非平方正整数） 当x=1或x=-1，y=0时，显然满足方程。常把x,y中有一个为零的解称为平凡解。我们要求佩尔方程的非平凡解。

9 1. 枚举设计要点 设置y从1开始递增1取值，对于每一个y值，计算a=n*y*y后判别:
1. 枚举设计要点 设置y从1开始递增1取值，对于每一个y值，计算a=n*y*y后判别: 若a+1为某一整数x的平方，则(x,y)即为所求佩尔方程的基本解。 若a+1不是平方数，则y增1后再试，直到找到解为止。 应用以上枚举探求，如果解的位数不太大，总可以求出相应的基本解。 如果基本解太大，应用枚举无法找到基本解，可约定一个枚举上限，例如 。可把y<= 作为循环条件，当y> 时结束循环，输出“未求出该方程的基本解！”而结束。

10 2. 枚举设计描述 y=1; while(y<= ) { y++; // 设置y从1开始递增1枚举 a=n*y*y; x=floor(sqrt(a+1)); if(x*x==a+1) // 检测是否满足方程 { printf(" x=%.0f, y=%.0f\n",x,y); break; }

11 2.4 解不等式 分数不等式 案例提出：

12 1. 枚举设计要点 设和变量为s，递增变量为i，两者赋初值为0。 在s<=m1的条件循环中，根据递增变量i对s累加求和，直至出现s>m1退出循环，赋值c=i，所得c为n解区间的下限。 继续在s<=m2的条件循环中，根据递增变量i对s累加求和，直至出现s>m2退出循环，通过赋值d=i-1，所得d为n解区间的上限。注意，解的上限是d=i-1，而不是i。 然后打印输出不等式的解区间[c,d]。

13 2. 枚举设计描述 scanf("%ld,%ld",&m1,&m2); i=0;s=0; while(s<=m1) {i=i+1;s=s+sqrt(i)/(i+1);} c=i; do while(s<=m2); printf(“ %ld≤n≤%ld \n”,c,i-1);

14 2.5 求最值 2.5.2 整数的因数比 案例提出： 设整数a的小于其本身的因数之和为s，定义 p(a)=s/a 为整数a的因数比。
2.5 求最值 整数的因数比 案例提出： 设整数a的小于其本身的因数之和为s，定义 p(a)=s/a 为整数a的因数比。 试求指定区间 [x,y]中整数的因数比最大值。

15 1. 枚举设计要点 为了求整数a的因数和s,显然1是因数。设置k(2——sqrt(a))循环枚举，如果k是a的因数，则a/k也是a的因数。显然k≤a/k。 如果a=b*b，显然k=b,a/k=b，此时k=a/k。而因数b只有一个，所以此时必须从和s中减去一个b，这样处理以避免重复。 设置max存储因数比最大值。枚举区间内每一整数a，求得其因数和s。通过s/a与max比较求取因数比最大值。

16 2. 枚举设计描述 scanf("%lf,%lf",&x,&y); for(a=x;a<=y;a++) // 枚举区间内的a {s=1;b=sqrt(a); for(k=2;k<=b;k++) // 试商寻求a的因数k if(fmod(a,k)==0) s=s+k+a/k; if(a==b*b) s=s-b; t=s/a; if(max<t) {max=t;a1=a;s1=s;} } printf(" %.0f,%.4f \n",a1,max);

17 案例提出: 2.6 数组与数列 2.6.2 基于2x+3y的递推数列 已知集合A定义如下: （1）1∈A，2∈A
2.6 数组与数列 基于2x+3y的递推数列 案例提出: 已知集合A定义如下: （1）1∈A，2∈A （2）x,y∈A且x≠y => 2x+3y∈A （3）再无其他数属于A。 试求集合A中元素从小到大排列序列的第n项。

18 1. 枚举设计要点 设置a数组存储序列各项，a(t)为序列的第t项。显然a(1)=1,a(2)=2。 设t为项数，在t<n的条件循环中，变量k从2开始递增1取值。 若k可由已有的项a(j)，a(i) (j<i)推得，即若k满足k=2*a(j)+3*a(i) 或k=2*a(i)+3*a(j)，说明k是a数列中的一项，赋值给a(t)。 当项数t达到规定项数n时，则退出循环，打印输出a(n)后结束。

19 2. 枚举设计描述 scanf("%d",&n); a[1]=1;a[2]=2;t=2;k=2; while(t<n) {k++;h=0; // 枚举k是否为A集项 for(i=2;i<=t;i++) {for(j=1;j<=i-1;j++) if(k==2*a[j]+3*a[i] || k==2*a[i]+3*a[j]) { h=1;t++;a[t]=k;} if(h==1) break;} } printf(" a(%d)=%d ",n,a[n]);

20 2.7 数式探求 完美综合式 案例提出： 把数字1,2,...,9这9个数字分别填入以下含加、减、乘、除与乘方(^)的综合运算式中的9个□中 □^□+□□÷□□-□□×□=0 要求数字1,2,...,9这9个数字在式中出现一次且只出现一次，且约定数字“1”不出现在乘、乘方的一位数中。

21 1. 枚举设计要点 设置整数变量，其中a^b用a自乘b次实现。 即要求的综合运算式为: a^b+z/c-d*e=0 设置a,b,c,d,e循环，对每一组a,b,c,d,e，计算z=(d*e-a^b)*c，省略z循环。 检测z是否为二位数。若z非二位数，则返回。 对6个整数进行数字分离，设置f数组对分离的9个数字进行统计，f(x)即为数字x(1—9)的个数。 若某f(x)不为1，标记t=1，则返回。 若所有f(x)全为1，保持标记t=0, 则输出。

22 2. 枚举设计描述 for(a=2;a<=9;a++) for(b=2;b<=9;b++) for(c=12;c<=98;c++) for(d=12;d<=98;d++) // 实施枚举 for(e=2;e<=9;e++) { for(t=1,k=1;k<=b;k++) t=t*a; z=(d*e-t)*c; if(z<10 || z>98) continue; m[1]=a;m[2]=b;m[3]=c;m[4]=d;m[5]=e;m[6]=z;

23 2. 枚举设计描述续 for(x=0;x<=9;x++) f[x]=0; for(k=1;k<=6;k++) { y=m[k]; while(y>0) { x=y%10;f[x]=f[x]+1;y=y/10;} } for(t=0,x=1;x<=9;x++) if(f[x]!=1) {t=1;break;} if(t==0) 则输出一个解；

24 2.8 趣味数阵 自学，可选为课程设计题材。 2.9 枚举应用小结 应用枚举求解，在设计上比较简单，不存在太多难点，但 决不可太随意。
2.8 趣味数阵 自学，可选为课程设计题材。 2.9 枚举应用小结 应用枚举求解，在设计上比较简单，不存在太多难点，但 决不可太随意。 从本章诸案例的枚举设计求解可以看出，枚举思路的调整、 枚举规律的归纳、枚举结构的设置与枚举参量的选择，都有 一定的技巧运用，自然也存在许多改进与优化的空间。

25 1. 简化计算，调整思路 求解案例，根据案例的具体实际确定枚举方案的过程中，简化计算流程，调整求解思路。 2. 观察归纳，寻求规律 面对一个具体案例，通过反复的观察、比较、归纳、总结，找出一般规律，才能确立求解思路与算法。 3. 减少重复，优化结构 在进行枚举设计时，优化枚举结构，减少重复操作，可望在降低枚举的时间复杂度方面收到好的成效。 4. 细化操作，精简参数 枚举结构确定之后，根据案例的具体实际确定合适的参数，是缩减无效操作，提高枚举效率的重要一环。

26 第2章作业 第2章上机 习题2: 1, 2, 3, 4, 5, 6, 7, 8 上机通过本章例2-1, 2-2, 2-3, 2-4；
习题2: 1, 2, 3, 4, 5, 6, 7, 8 第2章上机 上机通过本章例2-1, 2-2, 2-3, 2-4； 上机通过习题 2-3, 2-4, 2-7, 2-8; 上机通过习题 2-9,输出: n= 80 时， 结果： ; n= 100 时，结果： 。

27 欢迎大家提出教学建议 返回