资源简介

(共24张PPT)
算法的概念及描述
问：把大象放进冰箱需要几步？
第一步 把冰箱门打开
第二步 把大象放进去
第三步 把冰箱门关上
汉诺塔游戏
编号从短到长分别为a b c d
第一步 把a移动到Y
第二步 把b移动到Z
第三步 把a移动到Z
第四步 把c移动到Y
第五步 把b移动到Y
第六步 把a移动到Y
第七步 把d移动到Z
第八步 把a移动到X
第九步 把b移动到Z
第十步 把a移动到Y
第十一步 把b移动到X
第十二步 把a移动到X
第十三步 把c移动到Z
第十四步 把a移动到Y
第十五步 把b移动到Z
第十六步 把a移动到Z
什么是算法？
算法的定义
广义：解决问题或完成任务的一系列步骤
不仅仅指计算任务（算术），也可以是社会生活中各种事务的处理。
计算机科学领域：用计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的集合。
为了让计算机理解算法中的步骤，用计算机能理解的语言来描述算法并将其输入到计算机中，这个过程就称为计算机程序设计
不仅包含了数值计算，还包含了非数值计算的数据处理
算法
通俗的讲，“算法”指的是解决问题或完成问题的一系列步骤。
算法应由有限个步骤组成；
① 有穷性
例如：X=-9，
求X的算术平方根？
不可行
② 可行性
例如：X=10，
求X/自然数 的值？
③ 确定性
算法中已包含所需要的数据
④ 0个或多个输入
任何算法都需要结果。
⑤ 1个或多个输出
算法的五大特征
算法的要素：数据 运算 控制转移
求根公式求解一元二次方程的算法：
（1）输入一般形式下的二次项系数a，一次项系数b，常数项c
（2）计算判别式 的值
（3）若 ，则计算 ，输出字符串“方程有实数解”，并输出x的值；否则，输出字符串“方程无实数解”
要素 含义
数据 明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据
运算 明确每一步的运算是什么、对哪些数据进行运算等
控制转移 有时需要根据数据或运算结果的特点进行不同的处理，这时就需要运用控制转移来执行不同的操作
a,b,c, ,x
加减乘除，开根，平方
若......,则......;
否则........
=b2-4ac
>=0
算法的描述
设计出解决问题的算法，也需要用能被算法执行者理解的形式加以呈现，才能被算法执行者（人，计算机）理解并执行。算法的这种呈现就称为算法的描述。
常见的算法描述方式有自然语言、流程图、伪代码、计算机程序设计语言等
自然语言是人们在日常生活中交流使用的语言，如汉语、英语、德语、日语等。
变量：数据可能会发生改变
约定俗成的规则——专业名词
输入，输出.....
常量：数据不会会发生改变
求根公式求解一元二次方程的算法：
（1）输入一般形式下的二次项系数a，一次项系数b，常数项c
（2）计算判别式 的值
（3）若 ，则计算X= ，输出字符串“方程有实数解”，
并输出x的值；否则，输出字符串“方程无实数解”
=b2-4ac
>=0
自然语言描述算法
自然语言是人们在日常生活中交流使用的语言，如汉语、英语、德语、日语等。用自然语言描述算法通俗易懂，且不需要进行专门的学习和训练。
阅读：停车场车位探测中的算法
自然语言描述如下：
（1）输入变量flag的值。
（2）若flag的值为1, 则设置指示灯为绿色，输出“空车位”；
否则，设置指示灯为红色，输出“非空车位。
使用自然语言描述算法的优缺点
优点：容易理解
缺点：书写烦琐，不确定性，对复杂的问题难以表达准确，不能被计算机识别和执行。
流程图描述算法
流程图用一些图形符号表示规定的操作，并用带箭头的流程线连接这些图形符号，表示操作进行方向。
自然语言描述如下：
（1）输入变量flag的值。
（2）若flag的值为1, 则设置指示灯为绿色，输出“空车位”；否则，
设置指示灯为红色，输出“非空车位”。
使用流程图描述算法的优缺点
优点：直观、形象
缺点：不能被计算机识别和执行。
流程图描述算法
求根公式的流程图
图形 名称 功能
开始/结束符 表示算法的开始或结束
输入/输出框 表示算法中数据的输入或输出
处理框 表示算法中数据的运算处理
判断框 表示算法中的条件判断
流程线 表示算法中的流
连接点 表示算法中的转接
？
求根公式求解一元二次方程的算法：
（1）输入一般形式下的二次项系数a，一次项系数b，常数项c；
（2）计算判别式
的值；
（3）若 ，则计算
，输出字符串“方程有实数解”，并输出x的值；否则，输出字符串“方程无实数解”。
=b2-4ac
>=0
求根公式算法流程图
开始
输入二项系数a
一项系数b常数c
计算判别式
计算x=
输出方程
无实数根
输出方程有实数根
输出x
结束
>=0？
伪代码的描述
车位探测算法
计算机程序语言描述算法
为了让计算机真正解决问题，需要将算法用某种计算机程序设计语言来描述，这个过程称为程序编写（或称代码编写）。
车位探测算法
求根公式算法
1. 求矩形面积s的部分流程图如下图所示，矩形的长、宽分别用变量a、b表示，对于框①和框②的作用，下列说法正确的是（ ）
A.框①用于输入a和b的值，框②用于输出s的值
B.框①用于输出a和b的值，框②用于输出s的值
C.框①用于输入a和b的值，框②用于输入s的值
D.框①用于输出a和b的值，框②用于输入s的值
A
练习巩固
2. 有流程图如下图所示，其功能是将键盘输入的数进行相加，
当输入的数为0时输出它们的和，则图中红色加框部分的内容是（ ）
A. B.
C. D.
D

算法执行时，若输入n的值为3，
则输出s的值是（ ）
A.6 B.8 C.9 D.15

3、如下图所示的流程图:
C
4．下面关于算法的描述，正确的是（ ）
A.一个算法只能有一个输入
B. 算法只能用框图来表示
C.一个算法的执行步骤可以是无限的
D.一个完整的算法，不管用什么方法来表示，都至少有一个输出结果
D
5. 下列问题不能用算法描述的是(　　)A. 输入圆的半径,求圆的面积B. 输入十位同学的身高,求他们的平均身高C. 输入三个数,求这三个数的最大数D. 输出所有3的倍数
D
思考：高楼的自动电梯在运行时需要考虑哪些方面（例如方便乘客，节约能源等），请为自动电梯设计一个适宜的算法。
？
提示
A.要让乘客方便，尽可能减少等待。B.要节约能源，尽可能减少空开里程和往返次数。
① 乘客进入电梯房，按目标楼层键并关门启动运行；
② 控制器根据事先存储在电脑中的指标判断人员是否超载？若超载发出提示信息，下去若干人，返回第①步；若未超载，执行下一步；
③关闭电梯门，根据目标楼层键判断上升或下降；
④ 随时判断是否有人按下同方向的请求键。若是，则运行到该层停下，开门上下人，并按键启动；若没有新的请求，则到达既定目标层后，停止；
⑤接受新的请求，转而执行①；否则，停止。
体验算法多样性
(1)输入两个正整数m和n。
(2)若m(3)以m除以n，相除得到的余数为r。
(4)若r = 0，则输出n的值，算法结束；否则，执行步骤(5)。
(5)令m = n， n = r，返回步骤(3)继续执行。
求两个正整数的最大公约数问题
？
辗转相除法
更相减损术
(1)输入两个正整数m和n。
(2)判断两个数是否都是偶数,若是，则用2约简，直至出现奇数。
(3)以较大的数(被减数)减去较小的数(减数)，得到差。
(4)若减数与差相等，则第二步约掉的若干个2与差的乘积就是最大公约数，算法结束；否则，执行步骤(5)。
(5)将减数与差作为比较的数，返回步骤(3)继续执行。
小结
1.算法的概念
解决问题或完成任务的一系列步骤
为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的集合
2.算法的特征
有穷性；可行性；确定性；0个或多个输入；1个或多个输出；
3.算法的要素
数据，运算，控制转移
4.算法的描述
自然语言、流程图、伪代码、计算机程序设计语言

展开更多......

收起↑