山东省实验中学教科版高中信息技术选修一:第三章 算法与程序实现 知识要点复习
第三章 算法与程序实现
一、解析法:是指通过分析问题中各要素之间的关系,用最简练的语言或形式化得符号来表达他们的关系,得出解决问题所需的表达式,然后设计程序求解问题的方法。
例1: 假设在平面内,有一个三角形,边长为a、b、c,三角形的面积S可由海伦公式求得:
S=,而公式里的p为半周长:p=(a+b+c)/2,输入三角形的三条边,输出三角形的面积。
Dim a, b, c, p, s As Single
a = Val(InputBox("请输入第一条边边长"))
b = Val(InputBox("请输入第二条边边长"))
c = Val(InputBox("请输入第三条边边长"))
If ____________________ Then
p = (a + b + c) / 2
s = ___________________
Print "三角形面积=" & s
Else
Print "构不成三角形"
End If
1、本题采用的算法是( 解析法 )( 穷举法/解析法/ 递归法/ 排序法)
2、写出程序中空白处表达式(a+b>c and b+c>a and a+c>b Sqr(p * (p - a) * (p - b) * (p - c)))
例2:一玻璃球从高空做自由落体运动,在达到地面时速度为98m/s,请问:该玻璃球从高空开始下落到地面用了多少时间?
Const a =9.8 '自由落体加速度为常量
Dim t as Single '时间
Dim v as Single '到达地面速度
v=98
t=_______
Print “用了” & t & “秒时间”
例3:某省2016年的GDP是6.7万亿元,如果每年按7%的比例增长,问多少年以后此省的GDP可以翻一翻?
Dim p As Single 'p用于记录GDP的值
Dim n As Integer 'n用于统计年数
p = 6.7
n = 0
Do While ____________
p = p * (1 + 0.07)
n = n + 1
Loop
Print "某省" & n & "年后GDP翻一翻"
例4:国内航班乘坐经济舱时,行李托运规定,免费托运行李一般不得超过20公斤,超重每公斤按全票价的1.5%计算。输入行李重量及经济舱全票价后,输出相应的行李托运费。
Dim w As Integer 'w为行李的重量
Dim pj As Integer 'pj为票价
Dim yunfei As Single 'yunfei为运费
w = Val(InputBox("请输入行李重量"))
pj = Val(InputBox("请输入票价"))
第 1 页 共 6 页
If w <= 20 Then
yunfei = 0
Else
yunfei = ____________
End If
Print "托运" & w & "重的行李,需要运费:" & yunfei & "元"
二、穷举法:是例举一切与命题相关的情况,然后根据问题设定的条件,逐个加以检查,找到满足条件的解。
三要素:穷举对象、穷举范围、穷举条件
例1:有一张单据,编号为四位数,号码为:6□□5。中间两位被污浊看不出来,已知该单据能被69和95整除,请编程求出该单据号码。
方案一:for i=0 to 9
for j=0 to 9
t=6*1000+i*100+j*10+5 ‘这条语句执行多少次?
if _______________ then print t
next j
next i
方案二:for i=0 to 99
t=i*10+6005
if _______________ then print t
next i
例2:搬砖问题:
100块砖,100人搬,一个男人搬4块,一个女人搬3块,两个小儿抬1块,要求一次全搬完,问需男、女、小儿各多少人?(男、女、小孩至少1人)
For x = 1 To 25
For y = 1 To 33
For z = 1 To 100
If _________________ Then Print x, y, z
Next z
Next y
Next x
例3:水仙花数是三位整数:其各位数字立方和等于该数本身,如153=1^3+5^3+3^3,如果要求出所有的水仙花数
例4:鸡兔同笼问题。头35个,脚94只,问鸡、兔各多少只?
Dim chicken As Integer
Dim rabbit As Integer
For chicken = 1 To 35
For rabbit = 1 To 23
If _______________________ Then
Print "鸡:" & chicken & "只"
Print "兔:" & rabbit & "只"
End If
Next rabbit
Next chicken
第 1 页 共 6 页
1 本题采用的算法是( 穷举法 )( 穷举法/解析法/ 递归法/ 排序法)
2 写出程序中空白处表达式(chicken + rabbit = 35 And chicken * 2 + rabbit * 4 = 94 )
三、递归算法:函数在定义时,直接或间接地调用了自己。
例1:用递归算法实现10!,10!=10*9!,9!=9*8!,8!=8*7!,……,已知1!=1
f(10)=10*f(9),f(9)=9*f(8),f(8)=8*f(7)……,必须给出f(1)=1
例2:猴子吃桃问题:
小猴有一天摘了若干个桃子,它非常贪吃,当天就吃掉了一半还多一个;第二天接着吃剩下的桃子一半多一个;以后每天都是如此,到了第七天要吃桃子时,发现只剩下一个。问小猴那天一共摘了多少个桃子?
f(6)=2*(f(7)+1) , f(5)=2*(f(6)+1),……f(1)=2*(f(2)+1)
例3:有5个人坐在一起,第5个人说他比第4个人小3岁;第4个人说他比第3个人小3岁;第3个人说他比第2个人小3岁;第2个人又说他比第1个人小3岁;第1个人说他是38岁。问第五个人多少岁?
f(5)=f(4)-3, f(4)=f(3)-3,……,f(1)=38
第 1 页 共 6 页