高一信息技术(人教中图版)算法概念与描述(第八课时)-ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,算法概念与描述,（第,八,课时）,年 级：高一 学 科：信息技术（人教,/,中图版）,算法概念与描述（第八课时）年 级：高一,1,地铁,1,号线,情境描述,小明到北京旅游，他乘坐火车到达了北京站，然后准备乘坐地铁去天安门参观，地铁线路图如下图所示，你能帮小明规划好路线吗？是否只有一条路线？请大家思考这个问题。,地铁1号线情境描述小明到北京旅游，他乘坐火车到达了北京站，然,路线,1,：乘坐地铁,2,号线，从北京站到建国门站，在建国门站换乘,1,号线，在天安门东站下车。,地铁,1,号线,路线,1,：共乘坐,4,站，换乘,1,次。,情境描述,路线1：乘坐地铁2号线，从北京站到建国门站，在建国门站换乘1,路线,2,：乘坐地铁,2,号线，从北京站到崇文门站，在崇文门站换乘,5,号线，到东单站，在东单站换乘,1,号线，在天安门东站下车。,地铁,1,号线,路线,2,：共乘坐,4,站，换乘,2,次。,情境描述,路线2：乘坐地铁2号线，从北京站到崇文门站，在崇文门站换乘5,地铁,1,号线,地铁,1,号线,情境描述,寻找路线的方法，可以称之为算法,地铁1号线地铁1号线情境描述寻找路线的方法，可以称之为算法,当你想要从北京去上海迪士尼旅游，你会如何规划行程呢？,算法的概念,广义上讲，算法是解决一个特定问题而采取的确定的、有限的步骤。,当你想要从北京去上海迪士尼旅游，你会如何规划行程呢？算法的概,网上购买迪士尼门票；,根据日期，购买火车票或者飞机票；,根据行程及日期安排，预订住宿酒店；,带好各种票据，准备好行李，按时乘车；,到达上海，乘坐出租车或公共交通车辆去往酒店入住，放行李；,带好门票，按时到迪士尼游玩。,解决同一个问题的算法可能有多种。,算法就是在解决特定问题时，采取的确定的、有限的步骤。,算法的概念,其他方案,网上购买迪士尼门票；解决同一个问题的算法可能有多种。算法,分析解决以下三个问题的算法，归纳算法的特征。,算法的特征,分析解决以下三个问题的算法，归纳算法的特征。算法的特征,分析项目,抛物线,执行的步骤个数,每一步是否明确可执行,是否有输入,是否有输出,4,是,否,是,算法的特征,分析项目抛物线执行的步骤个数每一步是否明确可执行是否有输,分析项目,抛物线,分段函数,绝对值,执行的步骤个数,4,每一步是否明确可执行,是,是否有输入,无,是否有输出,有,算法的特征,分析项目抛物线分段函数绝对值执行的步骤个数4每一步是否,分析项目,抛物线,分段函数,绝对值,执行的步骤个数,4,5,4,每一步是否明确可执行,是,是,是,是否有输入,无,有,有,是否有输出,有,有,有,算法的特征,分析项目抛物线分段函数绝对值执行的步骤个数454每一步,在计算机领域，算法作为一个精心设计的运算序列，描述了计算机如何将输入转化为输出的过程。算法一般具有如下特征：,算法的特征,算法的特征,有输入,一个算法通常要求有,0,个或多个输入。,有输出,一个算法可以有一个或多个输出。,有穷性,算法必须能在有限个步骤之后终止。,可行性,算法中的每一步都是可以执行的。,确定性,算法的每个步骤都具有确定的含义，没有歧义。,在计算机领域，算法作为一个精心设计的运算序列，描述了计算机,算法已经广泛应用于各领域中，不只是解决数学问题。例如，如何在图书管理系统中查找需要的书籍？解决该问题的过程也是算法吗？符合算法的五个特征吗？,算法的特征,算法已经广泛应用于各领域中，不只是解决数学问题。例如，如何,自然语言,小明在去往地铁站时，在路口遇到了一个红绿灯。小明发现该红绿灯上配有一个倒计时器，倒计时,15,秒之后红灯变成了绿灯，如何将“,倒计时,15,秒,”的算法描述出来？,算法的描述方法,自然语言小明在去往地铁站时，在路口遇到了一个红绿灯。小明发现,自然语言,将计数器,t,（剩余秒数）设为,15,；,如果,t,大于等于,1,，执行步骤，否则执行步骤；,显示,t,，并保持显示,1,秒，然后清除显示；,将,t,的值减,1,，跳转至步骤。,倒计时结束。,倒计时,15,秒？,自然语言,歧义,易于理解,自然语言将计数器t（剩余秒数）设为15；倒计时15秒？自然,流程图是用图形表示算法的一种常用工具。用流程图描述的算法直观易读，问题解决的步骤清晰简洁，算法结构表达明确。,开始,/,结束框,输入,/,输出框,处理框,判断框,流程线,流程图,流程图是用图形表示算法的一种常用工具。用流程图描述的算法直观,流程图符号,名称,功能,开始,/,结束框,表示算法的开始或结束,输入,/,输出框,表示输入或输出数据,处理框,框中指出要处理的内容，此框有一个入口和一个出口,判断框,用于表示条件判断及产生分支的情况，判断框有四个顶点，通常上面的顶点表示入口,流程线,用于控制流程方向,流程图,流程图符号名称功能开始/结束框表示算法的开始或结束输入/输出,操作时，我们可以在纸上手工绘制流程图，也可以使用工具软件或者到特定的网站进行绘制。,文稿处理软件,流程图绘制软件,在线绘制流程图网站,流程图,操作时，我们可以在纸上手工绘制流程图，也可以使用工具软件或者,结束,t,15,t,1,输出,t,t,t-1,True,False,保持显示,1,秒,清除显示,倒计时,15,秒？,将计数器,t,设为,15,；,如果,t,大于等于,1,，执行步骤，否则执行步骤；,显示,t,，并保持显示,1,秒，然后清除显示；,将,t,的值减,1,，跳转至步骤。,倒计时结束。,流程图,开始,结束t 15t 1输出tt t-1TrueFal,循环结构,顺序结构,选择结构,三种基本结构,结束,t,15,t,1,输出,t,t,t-1,True,False,保持显示,1,秒,清除显示,开始,循环结构顺序结构选择结构三种基本结构结束t 15t,S1,Sn,顺序结构,False,True,S1,S2,C,选择结构,三种基本结构,S1,C,False,True,循环结构,S1Sn 顺序结构FalseTrue S1S2C选择结,注意区分,选择和循环,三种基本结构,False,True,S1,S2,C,选择结构,S1,C,False,True,循环结构,注意区分三种基本结构FalseTrue S1S2C选择结构S,伪代码,t,15,while t,1,output 1,sleep 1s,clear,t,t-1,end while,规避了程序设计语言严格的书写格式，无歧义，结构性强。,不太适合完全没有程序设计基础的初学者。,倒计时,15,秒？,伪代码,伪代码t 15规避了程序设计语言严格的书写格式，无歧义，,算法的描述方法,算法的描述方法,自然语言,伪代码,流程图,自然语言就是使用日常所用的语言描述算法的步骤。,优点：使用简单，易于理解。,缺点：容易产生二义性。,流程图是用图形表示算法的一种常用工具。,优点：步骤清晰简洁，算法结构表达明确，适合初学者使用。,缺点：绘制过程繁琐，对于复杂问题，结构过于复杂，不易理解。,伪代码是采用一种类似程序设计语言的代码来描述算法。,优点：回避了程序设计语言严格的书写格式，叙述准确，无二义性，结构性强。,缺点：需要具备一定的程序设计语言基础，不利于初学者使用。,算法的描述方法算法的描述方法自然语言伪代码流程图自然语言就是,某地有两种不同类型的出租车，其计费标准分别为：甲车,3,千米起步，价格,10,元，,3,千米以上（含,3,千米）每千米为,2,元；乙车,3,千米起步，价格,8,元，,3,千米以上（含,3,千米）每千米,2.2,元。,设计算法，在不同里程时给出,最优资费的用车选择,。选用一种,描述方法,对该算法进行描述，并解释其中使用到的,基本结构,。,实践练习,某地有两种不同类型的出租车，其计费标准分别为：甲车3千米起步,结构？,实践练习,p1,甲车的起步价,p2,乙车的起步价,x1,甲车起步里程后，每千米的费用,x2,乙车起步里程后，每千米的费用,n,计划行使的里程数,p1,p2,x1,x2,n,n,3,甲车省钱,p1p2,False,True,乙车省钱,两车相同,False,结束,结构？实践练习p1甲车的起步价p1,p2,x1,x2,nn,算法的描述方法,顺序结构,选择结构,p1,p2,x1,x2,n,n,3,甲车省钱,p1p2,False,True,乙车省钱,两车相同,False,结束,在实际问题解决中，经常会将三种控制结构综合使用。,算法的描述方法顺序结构选择结构p1,p2,x1,x2,nn,已知有,10,个一模一样的零件，其中,9,个零件的质量相同，只有一个质量略轻，不符合规格要求。现在有一台天平，请设计算法找出该零件。,算法效率,一一比较？,次数？,其他方法？,15,次,二分法,23,次,已知有10个一模一样的零件，其中9个零件的质量相同，只有一个,如果有,n,个零件（,n,10,），要找出其中质量较轻的一个零件，以上方法是否仍然可用？试分析,n=10000,时，这些算法在问题解决效率上的不同。,算法效率,一一比较,二分法,15000,次,513,次,效率更高,在解决问题时，可根据问题规模，选择合适算法,如果有n个零件（n10），要找出其中质量较轻的一个零件，以,地铁,1,号线,乘坐地铁问题,迪士尼旅游问题,零件问题,在实际解决问题的过程中，应综合考虑问题类型、问题规模、适用范围等因素，选择合适算法。,算法效率,地铁1号线乘坐地铁问题迪士尼旅游问题零件问题在实际解决问题的,小结,算法概念和描述,算法的概念,算法的特征,算法的效率,算法的描述方法,有输入,有输出,确定性,有穷性,可行性,一个算法通常要求有,0,个或多个输入。,一个算法可以有一个或多个输出。,算法必须能在有限个步骤之后终止。,算法中的每一步都是可以执行的。,算法的每个步骤都具有确定的含义。,自然语言,流程图,伪代码,用日常所用语言来描述算法的步骤。,流程图是用图形表示算法的一种常用工具。,采用一种类似程序设计语言的代码来描述算法。,算法就是解决一个特定问题而采取的确定的，有限的步骤。,对于同一个问题，不同算法解决问题的效率不同。,小结算法概念和描述算法的概念算法的特征算法的效率算法的描述方,小结,算法概念和描述,算法的概念,算法的特征,算法的效率,算法的描述方法,有输入,有输出,确定性,有穷性,可行性,一个算法通常要求有,0,个或多个输入。,一个算法可以有一个或多个输出。,算法必须能在有限个步骤之后终止。,算法中的每一步都是可以执行的。,算法的每个步骤都具有确定的含义。,自然语言,流程图,伪代码,用日常所用语言来描述算法的步骤。,流程图是用图形表示算法的一种常用工具。,采用一种类似程序设计语言的代码来描述算法。,算法就是解决一个特定问题而采取的确定的，有限的步骤。,对于同一个问题，不同算法解决问题的效率不同。,小结算法概念和描述算法的概念算法的特征算法的效率算法的描述方,算法概念与描述,（第,八,课时）,年 级：高一 学 科：信息技术（人教,/,中图版）,算法概念与描述（第八课时）年 级：高一,33,