2.2-算法的概念及描述【新教材】高一信息技术(共19张PPT)

2.2算法的概念及描述教学目标描述算法的特征，理解算法在问题解决中的作用。选用恰当的描述方法和控制结构表示简单算法，增强用算法解决问题的意识。体验探究规划乘车路线小明同学所在城市的地铁线路局部图，如P47图2.2.2所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1；换乘地铁的用时也都相等,记为t2。思考:1.列举出由A站出发到达B站的所有换乘次数最少的乘车路线。2.如果小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线，并说明理由。2.2.1认识算法在生活和学习中，人们经常会运用到算法(algorithm)知识，只是很少意识到。从广义上讲，算法是为解决一类特定问题而采取的确定的、有限的步骤。它描述出某类问题求解的方法和过程，在整个问题解决过程中起着重要的作用。2.2.1认识算法一个算法一般要求有0个或多个输入,以描述运算对象的初始情况。一个算法可以有一个或多个输出,以反映对输入数据加工后的结果。算法的有穷性指算法必须能在执行有限个步骤之后终止,也就是算法步骤不能是无限的。算法中的每一步操作都是可以执行的,或者都可以分解成计算机可执行的基本操作。算法的每个步骤都具有确定的含义,没有歧义。模糊不清、模棱两可或带有二义性的描述都会影响算法的确定性。有穷性03可行性04有输出02有输入01确定性05算法的特征2.2.2描述算法描述算法就是将解决问题的步骤，用一种可理解的形式表示出来。常用的描述算法的方法有自然语言、流程图和伪代码等。思考活动：描述“红灯变绿灯”问题的算法任务：如何将“倒计时15s”的算法描述出来?2.2.2描述算法用自然语言描述算法自然语言指人们日常所用的语言。用自然语言描述算法就是使用人们能读懂的简短语句对算法的步骤进行描述。其中,“倒计时15s”算法可用自然语言描述为：步骤1:将计数器t设为15步骤2:如果t大于或等于1,执行步骤3,否则倒计时结束步骤3:输出t,并保持显示1s,然后清除显示步骤4:将t的值减1,跳转至步骤2用自然语言描述算法易于理解，它既可以描述生活中的算法，也可以描述在计算机中执行的算法。但是,自然语言的描述方法存在容易产生二义性的缺点，有可能干扰后续的编程实现。2.2.2描述算法用流程图描述算法流程图是一种常用的表示算法的图形化工具。用流程图描述的算法直观易读问题解决的步骤清晰简洁，算法结构表达明确，很适合初学算法的人员使用。绘制流程图的方法很多，可以手工绘制流程图，也可以用软件制作，如使用文本编辑软件中的“流程图”对象绘制，或使用专门的流程图绘制软件，还可以到在线绘制流程图网站进行制作。2.2.2描述算法用流程图描述算法流程图中常用的符号及其功能：2.2.2描述算法用流程图描述算法三种基本控制结构：1顺序结构2选择结构3循环结构2.2.2描述算法用流程图描述算法①顺序结构：每一个步骤按先后次序被执行，即执行处理A，然后执行处理B。2.2.2描述算法用流程图描述算法②选择结构：又称分支结构。根据条件的成立与否，选择执行不同的分支处理。当条件成立时(True)，执行处理A；当条件不成立时(False)，执行处理B。2.2.2描述算法用流程图描述算法③循环结构：当条件成立时，反复执行处理A，一旦条件不成立就立即结束循环。2.2.2描述算法用流程图描述算法“倒计时15s”的流程图：2.2.2描述算法用伪代码描述算法用伪代码描述算法就是采用一种类似于程序设计语言的代码来表示算法。伪代码没有固定的、严格的语法规则，只要定义合理，没有矛盾即可。例如，“倒计时15s”的算法用伪代码可以描述为右图。用伪代码描述算法回避了程序设计语言严格的书写格式，保持了语言叙述准确、无二义性的优点，结构性强，比较容易书写和理解。2.2.2描述算法实践活动：找出质量较轻的零件已知有10个一模一样的零件，其中9个零件的质量相同，只有1个质量略轻，不符合规格要求。现在有一台天平，请设计算法找出该零件。任务：1.如果采用一一比较的方法，逐一称重对比，最多需要比较多少次才能找出这个质量较轻的零件？试着描述该算法，想一想还有哪些方法可以解决该问题？2.如果有n个零件(n10)，要找出其中质量较轻的一个，以上方法是否仍然可用？试分析m=10000时，这些算法在问题解决效率上的不同。练习提升1.小明早上从起床到出门上学需要洗漱(5min)、烧水(10min)、准备早餐(10min)、吃早餐(15min)和听新闻(10min)，试帮他统筹安排各项事务，设计一个合理的算法步骤。2.某地有两种不同类型的出租车,其计费标准分别为：●甲车3km起步，价格为10元，3km以上(含3km)为2元/km;●乙车3km起步，价格为8元，3km以上(含3km)为22元/km设计算法，在不同里程时给出最优资费的用车选择。选用一种算法描述方法对该算法进行描述。练习提升3.欧几里得算法又名辗转相除法，其算法可用P54图22.5所示的流程图描述(“%”为取模运算符，可返回除法的余数)，认真阅读流程图，分析该算法实现的功能。谢谢！