资源简介

(共25张PPT)
算法的概念及描述
1. 认 识 算 法
2. 描 述 算 法
认识算法--问题探究
【案例1】有一个牧羊人，带着一头羊、一只狼和一颗大白菜准备乘船过河，但是船很小，每次只能带一样东西过去，可是如果狼和羊单独在一起，羊就会被狼吃掉，羊和白菜单独在一起，白菜就会被羊吃掉，那牧羊人怎样才能将三者都顺利的带过河呢？
以小组为单位，讨论帮助牧羊人带着狼、羊、白菜顺利过河的方案。
有一个牧羊人，带着一头羊、一只狼和一颗大白菜准备乘船过河，但是船很小，每次只能带一样东西过去，可是如果狼和羊单独在一起，羊就会被狼吃掉，羊和白菜单独在一起，白菜就会被羊吃掉，那牧羊人怎样才能将三者都顺利的带过河呢？
思考以下问题：
（1）小组得出的方案共有多少步？
（2）这些步骤的顺序是固定不变的吗？
认识算法
参考方案：
（1）人和羊过河，人返回，留下羊。
认识算法
参考方案：
（1）人和羊过河，人返回，留下羊。
（2）人和狼过河，人和羊返回，留下狼。
认识算法
参考方案：
（1）人和羊过河，人返回，留下羊。
（2）人和狼过河，人和羊返回，留下狼。
（3）人和菜过河，人返回，留下菜。
认识算法
参考方案：
（1）人和羊过河，人返回，留下羊。
（2）人和狼过河，人和羊返回，留下狼。
（3）人和菜过河，人返回，留下菜。
（4）人和羊过河。
认识算法
算法的概念
为解决一类特定问题而采取的
确定的、有限的步骤。
认识算法
参考方案2：
（1）人和羊过河，人返回，留下羊。
（2）人和菜过河，人和羊返回，留下菜。
（3）人和狼过河，人返回，留下狼。
（4）人和羊过河。
参考方案1：
（1）人和羊过河，人返回，留下羊。
（2）人和狼过河，人和羊返回，留下狼。
（3）人和菜过河，人返回，留下菜。
（4）人和羊过河。
认识算法

认识算法
算法的概念
为解决一类特定问题而采取的
确定的、有限的步骤。
有些步骤可以颠倒，不影响最终结果。
有些步骤不能颠倒，一旦颠倒，最终的结果就完全不一样。
注意
认识算法
有输入
算法的每个步骤都具有确定的含义（没有歧义）
算法的每一步操作都是可执行的
算法必须能在执行有限个步骤之后终止
（算法步骤不能是无限的）
有输出
一个算法要求有0个或1个输入
一个算法要求有1个或多个输入
有穷性
确定性
可行性
算法特性
认识算法
参考方案：
（1）人和羊过河，人返回，留下羊。
（2）人和狼过河，人和羊返回，留下狼。
（3）人和菜过河，人返回，留下菜。
（4）人和羊过河。
自然语言
描述算法
自然语言
流程图
伪代码
描述算法
描述算法的方法
用自然语言描述算法
描述算法
自然语言：人们日常所用的语言。
用自然语言描述算法：使用人们能读懂的简短语句
对算法的步骤进行描述。
缺点：容易产生二义性
用流程图描述算法
描述算法
流程图：一种常用的表示算法的图形化工具。
顺序结构
选择结构
循环结构
描述算法
三种基本控制结构
描述算法
1.顺序结构
每一个步骤按先后次序被执行，即执行处理A,然后执行处理B，如图所示。
描述算法
2.选择结构
又称分支结构。
根据条件的成立与否，选择执行不同的分支处理，如图所示。当条件成立时(用True表示),执行处理A;当条件不成立时(用False表示)，执行处理B。
描述算法
3.循环结构
当条件成立时，反复执行处理A，一旦条件不成立就立即结束循环，如图所示。
问题探究
【案例2】中国古代的第一部数学专著《九章算术》中记载了“更相减损术”的方法：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译：任意给出两个正数；判断它们是否都是偶数。若是，用2约简;若不是则用较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止，则这个数(等数)就是所求的最大公约数。
小组讨论用流程图实现“利用辗转相除法求a和b的最大公约数”的算法。
描述算法
参考方案
优点：克服了自然语言二义性的缺点。直观易读，问题解决的步骤清晰简洁，算法结构表达明确。
a=r
输入a,b
a不等于b
r=a-b
ra=b
b=r
输出b
结束
开始
否
否
是
是
用伪代码描述算法
描述算法
伪代码描述算法：采用一种类似于程序设计语言的代码来表示算法。
伪代码没有固定的、严格的语法规则，只要定义合理、没有矛盾即可。回避了程序设计语言严格的书写格式，保持了语言叙述准确、无二义性的优点，结构性强，比较容易书写和理解。
课堂小结
算法的概念：
为解决一类特定问题而采取的确定的、有限的步骤。
算法的特征：
（1）有输入
（2）有输出
（3）有穷性
（4）可行性
（5）确定性
课堂小结
算法描述方法 优势 不足
自然语言 通俗易懂 二义性，语句太长，循环和分支难以表达
流程图 清晰简洁，不依赖计算机 难度大
伪代码 书写方便，格式紧凑，便于翻译 语言种类多，不容易规范化
算法描述方法 优势 不足
自然语言
流程图
伪代码