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

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