2.1算法的概念及描述　课件　2022—2023学年浙教版（2019）高中信息技术必修1

第二章 算法与问题解决 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