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

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