高中信息技术选修一解析法穷举法课件.ppt

1、第三章 算法的程序实现一、解析法、穷举法,信息技术组,例1：某超市规定，顾客购买同种商品10件以上（含10件）可享受批发价。请设计一个收款机程序，输入顾客所购买商品的零售价、批发价、购买数量、及付款数，计算出顾客的应付款及找零。,变量分析： 数学模型： 应付款 找零付款应付款,解析表达式,程序代码：,Private Sub Command1_Click() 零售价 = Val(InputBox(输入零售价：) 批发价 = Val(InputBox(输入批发价：) 数量 = Val(InputBox(输入购买数量：) 付款 = Val(InputBox(输入付款数：) If 数量 10 Then

2、 应付款 = 零售价 * 数量 Else _ End If _ Print 应付款：, 应付款 Print 找零, 找零 End Sub,应付款 = 批发价 * 数量,找零 = 付款 - 应付款,解析法：,就是在分析具体问题的基础上，抽取出一个数学模型，这个数学模型能用若干解析表达式表示出来，解决了这些表达式，问题也就得以解决。 用解析法解决问题的关键是寻找_。,解析表达式,练习：已有的研究成果表明，海拔每升高100米，年平均气温降低0.5。编写程序输入山下的气温及山顶的相对海拔高度，输出山顶的气温。,Private Sub Command1_Click() t0 = Val(InputBox

3、(“输入山下的气温：) h= Val(InputBox(“输入山顶的相对海拔高度：) t=_ Print “山顶的气温为：, t End Sub,t0-h/100*0.5,Private Sub Command1_Click() Const pi = 3.14159265 Dim i As Integer, j As Integer Dim x1 As Single, y1 As Single Dim x2 As Single, y2 As Single Dim a As Single Dim r As Single Dim nodes As Integer Picture1.Scale (-

4、1.5, 1.5)-(1.5, -1.5) 建立坐标系 Picture1.Cls r = 1 nodes = 15 a = 2 * pi / nodes 弧度数 For i = 1 To nodes 枚举 求(x1,y1) x1 = r * Cos(a * i) y1 = r * Sin(a * i) For j = 1 To nodes 枚举 求(x2,y2) If i j Then x2 = r * Cos(a * j) y2 = r * Sin(a * j) Picture1.Line (x1, y1)-(x2, y2), vbBlue 画线 End If Next j Next i E

5、nd Sub,注意：需要添加picture1和command1,程序代码：,Private Sub Command1_Click() a1 = Val(Text1.Text) b1 = Val(Text2.Text) c1 = Val(Text3.Text) a2 = Val(Text4.Text) b2 = Val(Text5.Text) c2 = Val(Text6.Text) x = (c2 - b2 * c1) / (a2 - a1 * b2 / b1) y = (c1 - a1 * x) / b1 Label5.Caption = X= & x Label6.Caption = Y=

6、 & y End Sub,例：韩信点兵,今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？ 求符合条件的最小的数。 尝试用解析法解决： x mod 3=2 x mod 5=3 x mod 7=2 采取从小到大一一尝试的办法。,很难得到有效的解析式。,穷举法,穷举法解韩信点兵问题：,Private Sub Command1_Click() i = 0 Do i = i + 1 Loop Until (i Mod 3=2) And (i Mod 5=3)And (i Mod 7=2) Print i End Sub,穷举范围？ 条件？,Not(i Mod 3=2) And (i

7、Mod 5=3)And (i Mod 7=2),1x,穷举法：（枚举法、列举法）,将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题最终得以解决。 注意判断穷举的范围和条件。,练习：水仙花数,水仙花是指一个三位数，它的各个位数的立方和正好等于该数本身。 如：153=13+53+33 求所有的水仙花数。 分析： 可能的数的范围是_ 数x(abc)需要满足的关系式是_,100999,a3+b3+c3=x,For x = 100 To 999 a = x 100 b = (x Mod 100) 10 c = x Mod 10 If x = a 3 +

8、b 3 + c 3 Then Print x End If Next x,水仙花数解法二：X（abc）,Private Sub Command2_Click() For a = 1 To 9 For b = 0 To 9 For c = 0 To 9 If a * 100 + b * 10 + c = a 3 + b 3 + c 3 Then Print a * 100 + b * 10 + c End If Next c Next b Next a End Sub,1、求解二元一次方程组。,x=(c2-b2*c1)/(a2-a1*b2/b1) y=(c1-a1*x)/b1,达标练习：判断用解析法还是穷举法。,解析法,x,y为实数，无法枚举。,穷举法？,2、百钱百鸡问题：“公鸡五文钱一只，母鸡三文钱一只，小鸡一文钱三只”，一百文钱买一百只鸡，问买公鸡、母鸡、小鸡各多少只？ 分析： x+y+z=100 5x+3y+z/3=100,Private Sub Command1_Click() For x = 1 To 20 For y = 1 To 33 z = 100 - x - y If x * 5 + y * 3 + z / 3 =