资源简介

(共27张PPT)
算法的控制结构
信息技术 高中
解决问题的关键：
找到合理的方法与步骤
情境描述
小明到北京旅游，他乘坐火车到达了北京站，然后准备乘坐地铁去天安门参观，地铁线路图如下图所示，你能帮小明规划好路线吗？是否只有一条路线？请大家思考这个问题。
地铁1号线
地铁5号线
地铁3号线
地铁4号线
路线1：乘坐地铁2号线，从北京站到建国门站，在建国门站换乘1号线，在天安门东站下车。
地铁1号线
路线1：共乘坐4站，换乘1次。
情境描述
地铁5号线
路线2：乘坐地铁2号线，从北京站到崇文门站，在崇文门站换乘5号线，到东单站，在东单站换乘1号线，在天安门东站下车。
地铁1号线
路线2：共乘坐4站，换乘2次。
情境描述
地铁5号线
地铁1号线
地铁1号线
情境描述
寻找路线的方法，可以称之为算法
当你想要从新余去上海迪士尼旅游，你会如何规划行程呢？
算法的概念
广义上讲，算法是解决一个特定问题而采取的确定的、有限的步骤。
① 网上购买迪士尼门票；
② 根据日期，购买火车票或者飞机票；
③ 根据行程及日期安排，预订住宿酒店；
④ 带好各种票据，准备好行李，按时乘车；
⑤ 到达上海，乘坐出租车或公共交通车辆去往酒店入住，放行李；
⑥ 带好门票，按时到迪士尼游玩。
解决同一个问题的算法可能有多种。
算法就是在解决特定问题时，采取的确定的、有限的步骤。
算法的概念
其他方案
一个房间里有三盏灯，房间外有三个开关分别控制这三盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯？
小活动——寻找“开关”
第一步：打开1、2两个开关
第二步：过2分钟后关闭1号开关
第三步：进房间，亮着的灯是由2号开关控制
第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制
第五步：不亮又不热的灯是由3号开关控制
自然语言
流程图
关1号开关
灯亮？
灯热？
该灯由2号开关控制
该灯由1号开关控制
该灯由3号开关控制
小活动——寻找“开关”
流程图是用图形表示算法的一种常用工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确。
开始/结束框
输入/输出框
处理框
判断框
流程线
流程图
流程图符号 名称 功能
开始/结束框 表示算法的开始或结束
输入/输出框 表示输入或输出数据
处理框 框中指出要处理的内容，此框有一个入口和一个出口
判断框 用于表示条件判断及产生分支的情况，判断框有四个顶点，通常上面的顶点表示入口
流程线 用于控制流程方向
流程图
操作时，我们可以在纸上手工绘制流程图，也可以使用工具软件或者到特定的网站进行绘制。
文稿处理软件
流程图绘制软件
在线绘制流程图网站
流程图
用流程图表示“输入一个整数，判断该数是奇数还是偶数”的算法。
该整数除以2余数等于0为偶数，不等于0则为奇数。
Y=X/2的余数
False 否
True 是
开始
结束
Y=0？
输入X
输出“X是偶数”
输出“X是奇数”
算法的描述方法
算法的描述方法
自然语言
流程图
自然语言就是使用日常所用的语言描述算法的步骤。
优点：使用简单，易于理解。
缺点：容易产生二义性。
流程图是用图形表示算法的一种常用工具。
优点：步骤清晰简洁，算法结构表达明确，适合初学者使用。
缺点：绘制过程繁琐，对于复杂问题，结构过于复杂，不易理解。
某地有两种不同类型的出租车，其计费标准分别为：甲车3千米起步，价格10元，3千米以上（不含3千米）每千米为2元；乙车3千米起步，价格8元，3千米以上（不含3千米）每千米2.2元。
设计算法，在不同里程时给出最优资费的用车选择。
实践练习
结构？
实践练习
x ←甲车的资费
y ←乙车的资费
a1←甲车的起步价
a2←乙车的起步价
b1←甲车起步里程后，每千米的费用
b2←乙车起步里程后，每千米的费用
n←计划乘坐的里程数
x,y,a1,a2,b1,b2,n
n > 3
甲车省钱
x开始
x←a1+b1×(n-3)
y←a2+b2×(n-3)
True 是
True 是
x>y
False 否
True 是
乙车省钱
两车相同
False 否
结束
False 否
x←a1
y←a2
S1
Sn
…
顺序结构
False
True
S1
S2
C
选择结构
三种基本结构
S1
C
False
True
循环结构
算法的结构
顺序结构
选择结构
x,y,a1,a2,b1,b2,n
n > 3
甲车省钱
x开始
x←a1+b1×(n-3)
y←a2+b2×(n-3)
True
True
False
x>y
False
True
乙车省钱
两车相同
False
结束
在实际问题解决中，经常会将几种控制结构综合使用。
False 否
x←a1
y←a2
a.洗刷水壶1分钟 b.洗刷茶杯1分钟 c.找茶叶2分钟
d.烧水5分钟 e.泡茶1分钟
假设要泡一杯茶有以下几个步骤：
请问泡好一杯茶需要用多少时间？
洗刷水壶
烧水
找茶叶
泡茶
洗刷茶杯
7分钟
算法效率
已知有10个一模一样的零件，其中9个零件的质量相同，只有一个质量略轻，不符合规格要求。现在有一台天平，请设计算法找出该零件。
算法效率
一一比较？
次数？
其他方法？
二分法
2~3次
1~5次
如果有n个零件（n＞10），要找出其中质量较轻的一个零件，以上方法是否仍然可用？试分析 n = 10000时，这些算法在问题解决效率上的不同。
算法效率
一一比较
二分法
1~5000次
5~13次
效率更高
在解决问题时，可根据问题规模，选择合适算法
地铁1号线
乘坐地铁问题
泡茶问题
零件问题
在实际解决问题的过程中，应综合考虑问题类型、问题规模、适用范围等因素，选择合适算法。
算法效率
计算机解决问题的一般过程
1、分析问题
2、确定算法
3、编写程序
4、调试程序
算法在计算机中的应用
小结
算法概念和描述
算法的概念
算法的效率
算法的描述方法
自然语言
流程图
用日常所用语言来描述算法的步骤。
流程图是用图形表示算法的一种常用工具。
算法就是解决一个特定问题而采取的确定的，有限的步骤。
对于同一个问题，不同算法解决问题的效率不同。
作业布置
思考：用没有刻度的500毫升杯和800毫升杯如何量出200毫升的水？请分别写出自然语言算法和流程图。
谢 谢！

展开更多......

收起↑