用解析法和穷举法设计程序教学设计

1、 4.14.2 用解析法、穷举法设计程序【学习目标：】 1、理解解析法和穷举法2、分清两者之间的区别在经过大量编程实践之后，人们总结出很多行之有效的算法来解决实际问题。常用的方法有：解析法、穷举法、查找法、排序法、递归法等。4.1 解析法所谓解析法是指：通过分析问题中各要素之间的关系，用最简练的语言或形式化的符号来表达它们的关系，得出解决问题所需的表达式，然后设计程序求解问题的方法。例1：求三角形面积已知a、b、c分别为三角形的三条边长，利用海伦公式求该三角形面积p=(a+b+c)/2编程实现：输入边长a，b，c，如果能构成三角形，输出面积，否则输出“No Answer!”界面如下：Dim a

2、 As Single , b As Single , c As Singlea=val(text1.text)b=val(text2.text)c=val(text3.text)If thenp=(a+b+c)/2s=sqr(p*(p-a)*(p-b)*(p-c)text4.text=format(s,”0.00”) 结果保留两位小数Elsetext4.text=”no answer”End If根据上述回答下列问题（8分，每空4分）（1）、利用海伦公式求三角形面积的算法是_（解析法/查找法/枚举法/排序法）。（2）、填写出参考程序中空白处的表达式_（填写字母：A/B/C/D）A、a + b

3、c or a + c b and b + c aB、a + b c or a + c b or b + c aC、a + b c and a + c b or b + c aD、a + b c and a + c b and b + c a（1）解析法 （2）D用解析法求解问题，许多时候并非只是计算一个解析式就可以完事，还要根据问题给出的已经条件，运用归纳、演绎等逻辑方法，揭示问题各要素之间的关系，寻找表示这种关系的表达式，有时需要计算的解析式是一组而不仅仅是一条。例子2、GDP增长问题某省2016年的GDP是6.7万亿元，如果每年按7%的比例增长，问多少年以后此省的GDP超过15万亿？【算法

4、分析】假设n年后此省的GDP超过15万亿元，根据题意得出数学关系式？求最小的n。【参考程序】Dim p As Single p用于记录GDP的值Dim r As Single r用于记录GDP的年增长比例Dim n As Integer 用于统计年数p=6.7r=0.07n=0Do while _p=p*(1+r)n=n+1LoopPrint n_”年后，GDP的值超过15万亿元。”根据上述回答下列问题：（共6分，每空3分）（1）本题采用的算法是_（填写：解析法/枚举法/排序法/递归法）。（2）写出程序中空白处表达式_（1）解析法 （2）p=154.2 穷举法穷举法也称为枚举法，这种算法是把问

5、题设计的可能情况一一罗列出来，并且根据题目的条件和实际背景逐个做出判断，从中挑选出符合条件的解答。例子1、勾股数勾股数是指满足条件a2+b2=c2的自然数，求出100以内满足ab的所有勾股数。【算法分析】a的取值范围1,100;b的取值范围1,100;c的取值范围1,100.【参考程序】Dim a As Integer,b As Integer,c As IntegerFor a=1 To 100For b=1 To 100For c=1 To 100If _ThenPrint a;b;c abc之间以分号分隔End IfNext cNext bNext （1）本题采用的算法是_（填写：解析法

6、/枚举法/排序法/递归法）。（2）程序代码中空白处应填写的条件是_（填写字母：A/B/C/D）A、ab And a2+b2=c2 B、ab Or a2+b2=c2C、ab And a2+b2=c2 D、ab Or a2+b2=c2（1）枚举法 （2）C使用穷举法时，要恰当地设计变量，并且决定用哪些变量作为搜索的主线，以便穷举出所有可能的情况。穷举一般使用循环结构，要注意循环的起点和终点，对可能的情况不能遗漏，一般也不应重复。编制程序时，还应当根据题目要求准确地写出是否符合条件的判断语句。例子2、换钱问题 要将一张100元的钞票，换成等值的5元、2元、1元一张的钞票共50张。其中一种换发如下：5

7、元：3张 2元：38张 1元：9张 求出所有的换钱方案。【算法设计】x表示5元的张数：1x20;y表示2元的张数：1y50;z表示1元的张数：1z100.【参考程序】Dim x As Integer,y As Integer,z As IntegerFor x=1 To 20For y=1 To 50For z=1 To 100If _ThenPrint x;y;z x y z 之间以分号分隔End ifNext zNext yNext x根据上述回答下列问题：（8分，每空4分）（1）本题采用的算法是_（填：解析法/枚举法/排序法/递归法）。（2）程序代码中空白处应填写的条件是_（填写字母：A

8、/B/C/D）。A、5x + 2y + z=100 Or x + y + z = 50B、5x + 2y + z=100 And x + y + z = 50C、5*x + 2*y + z=100 Or x + y + z = 50D、5*x + 2*y + z=100 And x + y + z = 50（1）枚举法 （2）D解析法和枚举法最大的区别是：枚举法会舍弃一些不符合题意的数据。比如枚举法计算能被3整除的数，从1开始一直枚举，1和2都不符合题意，都舍去，保留符合题意的3 。如果步骤中的任何数据都不能舍去，前一步计算的结果后一步要用的话，就是解析法【随堂练习】1、水仙花数是三位整数：其

9、各位数字立方和等于该数本身，如15313+53+33，如果要求出所有的水仙花数，下列算法最合适的是（ ）A、解析法 B、排序法 C、查找法 D、枚举法2、某市出租车收费标准如下：（1）3公里内（含3公里），收费8元；（2）超过3公里但未超过6公里部分，按1.5元/公里收费；（3）超过6公里部分，按2.25元/公里收费。根据以上标准，输入出租车行驶的公里数，请计算顾客需付费多少元？【算法分析】假设总费用为p，则可以分段计算p=8 （s3）P=1.5*(s-3)+8 (36)【参考代码】Dim s As Single s记录出租车行驶的公里数Dim p As Single p记录总费用s=Val(

10、InputBox(“s=”) 读入出租车行驶的公里数If s6 Thenp=2.25*(s-6)+1.5*3+8End IfPrint p根据上述回答下列问题：（1）、本题采用的算法是_（填写：解析法/查找法/枚举法/排序法）。（2）、程序代码中空白处应填写的条件是_（填写字母：A/B/C/D）.A、33 And s3 Or s20 ，求最小的n。【参考程序】Dim p as single,r as single, n as integerP=13r=0.012n=0Do while_ n=n+1 p=p*(1+r)LoopPrint n:”年后”：”人口超过”：p根据上述回答下列问题（8分，

11、每空4分）（1）、本题采用的算法是_（填写：解析法/枚举法/递归法）（2）、写出参考程序中空白处表达式_5、分析解决问题：有一张单据，编号为四位数，号码为：80，中间两位被污浊看不出来。已知该单据能够被23和37整除，请编程求出该单据号码【算法设计】设百位数字为x，十位数字为y，x和y的范围都是0到94位数8xy0=8*1000+x*100+y*10列举里的两个数字所有可能情况；00,01,02，03,04,05,06,07,08,0910,11,12,13,14,15,16,17,18,1990,91,92，93,94,95,96,97,98,99逐一判断找出符合条件的数字【参考代码】：Di

12、m x as long ,y as long, n as longFor x=0 to 9For y=0 to 9n=8*1000+x*100+y*10If thenPrint nEnd IfNext yNext x根据上述回答下面问题（1）、解决该问题采用的算法是： (填：解析法/枚举法/排序法/递归法)（2）、根据题意程序中的空白处应该填写： （填：A/B/C/D）A、n mod 23=0 OR n mod 37=0B、n23=0 AND n37=0C、n23=0 OR n37=0D、n mod 23=0 AND n mod 37=0(3)、根据算法设计，参考程序中循环体中的语句“n=8*1000+x*100+y*10”一共重复执行了多少次。 。【参考答案】1、D2、（1）解析法 （2）C3、（1）枚举法 “百鸡