《数据结构[Python语言描述]》教案第2课绪论（1.4）.docx

《《数据结构[Python语言描述]》教案第2课绪论（1.4）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第2课绪论（1.4）.docx（5页珍藏版）》请在优知文库上搜索。

1、课题第2课绪论(1.4)课时2课时(90min)教学目标知识目标：(1)了解算法的定义、特性、描述方法和设计要求(2)了解算雌能雨介的重要指标技能目标：能分析简单算法的时间复杂度和空间复杂度素质目标：通过对算法的改进，培养科学严谨、精益求精的工匠精神教学重难点教学重点：算法的描述方法和设计要求、算法性能评价的重要指标教学难点：算法的描述方法教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：你认为算法是什么？【蚂思考、传授新知【教师】通过学生的回答引入要讲

2、的知识，介绍算法和算法分析1.4算法和算法分析在实际生活中，人们做任I可事情都是有一定步骤的。例如，要在商场购买某种商品，应首先挑选商品，然后开具小票，接着到收银台付款，最后提货。因此，可以简单地将算法理解为解决某一问题所采取的方法和步骤.1.4.1 算法的定义和特性在计算机领域中，算法是指根据所要处理的问题，在数据的逻辑结构和存储结构基础上,利用有限的步骤解决这一特定问题所采用的一组有穷规则的集合.【高手点拨】算法建立在数据结构之上，它的设计依赖于数据的逻辑结构,而它的实现依赖于数据的存储结构。【教师】随机邀请学生回答以下问题算法有哪些特性?【学生】聆听、思考、回答(1)有穷性。一个算法必须

3、在有限步骤之内正常结束，不能形成无穷循环。(2)确定性。算法中的每一个步骤必须有确定含义，不能有二义性。(3)可行性。算法中的每一个步骤都可以通过已经实现的基本操作运算执行有限次来实现。(4)输入。一个算法可以有0个或多个输入。(5)输出。一个算法至少有一个或多个输出。【拓展阅读】高德纳克努特被誉为现代计算机科学的鼻祖，他所著的描述基本算法与数据结构的经典著作计算机程序设计艺术在计算机史上的地位，堪比数学史上欧几里得所著的几何学原理。（详见教材）1.4.2算法的描述方法1.自然语言使用自然语言（如汉语、英语等）描述算法的优点是简单直观且便于阅读，缺点是不够严谨，与计算机采用的程序设计语言相差很

4、大，需要用户自行进行转换。【教师】讲解实例1-2（详见教材），井介绍自然语言描述步骤2.流程图流程图通过规定的图形符号（见表1-2）来描述算法。使用流程图描述算法的优点是直观、简洁、明了。表1-2流程图常用的图形符号图形符号名称含义()起止符算法的起始或结束处理符算法中的具体处理步骤/7输入/输出符未指定媒体的数据，可用于输入和输出，比较通用O判断符用于对给定的条件进行判断，根据判断的结果选择流程方向或流线符数据流，箭头指示流向O连接符用于连接因页面写不下而断开的流线符，对应的连接符应有同一标记【教师】讲解实例1-3（详见教材），并演示流程图描述步骤【知识库】流程图还包括一些特殊的图形符号，如

5、注解符、文件符、显示符和人工输入符。（详见教材）3 .伪代码伪代码通常用文字和符号来表示。【教师】随机邀请学生回答以下问题伪代码描述算法的优点是什么？【学生】聆听、思考、回答使用伪代码描述算法的优点是忽略了程序设计语言的语法规则和描述细节，更易于用户理解。【教师】讲解实例1-4（详见教材），并演示伪代码描述步骤4 .程序设计语言程序设计语言是用于编写计算机程序的语言。使用程序设计语言描述算法必须严格遵循所用语言的语法规则，编写的程序可直接在计算机上执行，但相对来说不易理解，有时须借助注释语句来提高程序的可读性。【教师】讲解实例1-5(详见教材)，并演示程序设计语言描述步骤【知识库】Python

6、有多种注释方式，常用的有单行注释和多行注释两种。单行注释是以W开始，以换行符结束。这种注释可单独占一行，也可出现在一行中其他内容的右侧。多行注释是以三重引号(单引号或双引号)开始，同样以三重引号结束。1.4.3算法的设计要求(1)正确性。【教师】随机邀请学生回答以下问题如何理解算法设计的正确性？沙【学生】聆听、思考、回答对于几组输入数据,能够得到满足要求的结果。对于精心选择的典型、苛刻且带有刁难性的几组输入数据，能够得到满足要求的结果。对于一切合法的输入数据，都能得到满足要求的结果。(2)可读性。算法主要是为了人们的阅读与交流，其次才是机器执行。因此，算法的表达应思路清晰，层次分明，易于理解，

7、可读性强，以便于后续对算法的使用和修改。(3)健壮性。当输入数据非法时，算法也能做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。(4)高效率与低存储量。通俗地说，效率指的是算法的执行时间。对于同一个问题，若有多个算法可以解决,则执行时间越短的算法效率越高。存储量指的是算法执行过程中所需要的最大存储空间。1.4.4算法分析*【教师】随机邀请学生回答以下问题如何从这些算法中找出最有效的算法呢？【学生】聆听、思考、回答算法分析是每个程序设计人员都应该掌握的技术。评价一个算法的优劣主要看执行这个算法所需的时间(时间复杂度)和存储空间(空间复杂度)。1.算法的时间复杂度算法的时间复杂度(

8、timecomplexity)是指算法的执行时间随问题规模的变化而变化的趋势，反映算法执行时间的长短，记作T(n)=O(f(n).其中，n表示问题规模，是算法求解问题输入量的多少，也是问题大小的本质表示；T(n)表示语句的总执行次数(称为语句频度或时间频度)；f(n)是T(n)的同数量级函数，一般为问题规模n的某个函数。【提示】若存在函数f(n),使得当n趋近于无穷大时，T(n)f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n).其中，0是用来表示数量级的符号。分析算法时间复杂度的步骤如下。(1)找出算法中语句频度最大的语句。(2)计算频度最大语

9、句的频度与问题规模n的某个函数f(n)(3)取f(n)数量级并用符号O表示。【教师】讲解实例1-6、1-7,1-8(详见教材)，并要求学生完成实例19(详见教材)【教师】通过多媒体展示“常见的时间复杂度”表格(详见教材)，介绍常见的时间复杂度及统称2.算法的空间复杂度算法的空间复杂度(spacecomplexity)就是指程序运行所需的存储空间，记作S(n)=O(f(n),该函数各参数的含义与时间复杂度相同。由于程序本身所用指令等所占存储空间与算法无关，因此，分析算法的空间复杂度时，只需分析算法在实现时所需要的辅助存储空间即可。【教师】讲解实例IrO(详见教材)，并演示分析过程【提示】对于某个

10、特定的算法，其时间复杂度和空间复杂度往往是相互影响的。通常情况下，运算空间较为充足，因此，往往仅以算法的时间复杂度作为算法性能评价的重要指标。【学生】聆听、思考、理解、记录任务实施任务将百分制成绩转换为五级制成绩【教师】描述问题，安排学生扫描微课二维码观看视频”将百分制成绩转换为五级制成绩”(详见教材)，要求学生设计算法【问题描述】通过键盘输入百分制成绩，设计算法将其转换为五级制成绩并输出.【问题分析】对于输入的百分制成绩，只需利用条件语句依次进行判断，然后根据表1-4进行转换即可。第一种算法可以根据分数从低到高依次进行判断,流程图如下：/输入SCOre/输出“E”/N/Itscore/输出“

11、D”/A/输出C/-sreI/输出B/输出“A”/使用算法一时，70分以上的成绩(总占比80%)须进行3次或3次以上的判断才能得出结果。那么，怎样才能减少判断次数，从而提高效率呢？为此，可以将百分制成绩范围按照占比大小排序，并将具有较大占比的成绩范围排在前面，分别将输入的成绩与之进行比较。可以将算法一进行改进得到算法二，其流程图如下：/输入S8re/I70=scorei-1/输出C”/Zj80=scorei/输出“B“/输出【D/输出A/输出“E”/【代码实现】根据算法二，写出Python源程序。（详见教材）【学生】自行扫码观看配套微课，按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题实操练习【教师】组织学生完成以下任务，并随机邀请学生分享设计一个算法，在屏幕上打印九九乘法表。【学生】聆听要求、完成任务、分享课堂小结【教师】简要总结本节课的要点算法的定义和特性算法的描述方法算法的设计要求算法分析【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的剩余练习。【学生】完成课后任务教学反思