第2章 算法实例 ---枚举算法(穷举算法).

Presentation on theme: "第2章 算法实例 ---枚举算法(穷举算法)."— Presentation transcript:

1 第2章 算法实例 ---枚举算法(穷举算法)

2 2、请同学心中想一个两位整数，大家来猜这个数是多少？
课的导入 | 出示问题 出示问题（两个小游戏） 1、从一副扑克牌中抽一张牌，请大家猜这张牌是几，最多猜几次可猜中？ 2、请同学心中想一个两位整数，大家来猜这个数是多少？

3 枚举算法(穷举算法)概念： 当问题的所有可能解的个数不太多时一一列举出该问题 所有可能的解，并在逐一列举的过程中，检查每个可能的解是否是问题的真正解，若是，就采纳这个解，否则抛弃它。(在列举过程中，既不能遗漏，也不应重复) 。 课的导入 | 引出课题 枚举算法流程：

4 枚举算法运用关键： 首先列举所有可能解（即确定可能解的范围） 其次检验是否是真正解(即要找出判断正确解的条件) 不遗漏，不重复

5 输出1--100以内所有能被5整除的数，并统计个数。
课的深入 | 问题 1 输出1--100以内所有能被5整除的数，并统计个数。 开始 输出 c c0 n<=100 cc+1 输出n y n 结束 nn+5 n5 计数器 算法1 分析： 变量n: n依次取5、10、15……100来生成真正解并输出 变量C:计数器，初值为0，找到一个真正解，计数器加1

6 输出1--100以内所有能被5整除的数，并统计个数。
课的深入 | 问题 1 输出1--100以内所有能被5整除的数，并统计个数。 c0 n1 n<=100 cc+1 y n 开始 输出 c 结束 n mod 5=0 nn+1 输出n 算法2（穷举法） 分析： 循环初值：n=1 循环范围：1-100 条件：能被5整除 变量n的作用：既用它控制循环次数，又是一个可能解。

7 输出100—200之间所有能被5或7整除的数并统计个数。
测试反馈 | 问题 输出100—200之间所有能被5或7整除的数并统计个数。 （学生四人一组集体讨论，分别写出流程图并请１学生修改下面流程图） c0 n? n<=? cc+1 y n 开始 输出 c 结束 ? nn+1 算法2（穷举法） 输出n 1.exe 循环初值： 循环范围： 条件: 100 n mod 5=0 or n mod 7=0 伪代码

8 ？ 猜数（模糊不清的标签问题）课本48页例２ 课的深入 | 问题 ２ 循环初值：？ 循环范围：？ 条件：？ 每一变量的作用： ？ 分析：
（要求学生带问题自己看书掌握解决方法并进行流程图填空） 循环初值：？ 循环范围：？ 条件：？ 每一变量的作用： ？ ？ 分析： 程序自动执行过程：

9 小结并布置课外作业 总结 枚举算法解决问题的关键是一定要列举出所有可 能的解，不能遗漏但也不能重复。对于一个能用枚 举法解决的问题，首先要确定循环的范围，其次要 找出判断正确解的条件，这样才能得到正确的算法。 上机作业 2、用穷举法思想来求解鸡兔同笼问题：2.exe 有30个头，90只脚，问鸡、兔各有多少个？ 分析 3、 4、运行猜数课件，体会程序执行过程及穷举算法思想。

10 n mod 57=0 or n mod 67=0,则为真解。 分析：
设单据上的数为n=1XX47,模糊不清的数码XX可能是00~99,因此，n 可能的解是：10047到19947。采用循环结构，让变量j从0—99依次取值，则：n=10047+j*100，其中若 n mod 57=0 or n mod 67=0,则为真解。

11 1、 选择模式结束 n = 100 c = 0 Do While n <= 200 c0
cc+1 y n 开始 输出 c 结束 ? nn+1 输出n n = 100 c = 0 Do While n <= 200 If (n Mod 3 = 0 or n Mod 7 = 0) Then c = c + 1 Print n End If n = n + 1 Loop Print c 选择模式结束

12 2、用穷举法思想来求解鸡兔同笼问题：2.exe 有30个头，90只脚，问鸡、兔各有多少个？ x = 1 Do While x < 30
y n 开始 结束 xx+1 输出x x = 1 Do While x < 30 If 2 * x + 4 * (30 - x) = 90 Then Print x, 30 - x End If x = x + 1 Loop 设鸡为 x只，则 循环初值：？ 循环范围：？ 条件：？

13 3、 分析： 引入一变量i，让i从1开始依次增1，每次都检查i是否为m和n的公约数，是则存入变量gcd中，由于i 是从小到大变化的，所以gcd中最后得到的数必定是两数的最大公约数。 循环初值：？ 循环范围：？ 条件：？

14 枚举算法运用关键： 首先要确定循环的范围（即可能解的范围） 其次要找出判断正确解的条件

15 二、枚举算法实例： 1: 输出100内能被3或7整除的数并 统计个数。 2：猜数（1XX47 课本48页例2）
1: 输出100内能被3或7整除的数并 统计个数。 2：猜数（1XX47 课本48页例2） 3:从键盘上输入两个自然数，计算出它们的最大 公约数。 4：打印输出由1，2……8，9这九个数字组成的所有可能的二位数n(允许各位数字是相同的数，如：11,22…..) 5：打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如，153是一水仙花数，因为153= 6：猜数 （ 1X4X7 课本80页练习8） 7：包装问题（课本46页例1）

16 大家练 1: 输出100---200之间能被3或7整除的数并 统计个数。 2.exe 循环初值：n=1 循环范围：1---100
1: 输出 之间能被3或7整除的数并 统计个数。 开始 n=1 C=0 n<=100 输出 c y n 结束 输出n; c=c+1 n=n+1 n是否满足条件？ 2.exe 循环初值：n=1 循环范围： 条件：n mod 3=0 or n mod 7=0

17 3：从键盘上输入两个自然数，计算出它们的最大 公约数。
分析：引入一变量i，让i从1开始依次增1，每次都检查i是否为m和n的公约数，是则存入变量gcd中，由于i 是从小到大变化的，所以gcd中最后得到的数必定是两数的最大公约数。 流程图 4：打印输出由1，2……8，9这九个数字组成的所有可能的二位数n(允许各位数字是相同的数，如：11,22…..) 分析：a.个位数上的数字可以是哪几种数字？用变量i来表示。 b.十位数上的数字可以是哪几种数字？用变量j来表示。 c.找出二位数n与i,j之间的关系,提示:123=1*102+2*101+3*100 二位数n可记为j+10*i 流程图

18 j=1 i1 开始 i<=9 nj*10+i 输出n y n 结束 ii+1 j<=9 jj+1 说明：用双重循环操作来解决问题。当十位数j在外层循环每取得一定值之后，内层循环完整执行一遍，个位数i从1~9，从而获得不同的二位数n.然后继续执行外层循环，改变一个十位数j,直到j超出规定范围为止。内层循环作为外层循环体的一部分。 For语句

19 For j=1 to 9 for I=1 to 9 n=j*10+I print n next I Next j jj+1 99.exe
开始 i<=9 nj*10+i 输出n y n 结束 ii+1 j<=9 jj+1 For j=1 to 9 for I=1 to 9 n=j*10+I print n next I Next j 99.exe

20 5:猜数（一份单据中被涂抹的数字的推算 1X4X7 课本80页练习8）
流程图 分析：a.十位数上的数字可以是哪几种数字？用变量i来表示。 b.千位数上的数字可以是哪几种数字？用变量j来表示。 c.找出数n与i,j之间的关系：n= j+10i 循环初值：n=10407 循环范围： 条件：n mod 57=0 or n mod 67=0

21 j=0；c=0 i<=9 ii+1 jj+1 输出c
n j+10i y n 结束 ii+1 jj+1 输出c j<=9 i0 n是否是倍数 输出n ; c=c+1

22 打印“水仙花数” x = 100 Do While (x <= 999) a = x Mod 10
b = (x \ 10) Mod 10 c = x \ 100 If x = a ^ 3 + b ^ 3 + c ^ 3 Then Print x End If x = x + 1 Loop

23 6:直角三角形的一条直角边为a,斜边的最大长度为maxc，求所有满足条件的整数解。
流程图 分析：直角三角形三条边a,b,c均为整数，其中：一条直角边给定即为a,斜边C的最大值给定即为maxc，则有下列约束条件： 1. C的值在[a+1，maxc]之间； 2. 对于一个任何确定的C，b的值在[c-a+1，c-1]之间；

24 7:包装问题 包装600个变形金刚，要求是： （1）包装的规格分别是：小盒（每盒2个）、中盒（每盒5个）和大盒（每盒8个）；（2）每种规格的盒数都不能为0 。 流程图 分析： 设600个变形金刚分别装入x个小盒、y个中盒和z个大盒，则必须有 2x+5y+8z=600 显然，x、y、z 值可能的变化范围应为： x: 1 到 （600-13）/2； y: 1 到 （600-10）/5； z: 1 到 （600-7）/8。 说明：用三重循环操作来解决问题。当x在最外层循环每取得一定值之后，第二层循环y要从1--118完整执行一遍，而当y在第二层循环每取得一定值后，最内层循环z要从1--74完整执行一遍。内层循环作为外层循环体的一部分。

25 i=1 ? 输出gcd y n 开始 结束 ii+1 gcdi 输入m,n i同时小于等于m,n i能同时被m,n整除

26 用For语句建立循环结构： For循环语句主要用于建立已知循环次数的循环结构。 For循环语句的格式为： For 循环变量=初值 TO 终值 [Step 步长] <语句块> Next 循环变量 例：输出S=1+2+3+…….+100的和。 S=0 : I=1 Do while I<=100 s=s+I I=I+1 Loop Print s S=0 For I=1 to s=s+I Next I Print s