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

第2章 算法与问题解决 第1节 算法的概念及描述（1课时） 教材版本册别：浙教版（2019）必修1 高中信息技术 学习 目录 01 算法的概念 算法的描述 02 学习目标 1 2 了解算法描述方法及特点并能够运用恰当的描述方法表示简单算法； 了解算法的概念与基本特征； 3 能够根据实际需要设计算法解决问题，提升利用信息技术学科素养； 一 课堂导入 想 想 一 一个农夫带着—只狼、一只羊和—棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和—件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。 农夫过河游戏规则 请求出农夫将所有的东西运过河的方案。 提问 一 课堂导入 农夫过河游戏 一 课堂导入 第一步 人和羊过河 第四步 第二步 人和狼过河，人和羊返回，留下狼 第三步 人和菜过河，人返回，留下菜 人和羊过河，人返回，留下羊 将视频中所示的方法我们以文字的方式罗列出来 算法 帮助算法执行者高效地解决问题 Part 1 算法的概念 一 算法的概念 同学们还记得上期刚开学报道的场景吧？ 学校在校园入口处摆放“高一新生报到流程”示意图。 这个“高一新生报到流程”示意图就是一个算法，该算法可以帮助高一新生解决“入学报到”问题。 一 算法的概念 （一） 算法 的定义 古代算法概念 广义算法概念 计算机算法概念 请同学们看一看书上的内容和结合生活经验，想一想什么是算法？ 一 算法的概念 古老 的算法 “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买鸡百，问翁、母、雏各几何？”这是我国古代数学家张丘建在《算经》中提出的经典问题。同时，他还在书中给出了解决该问题的算法“鸡翁每增四，鸡母每减七，鸡雏每益三，即得”。 百钱买百鸡 古代的算法主要指的是“算术”，即数值的算术运算。 古老的算法 随着科学技术的发展，“算法”的外延和内涵逐渐发生着变化。 一 算法的概念 广 义 的 算 法 “算法”指的是解决问题或完成任务的一系列步骤。 广义的算法中，需要解决的问题不仅仅指传统意义上的计算任务（算术），也可以是社会生活中各种事务的处理。 概念 运用 案例 关键 这些算法的执行者往往是人，人们按照算法的要求逐步执行，最终解决问题。 假期的自由行旅游方案、一道菜的烹饪过程、洗衣机的操作步骤等。 一 算法的概念 计 算 机 算 法 概念 案例 计算机程序设计 在包含上万人信息的数据中查找某人的数据、导航程序中两个地点之间最短路线的规划等。 在计算机科学领域内，“算法”指的是用计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的集合。这些需要解决的问题不仅包含了数值计算，还包含了非数值计算的数据处理。 解决这些问题的算法执行者是计算机，为了让计算机理解算法中的步骤，需要用计算机能理解的语言来描述算法并将其输入到计算机中，这个过程就称为计算机程序设计。 设计 方案 编程 调试 提出 问题 分析 问题 解决 问题 一 算法的概念 用计算机解决实际问题的过程中，有两个重要的环节 ①设计算法 ②编制和运行程序来实现算法 一 算法的概念 穷举算法也称枚举算法，指的是在求解过程中，先按照一定的顺序一一列举所有可能的解， 然后用条件判断列举出的可能解是否为 正确解。 穷举法一般适合解决解集为离散的 且范围明确的问题。 穷举算法 一 算法的概念 探 究 交 流 洗衣服的过程 挂号流程 报道流程 解题 步骤 …… 生活中的算法 生活中还有哪些问题也可以用算法描述？ 是不是所有问题都可以用算法描述？ 一 算法的概念 算法 的特征 （二） 有穷性 一个算法的处理步骤必须是有限的。无论具体需要执行的操作步骤有多少，这个数量必须是确定的。 可行性 一个算法中的每一步操作与要求都应该是算法执行者（人或者机器）可以实施的，同时在现实环境中能做到并且能在有限的时间内完成。 一 算法的概念 确定性 0个或多个输入 1个或多个输出 算法中对于每个步骤的执行描述必须是明确的。 算法被执行者实施时，一般需要从外部获取可变的数据。 算法必须包含至少一个输出，以告诉外界问题求解的结果。 一 算法的概念 算法 的要素 （三） 数据 ① 全自动洗衣机操作面板 案例 用算法解决问题时，必须明确参与运算的初始数据、运算时产生的中间数据以及代表问题解决的结果数据。 在洗衣机执行洗衣算法前，必须进行洗涤时间、漂洗次数、脱水时间、每次洗涤所加水量的设置，并将这些设置产生的数据输入到算法中，洗衣机才能按照需求工作。 一 算法的概念 运算 ② 注 意 案例 在洗衣机的控制算法中必须包含“洗涤时间的计时”“漂洗次数的统计”以及“判断加水是否到达50升”等运算。 在对数据进行运算时，必须明确每一步的运算是什么、对哪些数据进行运算等。 一 算法的概念 ③ 控制转移 在洗衣机控制算法的进水过程中，若水量达到50升，则关闭进水阀，否则不关闭进水阀，这个环节就采用了一种称为分支结构（也称选择结构）的控制转移。 漂洗过程中，当漂洗次数未达到2次时，需要继续加水到50升，然后重复原来的漂洗处理，这种需要实现重复执行某些操作的控制转移称为循环结构。 案例1 案例2 在算法执行过程中，有时需要根据数据或运算结果的特点进行不同的处理，这时就需要运用控制转移来执行不同的操作。 Part 2 算法的描述 二 算法的描述 一个作曲家想让一个钢琴家演奏他创作的新作品，首先他要写出琴谱，然后钢琴家才能根据琴谱进行演奏。 设计出一个解决问题的算法，也需要用能被算法执行者理解的形式加以呈现，才能被算法执行者理解并执行。算法的这种呈现就称为算法的描述。 掌握各种算法的描述方法，在解决问题过程中选择恰当的方式合理地描述算法，是解决问题的一个重要环节。 二 算法的描述 用自然语言描述算法 1 自然语言是人们在日常生活中交流使用的语言，如汉语、英语、德语、日语等。用自然语言描述算法通俗易懂，且不需要进行专门的学习和训练。 人们在长期用自然语言描述算法的过程中也逐渐形成了一些约定俗成的规则，了解这些规则有助于快速应用自然语言描述算法。 在算法执行过程中如果需要记住某些数据，且这些数据可能会发生改变，可用“变量”（往往用由字母、数字、下划线等组成的一串字符来表示）来表示这些数据；算法执行过程中某些数据会根据问题特征以不同的值参与计算，这些数据可以通过“输入”来获得。 二 算法的描述 使用自然语言描述算法 输入苹果的重量x 判断苹果的重量是否大于3千克 输出应付款的金额 如果苹果的重量大于3千克，应付款y=3*5+(x-3)*5*0.6 如果苹果的重量不大于3千克，应付款y=x*5 自然语言 第一步 第二步 第三步 第四步 第五步 某超市为了对苹果进行促销，规定苹果原价5元，购买3千克以上的，超过3千克的部分可以在原价的基础上打6折。请同学们用语言描述付款的算法。 二 算法的描述 2 用流程图描述算法 在描述根据条件进行不同处理的算法时比较烦琐 在描述某些操作时容易出现歧义（面对同样的文字描述，不同的人产生不同的理解）； 流程图 流程图描述算法结构清晰、寓意明确。 流程图用一些图形符号表示规定的操作，并用带箭头的流程线连接这些图形符号，表示操作进行方向。 概念 优点 二 算法的描述 图形 名称 功能 开始／结束符 表示算法的开始或结束 输入／输出框 表示算法中数据的输入或输出 处理框 表示算法中数据的运算处理 判断框 表示算法中的条件判断 流程线 表示算法中的流向 连接点 表示算法中的转接 常用的流程图基本图形及其功能 二 算法的描述 3 用伪代码描述算法 人们想出了用伪代码来描述算法。 流程图虽然直观易懂，但当分支增多时会出现流程线相互交叉而影响算法理解的情况。 自然语言和流程图描述的算法要转化为计算机能理解的计算机程序时，中间还需要较多的语义解释和格式转换工作。 伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式，其风格很像计算机程序设计语言，但又不是真正的可以被计算机理解的代码。伪代码的表示方法没有统一、严格的规定，只要定义合理、表达正确即可。 二 算法的描述 伪代码由于语法比较接近计算机程序设计语言，所以描述的算法更加紧凑简练，也便于进一步转化为相应的计算机程序。 条件判断语句 ① 格式1：if 条件 then 　　　 (语句序列1) 　 else 　　　 (语句序列2) 若条件成立，则执行语句序列1（由一个或多个语句组成），否则执行语句序列2。如果在该条件基础上还需要做进一步的条件判断，那么可以进行条件判断语句的嵌套，在If语句中继续放入另一个If 语句。 语义 格式2：if 条件 then 　　　 (语句序列1) 当条件成立需要执行特定的语句序列1，而条件不成立不需要执行特定的处理时，则采用下列格式： 二 算法的描述 循环语句 ② while 条件 （循环体） 循环体由一个或多个语句组成。循环语句执行时，先判断条件是否成立，若条件成立则执行循环体，循环体执行完后再次判断条件是否成立，如此重复，直到某次条件不成立，则结束循环语句，接着去执行循环语句后面的语句。 格式 语义 二 算法的描述 4 用计算机程序设计语言描述算法 无论是自然语言描述的算法，还是流程图或者伪代码描述的算法，计算机都无法理解并执行。为了让计算机帮助人们真正解决问题，需要将算法用某种计算机程序设计语言来描述，这个过程称为程序编写（或称代码编写）。 世界上有很多计算机程序设计语言，实际工作中可以根据问题特点选择恰当的程序设计语言来描述算法。 二 算法的描述 讨论探究 停车场车位探测中的算法 某停车场每个车位的上方都装有传感器（车位探测器）、前方装有车位指示灯（空车位显示绿色，否则显示红色），如下图所示。车位上方的传感器探测下方的车位是否为空，然后根据探测结果控制车位指示灯的颜色并向区域控制器发送该车位的状态信息（“空车位”或“非空车位”）。 停车场中的车位探测 请同学们之间相互讨论，用自然语言、流程图、N-S图、伪代码、程序语言描述。 二 算法的描述 自然语言 分析：传感器每隔一段时间对车位进行探测，在某个时刻，若传感器测得结果为空车位，则将指示灯设置为绿色，同时向区域控制器输出“空车位”的信息；否则，将指示灯设置为红色，同时向区域控制器输出“非空车位”的信息。 将传感器回传的数据作为输入数据并进行数字化设定，若测得空车位，则用输入数值1表示，否则用输入数值0表示。因为该数据会发生改变，所以用变量flag保存该输入数据。 根据上述分析，某个时刻对车位进行数据处理的任务可以界定为以下问题： 输入flag的值，根据flag的值设置车位上方指示灯的颜色，并输出车位状态（“空车位”或“非空车位”）。 解决本问题的算法可以用自然语言描述如下。 （1）输入变量flag的值。 （2）若flag的值为1，则设置指示灯为绿色，输出“空车位”；否则，设置指示灯为红色，输出“非空车位”。 二 算法的描述 用流程图表示车位探测中的算法 二 算法的描述 N-S图 “N-S图”是由美国学者纳西（Nassi）和斯奈德曼（Shneiderman）提出的一种在流程图中完全去掉流程线，全部算法写在一个矩形框内的算法描述方式。相比于原来的流程图描述，结构性显得更好，也更有助于高效地编写程序。 用N-S图表示车位探测中的算法 二 算法的描述 车位探测中的算法用伪代码表示 代码 注释 flag←车位探测结果； If flag=1 then (指示灯绿色输出“空车位”) Else (指示灯红色输出“非空车位”) #将测得的车位当前状态值输入给变量flag 二 算法的描述 车位探测中的算法用C++程序设计语言描述 代码 该程序的运行结果如下图 void MainWindow::on_pushButton_clicked() { int flag = ui->lineEdit->text().toInt(); if (flag == 1){ ui->label_4->setStyleSheet("color:green;"); ui->label_4->setText("绿色"); ui->label_5->setText("空车位"); } else { ui->label_4->setStyleSheet("color:red;"); ui->label_4->setText("红色"); ui->label_5->setText("非空车位"); } } 当前车位无车时的输出信息 当前车位有车时的输出信息 二 算法的描述 车位探测中的算法用Python程序设计语言描述表示 代码 flag=int(input("输入车位状态值：")) if flag==1: print("绿色") print("空车位") else: print("红色") print("非空车位") 二 算法的描述 计算机程序设计语言 计算机程序设计语言经历了“机器语言→汇编语言→高级语言”的发展历程。机器语言中的指令由“0”“1”二进制码组成，机器执行效率高但可读性、维护性差。为了提升编程的效率，科学家用特定的符号（助记符）来表示各个机器指令，发明了汇编语言。科学家后来又发明了高级语言，用接近人类日常用语的符号来表示各类指令。常见的高级语言有Basic、C、C++、Java、Python、Ruby等。 拓展链接 Part 3 小结 三 小结 Part 4 课堂小练 四 课堂小练 只需知道数据之间相互链接的顺序 探讨与讨论 1.算法流程图中矩形框的功能是（ ） A.表示算法的开始或结束 B.表示算法中变量的计算与赋值 C.表示算法中的条件判断 D.表示算法中变量的输入或输出 B 答案：B 解析：本题考查算法流程图。算法流程图中矩形框的功能是表示变量的计算与赋值。 四 课堂小练 只需知道数据之间相互链接的顺序 探讨与讨论 2.下列关于算法的叙述,正确的是（ ） A.描述算法只能使用自然语言 B.算法如果没有数据输入就没有数据输出 C.在执行算法时,必须输入至少一个数据 D.算法必须能在执行有限个步骤之后终止 D 答案：D 解析：本题考查算法的特征及其描述。描述算法的常用方法有自然语言描述算法、流程图描述算法、伪代码描述算法;一个算法至少有一个数据输出;一个算法可以有零个数据输入;算法必须能在执行有限个步骤之后终止。 四 课堂小练 只需知道数据之间相互链接的顺序 探讨与讨论 3.下列关于算法的叙述,正确的是（ ） A.算法必须有数据输入 B.算法只能用流程图描述 C.算法必须有数据输出 D.可以用算法描述“输出所有素数” C 答案：C 解析：本题考查算法的特征及其描述。算法能用自然语言、流程图、伪代码描述;一个算法必须有零个或多个数据输入;一个算法必须有一个或多个数据输出;不可以用算法描述“输出所有素数”,因为不满足算法的有穷性。 谢谢！ 高中信息技术浙教版必修1 $$