第2章 算法实例 ---枚举算法(穷举算法)
2、请同学心中想一个两位整数,大家来猜这个数是多少? 课的导入 | 出示问题 出示问题(两个小游戏) 1、从一副扑克牌中抽一张牌,请大家猜这张牌是几,最多猜几次可猜中? 2、请同学心中想一个两位整数,大家来猜这个数是多少?
枚举算法(穷举算法)概念: 当问题的所有可能解的个数不太多时一一列举出该问题 所有可能的解,并在逐一列举的过程中,检查每个可能的解是否是问题的真正解,若是,就采纳这个解,否则抛弃它。(在列举过程中,既不能遗漏,也不应重复) 。 课的导入 | 引出课题 枚举算法流程:
枚举算法运用关键: 首先列举所有可能解(即确定可能解的范围) 其次检验是否是真正解(即要找出判断正确解的条件) 不遗漏,不重复
输出1--100以内所有能被5整除的数,并统计个数。 课的深入 | 问题 1 输出1--100以内所有能被5整除的数,并统计个数。 开始 输出 c c0 n<=100 cc+1 输出n y n 结束 nn+5 n5 计数器 算法1 分析: 变量n: n依次取5、10、15……100来生成真正解并输出 变量C:计数器,初值为0,找到一个真正解,计数器加1
输出1--100以内所有能被5整除的数,并统计个数。 课的深入 | 问题 1 输出1--100以内所有能被5整除的数,并统计个数。 c0 n1 n<=100 cc+1 y n 开始 输出 c 结束 n mod 5=0 nn+1 输出n 算法2(穷举法) 分析: 循环初值:n=1 循环范围:1-100 条件:能被5整除 变量n的作用:既用它控制循环次数,又是一个可能解。
输出100—200之间所有能被5或7整除的数并统计个数。 测试反馈 | 问题 输出100—200之间所有能被5或7整除的数并统计个数。 (学生四人一组集体讨论,分别写出流程图并请1学生修改下面流程图) c0 n? n<=? cc+1 y n 开始 输出 c 结束 ? nn+1 算法2(穷举法) 输出n 1.exe 循环初值: 循环范围: 条件: 100 100-200 n mod 5=0 or n mod 7=0 伪代码
? 猜数(模糊不清的标签问题)课本48页例2 课的深入 | 问题 2 循环初值:? 循环范围:? 条件:? 每一变量的作用: ? 分析: (要求学生带问题自己看书掌握解决方法并进行流程图填空) 循环初值:? 循环范围:? 条件:? 每一变量的作用: ? ? 分析: 程序自动执行过程:
小结并布置课外作业 总结 枚举算法解决问题的关键是一定要列举出所有可 能的解,不能遗漏但也不能重复。对于一个能用枚 举法解决的问题,首先要确定循环的范围,其次要 找出判断正确解的条件,这样才能得到正确的算法。 上机作业 2、用穷举法思想来求解鸡兔同笼问题:2.exe 有30个头,90只脚,问鸡、兔各有多少个? 分析 3、 4、运行猜数课件,体会程序执行过程及穷举算法思想。
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,则为真解。
1、 选择模式结束 n = 100 c = 0 Do While n <= 200 c0 cc+1 y n 开始 输出 c 结束 ? nn+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 选择模式结束
2、用穷举法思想来求解鸡兔同笼问题:2.exe 有30个头,90只脚,问鸡、兔各有多少个? x = 1 Do While x < 30 y n 开始 结束 xx+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只,则 循环初值:? 循环范围:? 条件:?
3、 分析: 引入一变量i,让i从1开始依次增1,每次都检查i是否为m和n的公约数,是则存入变量gcd中,由于i 是从小到大变化的,所以gcd中最后得到的数必定是两数的最大公约数。 循环初值:? 循环范围:? 条件:?
枚举算法运用关键: 首先要确定循环的范围(即可能解的范围) 其次要找出判断正确解的条件
二、枚举算法实例: 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=13+53+33 6:猜数 ( 1X4X7 课本80页练习8) 7:包装问题(课本46页例1)
大家练 1: 输出100---200之间能被3或7整除的数并 统计个数。 2.exe 循环初值:n=1 循环范围:1---100 1: 输出100---200之间能被3或7整除的数并 统计个数。 开始 n=1 C=0 n<=100 输出 c y n 结束 输出n; c=c+1 n=n+1 n是否满足条件? 2.exe 循环初值:n=1 循环范围:1---100 条件:n mod 3=0 or n mod 7=0
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 流程图
j=1 i1 开始 i<=9 nj*10+i 输出n y n 结束 ii+1 j<=9 jj+1 说明:用双重循环操作来解决问题。当十位数j在外层循环每取得一定值之后,内层循环完整执行一遍,个位数i从1~9,从而获得不同的二位数n.然后继续执行外层循环,改变一个十位数j,直到j超出规定范围为止。内层循环作为外层循环体的一部分。 For语句
For j=1 to 9 for I=1 to 9 n=j*10+I print n next I Next j jj+1 99.exe 开始 i<=9 nj*10+i 输出n y n 结束 ii+1 j<=9 jj+1 For j=1 to 9 for I=1 to 9 n=j*10+I print n next I Next j 99.exe
5:猜数(一份单据中被涂抹的数字的推算 1X4X7 课本80页练习8) 流程图 分析:a.十位数上的数字可以是哪几种数字?用变量i来表示。 b.千位数上的数字可以是哪几种数字?用变量j来表示。 c.找出数n与i,j之间的关系:n=10407+1000j+10i 循环初值:n=10407 循环范围:10407---19497 条件:n mod 57=0 or n mod 67=0
j=0;c=0 i<=9 ii+1 jj+1 输出c n10407+1000j+10i y n 结束 ii+1 jj+1 输出c j<=9 i0 n是否是倍数 输出n ; c=c+1
打印“水仙花数” 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
6:直角三角形的一条直角边为a,斜边的最大长度为maxc,求所有满足条件的整数解。 流程图 分析:直角三角形三条边a,b,c均为整数,其中:一条直角边给定即为a,斜边C的最大值给定即为maxc,则有下列约束条件: 1. C的值在[a+1,maxc]之间; 2. 对于一个任何确定的C,b的值在[c-a+1,c-1]之间;
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完整执行一遍。内层循环作为外层循环体的一部分。
i=1 ? 输出gcd y n 开始 结束 ii+1 gcdi 输入m,n i同时小于等于m,n i能同时被m,n整除
用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 100 s=s+I Next I Print s