算法和算法的描述资料.pptx

高二年级信息技术学科（选修1）广东教育出版社东平明湖中学 董爱平 第一章第二节 课题：算法和算法的描述东平明湖中学东平明湖中学复 习计算机解决问题的过程计算机解决问题的过程东平明湖中学东平明湖中学课下自主预习（学案）课下自主预习（学案）东平明湖中学东平明湖中学 激发学习热情，培养合作意识和进取精神，初步形成严谨的逻辑思维习惯。理解算法的概念及特征；用自然语言、流程图等方法描述算法的过程；通过问题分析，选择适当的算法描述工具进行算法探究活动。知识与技能情感态度与价值观过程与方法一一教教 学学 目目 标标东平明湖中学东平明湖中学教学重点教学重点 算法的特征以及经历用自然语言、流程图等方法描述算法的过程。教学重点教学重点 教学重点教学重点教学难点教学难点 算法的特征以及流程图描述算法。教学难点教学难点二二重重 点点 难难 点点二二东平明湖中学东平明湖中学（环节一）情境引入狼羊菜过河游戏有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？要求：请设计一个方案,把3样东西安然无恙的带过河。东平明湖中学东平明湖中学1这个方案总共有多少步？这个方案总共有多少步？2农夫过河问题解决了，那到底什么是算法？农夫过河问题解决了，那到底什么是算法？合作探究一：合作探究一：总结算法的定义总结算法的定义东平明湖中学东平明湖中学 过河方案过河方案第一步：将羊运过去第二步：人返回第三步：将菜运过去第四步：将羊运过来第五步：将狼运过去第六步：人返回第七步：将羊运过来东平明湖中学东平明湖中学 算法是在有限步骤内有限步骤内求解某一问题所使用的一组定义定义明确明确的规则。通俗地说，算法就是求解某一问题的方法，是能被机械地执行的动作或指令的集合。算法就是解决问题的方法和步骤方法和步骤（环节二）学习新知有穷性有穷性 确定性确定性东平明湖中学东平明湖中学历史上的经典算法！辗辗转转相相除除法法合作探究二：算法的特征设给定的两个正整数设给定的两个正整数m=112,n=64，求它们的，求它们的最大公约数和最小公倍最大公约数和最小公倍数是多少？数是多少？数数 学学 问问 题题东平明湖中学东平明湖中学最小公倍数：两个正整数的乘积除以最大公约数 设给定的两个正整数为m和n，求它们的最大公约数的步骤为：（1）以m除以n，令所得的余数为r。（2）若r=0，则输出结果n，算法结束；否则，继续步骤（3）。（3）令m=n，n=r，并返回步骤（1）继续进行。欧几里得辗转相除法东平明湖中学东平明湖中学 利用辗转相除法求最大公约数和最利用辗转相除法求最大公约数和最小公倍数小公倍数P9(P9(实践一和实践二实践一和实践二)试试 一一 试试总结算法的特征总结算法的特征东平明湖中学东平明湖中学（1）输输 入。入。一个算法有零零个(算法本身给了一个初始值)或多多个输入。（2）确定性确定性。算法的每一个步骤必须要确切地定义确切地定义。（3）有穷性有穷性。一个算法的计算步骤是有限有限的。（4）输输 出出。算法有一一个或多多个输出。学业水平考试学业水平考试考点（5）能行性能行性。计算机解决问题能不能精确地进行。东平明湖中学东平明湖中学1、这个人好说话。课课 堂堂 检检 测：测：2、S1:sum=0 S2:I=1 S3:sum=sum+I S4:I=I+1 S5:若sum=0，返回s3;否则，算法结束。违反了算法的（）特征东平明湖中学东平明湖中学 3、算法要有一个清晰的起始步清晰的起始步，表示处理问题的起点，且每一个步骤只能有一个确定的只能有一个确定的后继步骤()，从而组成一个步骤的有限有限序列()；要有一个一个终止步终止步(序列的终止)表示问题得到解决或不能得到解决；每条规则必须是确定的、可行的(3 )、不能存在二义性。算法总是对数据进行加工处理，因此，算法的执行过程中通常要有数据4 4输入输入()和数据5 5输出输出（）的步骤。算法的算法的确定性确定性算法的有算法的有穷性性穷性性算法的可算法的可行性行性0个或多个或多个个至少一个至少一个东平明湖中学东平明湖中学1在在【辗转相除法辗转相除法】中，我们是用什么来描述算法的？中，我们是用什么来描述算法的？2算法还有其他的描述方法吗？算法还有其他的描述方法吗？合作探究三：算法的描述东平明湖中学东平明湖中学自自 然然 语语 言言、流程图流程图1、用自然语言描述算法，就是把算法的各个步骤，、用自然语言描述算法，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。依次用人们熟悉的自然语言表示出来。2、也称为程序框图，它是算法的一种图形化表示方法。东平明湖中学东平明湖中学 3、伪代码是介于自然语言和计算机程序语言之间、伪代码是介于自然语言和计算机程序语言之间的文字、符号来描述算法的方法。的文字、符号来描述算法的方法。伪代码伪代码东平明湖中学东平明湖中学三种方法描述辗转相除法：三种方法描述辗转相除法：给定两个正整数m和n；以m除以n，令所得的余数为r；若r=0，则输出结果n，算法结束；否则，继续步骤；令m=n，n=r，并返回步骤继续进行。欧几里得辗转相除法：INPUT m,nr=m mod nDo While r0 m=n n=r r=m mod nLoopPrint n东平明湖中学东平明湖中学交换两个杯子中的液体交换两个杯子中的液体AB提问同学，如何处理？提问同学，如何处理？将杯子将杯子A中的液体倒给杯子中的液体倒给杯子C；将杯子将杯子B中的液体倒给杯子中的液体倒给杯子A；将杯子将杯子C中的液体倒给杯子中的液体倒给杯子B。C引入一个空杯子引入一个空杯子东平明湖中学东平明湖中学开始开始A-CB-AC-B输出输出A,B结束结束交换两个杯子中的液体交换两个杯子中的液体东平明湖中学东平明湖中学三种描述方法的优点与缺三种描述方法的优点与缺 点点自然语言描述 流程图描述直观清晰确定性繁琐程度是否容易修改通俗易懂不不 能能 被被 计计 算算 机机 识识 别别东平明湖中学东平明湖中学用伪代码描述算法优点：书写方便，格式紧凑，易于理解，便于向计算机 程序设计语言过度。缺点：由于语言的种类繁多，伪代码的语句不容易规范。优优 点点 与与 缺缺 点点东平明湖中学东平明湖中学（环节三）巩固练习（环节三）巩固练习1、关于算法的描述，下列选项中正确的是（）A、一个算法的执行步骤可以是无限的 B、一个算法可以没有输入 C、一个算法，当没有输入时，也没有输出 D、算法只能用流程图来表示B学业水平考试题学业水平考试题东平明湖中学东平明湖中学2、下列关于算法的描述错误是（）。A、一个有效的算法至少要有一个或多个输入B、算法是解决某一类问题的方法和步骤C、算法必须在有限步骤内实现D、算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述学业水平考试题学业水平考试题A东平明湖中学东平明湖中学 如图所示的算法流程图，执行情况如下：如图所示的算法流程图，执行情况如下：当输入当输入a,b的值分别为的值分别为3，8时，输出结果为时，输出结果为5当输入当输入a,b的值分别为的值分别为11，7时，输出结果为时，输出结果为43、分析解答问题（学业水平考试题）、分析解答问题（学业水平考试题）问题：依据问题所选流程图，当输入a,b的值分别为9，6时，输出结果为（）学业水平考试题学业水平考试题C=abs(a-b)东平明湖中学东平明湖中学 1、已知圆半径，求面积（用流程图描已知圆半径，求面积（用流程图描述算法）述算法）（环节四）：课下作业（环节四）：课下作业2、预习第三节程序与程序、预习第三节程序与程序设计语言（学案）设计语言（学案）东平明湖中学东平明湖中学（环节五）课堂小结输入输入 确定性确定性 有穷性有穷性 有输出有输出 可行性可行性 算法的描述算法的描述用自然语言描述算法用流程图描述算法用伪代码描述算法算法算法和算和算法的法的描述描述概念：概念：考点考点解决问题的方法和步骤特征：特征：东平明湖中学东平明湖中学制作单位：东平明湖中学制作单位：东平明湖中学时间：2016年4月东平明湖中学东平明湖中学人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自有黄金屋。书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，给我们巨大的精神力量，鼓舞我们前进鼓舞我们前进。东平明湖中学东平明湖中学