资源简介

(共32张PPT)
算法概念与描述
algorithm concepts and descriptions
信息技术
CONTENTS
目录
认识算法
总结
描述算法
1
2
3
情景描述
狼羊菜问题
一个农夫带着一条狼、一头羊和一篮蔬菜要过河，但只有一条小船可用。乘船时，农夫每趟只能带一样东西。当农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊，羊会吃菜。
请设计一个方案，使农夫能安全地将这三样东西带过河。
情景描述
方案一
情景描述
方案二
情景描述
01
02
04
03
农夫带羊过河
农夫返回
农夫带狼过河
农夫带羊返回
农夫带菜过河
农夫返回
农夫带羊过河
农夫带羊过河
农夫返回
农夫带菜过河
农夫带羊返回
农夫带狼过河
农夫返回
农夫带羊过河
解决农夫带狼羊菜过河的方法，可以称之为算法
01
认识算法
recognize algorithms
算法的概念
广义上讲，算法是解决一个特定问题而采取的确定的、有限的步骤。
清洗茶壶、茶杯、拿茶叶
烧水
泡茶
算法的概念
1
2
4
方案一：
方案二：
方案三：
以上方案中，哪一个可行且高效？
解决同一个问题的算法可能有多种。
算法的特征
《九章算术》“更相减损术”
算法的特征
在计算机领域，算法作为一个精心设计的运算序列，描述了计算机如何将输入转化为输出的过程。算法一般具有如下特征：
算法的特征
有输入
一个算法通常要求有0个或多个输入。
有输出
一个算法可以有一个或多个输出。
有穷性
算法必须能在有限个步骤之后终止。
可行性
算法中的每一步都是可以执行的。
确定性
算法的每个步骤都具有确定的含义，没有歧义。
更相减损数中输入153和119，print(“Hello,World!”)
02
描述算法
describe the algorithm
算法的描述方法
自然语言
小明在去往地铁站时，在路口遇到了一个红绿灯。小明发现该红绿灯上配有一个倒计时器，倒计时15秒之后红灯变成了绿灯，如何将“倒计时15秒”的算法描述出来？
算法的描述方法
自然语言
将计数器t（剩余秒数）设为15；
如果t大于等于1，执行步骤③，否则执行步骤⑤；
显示t，并保持显示1秒，然后清除显示；
将t的值减1，跳转至步骤②。
倒计时结束。
倒计时15秒？
算法的描述方法
优势
不足
简单直接，比较容易掌握。
算法中含有多分支或循环操作较多时难以清晰表示；
自然语言的歧义性易导致算法执行的不确定性。
小明请小李和他的朋友去看电影。
算法的描述方法
流程图是用图形表示算法的一种常用工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确。
流程图
流程图符号 名称 功能
开始/结束框 表示算法的开始或结束
输入/输出框 表示输入或输出数据
处理框 框中指出要处理的内容，此框有一个入口和一个出口
判断框 用于表示条件判断及产生分支的情况，判断框有四个顶点，通常上面的顶点表示入口
流程线 用于控制流程方向
算法的描述方法
结束
t ← 15
t ≥ 1
输出t
t ← t-1
True
False
保持显示1秒
清除显示
倒计时15秒？
将计数器t设为15；
如果t大于等于1，执行步骤③，否则执行步骤⑤；
显示t，并保持显示1秒，然后清除显示；
将t的值减1，跳转至步骤②。
倒计时结束。
开始
流程图
算法的描述方法
循环结构
顺序结构
选择结构
三种基本结构
结束
t ← 15
t ≥ 1
输出t
t ← t-1
True
False
保持显示1秒
清除显示
开始
算法的描述方法
S1
Sn
…
顺序结构
三种基本结构--顺序结构
算法的描述方法
False
True
S1
S2
条件
选择结构
三种基本结构--选择结构（分支结构）
算法的描述方法
三种基本结构
S1
条件
False
True
循环结构
食堂阿姨打菜：接过顾客的餐盘→询问菜品→打菜→递回餐盘，重复以上过程，直到所有顾客的菜都打完为止。
公交司机：驾驶到一个站点→停车→开前后门→等乘客上下车→关门→继续行驶，重复以上过程，直到交接班时间为止。
循环体
算法的描述方法
注意区分
选择和循环
三种基本结构
False
True
S1
S2
条件
选择结构
S1
条件
False
True
循环结构
算法的描述方法
操作时，我们可以在纸上手工绘制流程图，也可以使用工具软件或者到特定的网站进行绘制。
算法的描述方法
辗转相除法
输入m,n
R=0
m=n
循环结构
算法的描述方法
伪代码
t ← 15
while t ≥ 1
output 1
sleep 1s
clear
t ← t-1
end while
倒计时15秒？
三种描述方法的比较
算法描述的方法 优势 不足
自然语言 简单直接易掌握 难以清晰表示
不确定性
流程图 清晰简洁 易于表达选择结构 利于不同环境的程序设计 形势复杂
伪代码 书写方便易于理解 便于向计算机程序设计语言过渡 需懂专业技能才能编写
不直观
错误不容易排查
03
总结
summary
算法概念和描述
算法的概念
算法的特征
算法的描述方法
有输入
有输出
确定性
有穷性
可行性
一个算法通常要求有0个或多个输入。
一个算法可以有一个或多个输出。
算法必须能在有限个步骤之后终止。
算法中的每一步都是可以执行的。
算法的每个步骤都具有确定的含义。
有输入
有输出
有穷性
可行性
自然语言
流程图
伪代码
用日常所用语言来描述算法的步骤。
流程图是用图形表示算法的一种常用工具。
采用一种类似程序设计语言的代码来描述算法。
算法就是解决一个特定问题而采取的确定的，有限的步骤。
实践练习
阅读流程图说出它的功能。
输出0~100可以被3整除的所有整数
实践练习
某城市公交车票价 2 元，乘客可以刷卡乘车。刷卡时，若公交卡余额不足 2 元，提示“请投币”；若余额大于等于 2 元但小于 10 元，提示“余额即将不足”；若余额大于等于 10 元，提示“欢迎乘车”。请用流程图描述该功能。
实践练习
感谢聆听
thanks for listening
信息技术

展开更多......

收起↑