资源简介

(共21张PPT)
《算法的概念及描述》
体验探索：规划乘车路线
小明同学计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等。请你帮他完成以下路线规划：
1、列举出A站出发到达B站的所有乘车路线。
2、如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。
算法的定义
寻找路线的方法，我们可以称之为算法。
路线①：
一号线从A站坐到E站换乘9号线坐到B,共6站
路线②：
2号线从A站坐到J站换乘4号线坐到B站，共5站
……
算法的定义
从广义上讲，算法是为解决一类特定问题而采取的确定的、有限的步骤。
“做菜的步骤”
“洗衣服的步骤”
算法的定义
计算机科学领域
算法指用计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的，无歧义的、有限步骤的集合。
用计算机能理解的语言描述算法，并输入到计算机中，这个过程就是计算机程序设计。
思考
算法 = 程序？
程序=数据结构+算法
算法的特征
算法作为解决问题的策略，具有五个特征：
有输入
有输出
有穷性
可行性
确定性
一个算法一般要求有0个或多个输入，以描述运算对象的初始情况。
一个算法可以有一个或多个输出，以反映对输入数据加工后的结果。
指算法必须能在执行有限个步骤之后终止，也就是算法步骤不能是无限的。
算法的每一步操作都是可以执行的，或者都可以分解成计算机可执行的操作
算法的每个步骤都具有确定的含义，没有歧义
描述算法
小明在去往地铁站时，在路口遇到了一个红绿灯，小明发现该红绿灯上配有一个倒计时器，倒计时15秒后红灯变成了绿灯，如何将“倒计时15秒”的算法描述出来？
步骤1：将计数器t设为15；
步骤2：如果t大于或等1，执行步骤3，否则倒计时结束；
步骤3：输出t，并保持显示1s，然后清除显示；
步骤4：将t的值减1，跳转至步骤2
自然语言
描述算法的常用方法
同样的画面，分辨率越大，图像越清晰
用自然语言描述算法
自然语言指人们日常所用的语言，用自然语言描述算法就是使用人们能读懂的简短语句对算法的步骤进行描述。
优点：通俗易懂，容易被大众理解。
缺点：容易产生二义性，干扰后续的编程实现。
描述算法的常用方法
用流程图描述算法
流程图是一种常用的表示算法的图形化工具。常用的符号的符号如下：
开始/结束框
输入/输出框
处理框
判断框
流程线
连接点
描述算法的常用方法
流程图符号 名称 功能
开始/结束框 表示算法的开始或结束
输入/输出框 表示输入或输出数据
处理框 框中指出要处理的内容，此框有一个入口和一个出口
判断框 用于表示条件判断及产生分支的情况，判断框有四个顶点，通常上面的顶点来表示入口。
流程线 用于控制流程方向。
连接点 用于连接因页面写不下而断开的流程线
描述算法的常用方法
活动：
思考如何将“倒计时15s”的流程图绘制出来。
开始
t≥1
输出t
保持显示1秒
清除显示
结束
t =15
t t-1
True
False
步骤1：将计数器t设为15；
步骤2：如果t大于或等于1，执行步骤3，否则倒计时结束；
步骤3：输出t，并保持显示1s，然后清除显示；
步骤4：将t的值减1，跳转至步骤2
描述算法的常用方法
对比自然语言描述法和流程图法。你认为用流程图法来描述算法有什么优缺点？
优点：形象直观、清晰简洁 ，算法结构表达明确
缺点：当控制结构和嵌套层次复杂时，对应流程图所占篇幅会比较大，影响可读性，也不易于修改。
用流程图描述算法
描述算法的常用方法
用伪代码描述算法就是采用一种类似于程序设计语言的代码来表示算法。例如，“倒计时15s”的算法用伪代码可以描述为：
用伪代码描述算法
t<-15
while t≥1
output t
sleep 1s
clear
t<-t-1
end while
三种基本控制结构
S1
…
Sn
条件
S1
条件
S1
S2
True
False
True
False
顺序结构
选择结构
循环结构
三种基本控制结构
A
…
B
顺序结构
顺序结构表示程序中的各步操作按出现的先后顺序执行。顺序结构式最简单的一种结构。
它的执行顺序是自上而下，依次执行。
顺序结构
三种基本控制结构
选择结构又称分支结构。根据条件的成立与否，选择执行不同的分支。
当条件成立时，执行处理A；当条件不成立时，执行处理B。
选择结构
条件
A
B
True
False
选择结构
三种基本控制结构
当条件成立时，反复执行处理A,一旦条件不成立就立即结束。
循环结构
条件
A
True
False
循环结构
三种基本控制结构
开始
t≥1
输出t
保持显示1秒
清除显示
结束
t =15
t t-1
True
False
活动：
分析“倒计时15s”算法中包含了哪几种基本结构？
顺序结构
循环结构
任何复杂的算法都可以用这三种基本控制结构组合表示。
实践活动
已知有10个一模一样的零件，其中9个零件的质量相同，只有1个质量略轻，不符合规格要求。现有一台天平，请设计算法找出该零件。比较不同算法在效率上的不同
解决同一问题可能会有不同的算法，不同算法求解的过程可能有不同。在解决问题时，可以根据需要选择合适的算法。
知识小结
算法及其描述
算法的定义
算法的特征
算法的描述
有穷性
确定性
1个或多个输出
可行性
0个或多个输入
描述算法的常用方法
三种基本控制结构
下节课见

展开更多......

收起↑