资源简介

(共25张PPT)
2.2 算法的概念及其描述
学习目标
描述算法的特征，理解算法在问题解决过程中的作用。
选用恰当的描述方法和控制结构表示简单算法，增强用算法解决问题的意识。
情境描述
小明到北京旅游，他乘坐火车到达了北京站，然后准备乘坐地铁去天安门参观，地铁线路图如下图所示，你能帮小明规划好路线吗？是否只有一条路线？请大家思考这个问题。
体验探索
地铁1号线
寻找路线的方法，可以称之为算法。
解决同一个问题的算法可能有多种。
2.2.1认识算法
广义上讲，算法是解决一个特定问题而采取的确定的、有限的步骤。
在计算机领域，算法作为一个精心设计的运算序列，描述了计算机如何将输入转化为输出的过程。
2.2.1认识算法
如何帮助牧羊人成功渡河？
算法是解决一个特定问题而采取的确定的、有限的步骤。
2.2.1认识算法
算法一般具有如下特征：
有输入：一个算法一般要求有0个或多个输入。
有输出：一个算法可以有一个或多个输出。
有穷性：算法必须能在执行有限个步骤之后终止，也就是算法的步骤不能是无限的。
可行性：算法中的每一步的操作都是可以执行的，或者都可以分解成计算机可执行的基本操作。
确定性：算法的每个步骤都具有确定的含义，没有歧义。杜绝含糊不清、模棱两可、二义性描述。
2.2.1认识算法
练一练：
1. 下面关于算法的描述，正确的是（ ）
A. 算法就是解决问题的方法和步骤。
B. 算法可以被无限制的执行。
C. 算法描述了计算机如何将输入转化为输出的过程。
D. 算法可以有零个或多个输入，但只能有一个输出。
C
解析：
A:算法是解决一个特定问题而采取的确定的、有限的步骤。
B:有穷性：算法必须能在执行有限个步骤之后终止，也就是算法的步骤不能是无限的。
D: 算法一般要求有0个或多个输入，1或多个输出。
2.2.2 描述算法
小明在去往地铁站时，在路口遇到了一个红绿灯。小明发现该红绿灯上配有一个倒计时器，倒计时15秒之后红灯变成了绿灯，如何将“倒计时15秒”的算法描述出来？
描述“红灯变绿灯”问题的算法
描述算法是将解决问题的步骤用一种可理解的方式表示出来。
①自然语言
②流程图
③伪代码
2.2.2 描述算法
描述“红灯变绿灯”问题的算法
①自然语言
将计数器t（剩余秒数）设为15；
如果t大于等于1，执行步骤③，否则执行步骤⑤；
显示t，并保持显示1秒，然后清除显示；
将t的值减1，跳转至步骤②。
倒计时结束。
自然语言指人们日常所用的语言。
用自然语言描述算法就是用人们能够读懂的简短语言对算法的步骤进行描述。
易于理解，但有时容易产生二义性，干扰后续编程实现。
2.2.21 认识算法
当你想要从北京去上海迪士尼旅游，你会如何规划行程呢？
① 网上购买迪士尼门票；
② 根据日期，购买火车票或者飞机票；
③ 根据行程及日期安排，预订住宿酒店；
④ 带好各种票据，准备好行李，按时乘车；
⑤ 到达上海，乘坐出租车或公共交通车辆去往酒店入住，放行李；
⑥ 带好门票，按时到迪士尼游玩。
①自然语言
2.2.2 描述算法
②流程图
结束
t ← 15
t ≥ 1
输出t
t ← t-1
True
False
保持显示1秒
清除显示
开始
自然语言
流程图
2.2.2 描述算法
②流程图
流程图是用图形表示算法的一种常用工具。
用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确。
开始/结束框
输入/输出框
处理框
判断框
流程线
连接点
2.2.2 描述算法
②流程图
流程图符号 名称 功能
开始/结束框 表示算法的开始或结束
输入/输出框 表示输入或输出数据
处理框 框中指出要处理的内容，此框有一个入口和一个出口
判断框 用于表示条件判断及产生分支的情况，判断框有四个顶点，通常上面的顶点表示入口
流程线 用于控制流程方向
连接点 用于连接因页面写不下而断开的流程线
2.2.2 描述算法
②流程图
流程图绘制软件
在线绘制流程图网站
操作时，我们可以在纸上手工绘制流程图，也可以使用工具软件或者到特定的网站进行绘制。
文稿处理软件
2.2.2 描述算法
②流程图
A
C
B
顺序结构
算法有顺序结构、选择结构和循环结构三种基本的控制结构。
A
条件
False
True
循环结构
每个步骤按先后次序依次执行
按照条件的成立与否，选择执行不同的分支
条件成立反复执行A,一旦不成立跳出循环
False
True
A
B
条件
选择结构（分支结构）
2.2.2 描述算法
②流程图
对比选择结构与循环结构，你有什么发现？
A
条件
False
True
循环结构
False
True
A
B
条件
选择结构（分支结构）
自上而下
2.2.2 描述算法
②流程图
观察描述“红灯变绿灯”问题的算法，它包含了哪些基本控制结构？
结束
t ← 15
t ≥ 1
输出t
t ← t-1
True
False
保持显示1秒
清除显示
开始
循环结构
顺序结构
2.2.2 描述算法
②流程图
某城市公交车票价2元，乘客可以刷卡乘车。刷卡时，若公交车余额不足2元，提示“请投币”；若余额大于或等于2元但是小于10元，提示“余额即将不足”；若余额大于或等于10元，提示“欢迎乘车”；请你用流程图描述该功能实现的算法。
输入
获取当前的公交卡余额M
输出
输出对应的提示语
主要结构
选择结构
2.2.2 描述算法
②流程图
某城市公交车票价2元，乘客可以刷卡乘车。刷卡时，若公交车余额不足2元，提示“请投币”；若余额大于或等于2元但是小于10元，提示“余额即将不足”；若余额大于或等于10元，提示“欢迎乘车”；请你用流程图描述该功能实现的算法。
2.2.2 描述算法
③伪代码
伪代码是采用一种类似程序设计语言的代码来描述算法。
t ← 15
while t ≥ 1
output 1
sleep 1s
clear
t ← t-1
end while
结束
t ← 15
t ≥ 1
输出t
t ← t-1
True
False
保持显示1秒
清除显示
开始
2.2.2 描述算法
练一练：
算法有（ ）结构、（ ）结构和循环结构三种基本的控制结构。
阅读下面的流程图，它主要包括（ ）结构，它的功能为（ ）。
顺序
选择/分支
求100以内能够被3整除的数
选择、循环
for i in range(1,101):
if i%3==0:
print(i)
算法效率
求100以内能够被3整除的数
求100000以内能够被3整除的数
算法辅助运算
在解决问题时，可根据问题规模，选择合适算法
均体现了“算法效率”
圆周率的计算问题
在实际解决问题的过程中，应综合考虑问题类型、问题规模、适用范围等因素，选择合适算法。
课堂总结
算法概念和描述
算法的概念
算法的特征
算法的效率
算法的描述方法
有输入
有输出
确定性
有穷性
可行性
一个算法通常要求有0个或多个输入。
一个算法可以有一个或多个输出。
算法必须能在有限个步骤之后终止。
算法中的每一步都是可以执行的。
算法的每个步骤都具有确定的含义。
自然语言
流程图
伪代码
用日常所用语言来描述算法的步骤。
流程图是用图形表示算法的一种常用工具。
采用一种类似程序设计语言的代码来描述算法。
算法就是解决一个特定问题而采取的确定的，有限的步骤。
对于同一个问题，不同算法解决问题的效率不同。
课堂实践练习
2. 某地有两种不同类型的出租车，其计费标准分别为：甲车3千米起步，价格10元，3千米以上（含3千米）每千米为2元；乙车3千米起步，价格8元，3千米以上（含3千米）每千米2.2元。
设计算法，在不同里程时给出最优资费的用车选择。选用一种描述方法对该算法进行描述，并解释其中使用到的基本结构。
1.小明早上从起床到出门上学需要洗漱（5min）,烧水（10min）,准备早餐（10min）,听新闻（10min）,请你为他设计一个合理的算法步骤。
课堂实践练习
J←甲车的起步价
Y←乙车的起步价
x1←甲车起步里程后，每千米的费用
x2←乙车起步里程后，每千米的费用
n←计划行使的里程数
J,Y,x1,x2,n
n ≥ 3
甲车省钱
J开始
J←J+x1×(n-3)
Y←Y+x2×(n-3)
True
True
False
J>Y
False
True
乙车省钱
两车相同
False
结束
流程图
2. 某地有两种不同类型的出租车，其计费标准分别为：甲车3千米起步，价格10元，3千米以上（含3千米）每千米为2元；乙车3千米起步，价格8元，3千米以上（含3千米）每千米2.2元。

展开更多......

收起↑