资源简介

(共22张PPT)
第二章 算法与问题解决
2.1 算法的概念及描述
学习目标
1.能从生活和学习中发现算法，理解算法的内涵和外延.
2.能在解决问题过程中选择恰当的方式合理地描述算法.
新课讲授
一个牧民带着一条狗、一只羊和一筐白菜过河，路上要经过一条河，河边只有一条很小的船，他每次只能带狗、羊或白菜三者中的一个过河。牧民不在旁边时，狗会吃羊，羊也会吃白菜。问牧民怎么才能把他们都带过河去呢？
过河的方案:
第一步：人带羊过河，人返回，留下羊；
第二步：人带狼过河，人带羊返回，留下狼；
第三步：人带菜过河，人返回，留下菜；
第四步：人带羊过河
这属不属于算法呢？
知识点一：算法的概念
1.算法的定义
广义地讲，算法指的是解决问题或完成任务的一系列步骤。问题可以是计算任务，也可以是社会生活中各种事务的处理。
在计算机科学领域内，算法指的是用计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的集合。问题不仅包含数值计算，还包含非数值计算的数据处理。
方法只是概要，需要将其细化成算法执行者能理解的、更明确的步骤，才能转化为算法。
2.算法的特征
（1）有穷性：一个算法的处理步骤必须是有限的。
符合有穷性吗？
计算所有的偶数的和
2.算法的特征
（2）可行性：一个算法中的每一步操作与要求都应该是算法执行者（人或者机器）可以实施的，同时在现实环境中能做到并且能在有限的时间内完成。
符合可行性吗？
去天上摘最亮的那颗星星送给你的同桌
2.算法的特征
（3）确定性：算法中对于每个步骤的执行描述必须是明确的。
符合确定性吗？
取区间的中点
2.算法的特征
（4）0个或多个输入：算法被执行者实施时，一般需要从外部获取可变的数据。
这几个问题有什么不同？
求x -2x+1=0的根？
求x -2x+C=0的根？
求x -Bx+C=0的根？
求Ax -Bx+C=0的根？
2.算法的特征
（5）1个或多个输出：算法必须包含至少一个输出，以告诉外界问题求解的结果。
因为算法的核心价值就是解决问题，而解决问题的终极目标就是需要知道结果究竟如何。
3.算法的要素
数据
用算法解决问题时，必须明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据。
运算
控制转移
在对数据进行运算时，必须明确每一步的运算是什么、对哪些数据进行运算等。
在算法执行过程中，有时需要根据数据或运算结果的特点进行不同的处理，这时就需要运用控制转移来执行不同的操作。
知识点二：算法的描述
判断一元二次方程ax +bx+c=0是否有实数根？
请同学们用语言描述判断的算法。
1.自然语言
（1）输入方程系数a,b,c的值。
（2）判断b -4ac是否大于等于0。
（3）如果b -4ac大于等于0，输出“有实数根”信息。
（4）如果b -4ac小于0，输出“无实数根”信息。
使用自然语言描述算法的优缺点：
优点：通俗易懂
缺点：容易出现歧义（武松/打死老虎；武松/打/死老虎）；在描述根据条件进行不同处理的算法时比较烦琐。不能被计算机理解和执行。
2.流程图
2.流程图
使用流程图描述算法的优缺点：
优点：结构清晰，寓意明确。
缺点：分支增多时会出现流程线相互交叉而影响算法理解的情况。且不能被计算机理解和执行。
3.伪代码
伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式，其风格很像计算机程序设计语言，但又不是真正的可以被计算机理解的代码。
（1）条件判断语句：
格式1: If条件 then
（语句序列1)
Else
（语句序列2)
格式2: If条件 then
（语句序列1)
（2）循环语句：
格式：while条件
（循环体）
输入方程系数a,b,c的值
If b -4ac≧0 then
（输出“有实数根”信息)
Else
（输出“无实数根”信息)
使用伪代码描述算法的优缺点：
优点：更加紧凑简练，也便于进一步转化为相应的计算机程序。
缺点：不能被计算机理解和执行。
4.计算机程序设计语言
a=int(input(“请输入数a:”))
b=int(input(“请输入数b:”))
c=int(input(“请输入数c:”))
if b**2-4*a*c>=0:
print(“有实数根”)
else:
print(“无实数根”)
体验算法的多样性
著名数学家华罗庚“烧水泡茶”的两个算法。
算法一
第一步：烧水；
第二步：水烧开后，洗刷茶具；
第三步：沏茶。
算法二
第一步：烧水；
第二步：烧水过程中，洗刷茶具；
第三步：水烧开后沏茶。
两个算法的效率哪个更高？为什么？
一个好算法必须用到科学统筹的方法
随堂练习
1. 求圆形周长c的部分流程图如下图所示，圆形的半径用变量r表示，对于框①和框②的作用，下列说法正确的是（ ）
A.框①用于输入r的值，框②用于输出c的值
B.框①用于输出r的值，框②用于输出c的值
C.框①用于输入r的值，框②用于输入c的值
D.框①用于输出r的值，框②用于输入c的值
A
①
c←2*π*r
②
2. 下列关于算法的描述，正确的是（ ）
A.一个算法只能有2个输入
B.算法只能用流程图来表示
C.一个算法的处理步骤可以是无限的
D.算法必须包含至少一个输出
D
3. 如下图所示的流程图:
算法执行时，若输入n的值为3，则输出s的值是（ ）
A.6 B.10 C.4 D.8

D
开始
输入n
m←7
m<=n
s←2*n
s←m+1
输出s
Y
N
结束
4. 有部分流程图结构如下，其算法结构属于（ ）

A.顺序结构 B.重复结构
C.分支结构 D.循环结构
D

展开更多......

收起↑