资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高中,信息技术基础,（必修）,算法及其实现,高中信息技术基础（必修）算法及其实现,在小品,钟点工,中，宋丹丹讲了这样一个笑话：说要把大象装冰箱，一共分几步？,第一步 先把冰箱门打开,第二步 把大象放进去,第三步 把冰箱门关上,在小品钟点工中，宋丹丹讲了这样一个笑话：说要把大象装冰箱,1,、算法的定义：,所谓“算法”（,algorithm,）就是解题方法的精确描述。,“算法”的含义十分广泛，并不是只有“计算”的问题才有算法。,1.,一元二次方程,ax,2,+bx+c=0,的解法是算法。,2.,乐谱是乐队演奏的算法，菜谱是厨师做菜的算法。,3.,计算机的操作步骤等都是算法。,1、算法的定义：所谓“算法”（algorithm）,有两个瓶子,A,和,B,，,A,瓶装有雪碧，,B,瓶是可乐，问如何把雪碧和可乐互换。即,A,瓶原来雪碧，现改为盛可乐，,B,瓶则相反。,第一步 准备好一个空瓶子,C,第二步 把,A,瓶里的雪碧倒入瓶子,C,中,第三步 把,B,瓶里的可乐倒入,A,瓶中,第四步 把,C,瓶里的雪碧倒入,B,瓶,有两个瓶子A和B，A瓶装有雪碧，B瓶是可乐，问如何把雪碧和,2,、算法的特点,:,算法的特点是求解步骤必须是,有限的,而且每个环节都必须是,明确,和,可行的,。,（,1,）有穷性,（,2,）确定性,（,3,）可执行性,2、算法的特点:算法的特点是求解步骤必,问：,如何判断一个算法的好坏,？,对同一问题，可以有不同的解题方法和步骤。,问：如何判断一个算法的好坏？对同一问题，可以有不同的解题方法,数学家华罗庚的,统筹方法,中著名的,”,泡茶算法,”,：,灌凉水,洗茶壶,拿茶叶,泡茶喝,洗茶杯,洗开,水壶,烧开水,灌凉水,洗茶壶,拿茶叶,泡茶喝,洗茶杯,洗开,水壶,烧开水,灌凉水,洗茶壶,拿茶叶,泡茶喝,洗茶杯,洗开,水壶,烧开水,方法甲,方法丙,方法乙,t,(,请同学们对这几种算法进行评价,!),结论：算法有优劣。处理问题时算法应择优。,数学家华罗庚的统筹方法中著名的”泡茶算,算法的表示：,为了表示一个算法，常用的算法表示形式有：,自然语言、流程图,和,计算机语言,。,常用的计算机语言有：,C,、,C+,、,Basic,、,VB,和,java,等。,算法的表示：常用的计算机语言有,自然语言表示法,自然语言就是人们日常使用的语言,可以是汉语、英语或数学语言等,.,用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解,.,缺点是通常所用文字会比较冗长，还容易出现“歧义性”,.,歧义性语句：,1,）爸爸看见我不高兴。,2,）开刀的是他父亲。,3,）一边站着一位同学，守卫着校门。,自然语言表示法 自然语言就是人们日常使用的,流程图,是人们经常用来描述算法的工具，流程图用图框及流程线来表示算法形象直观。美国国家标准化协会（,ANSI,）规定了流程图符号。,1.,处理框（）：框中指出要处理的内容，有出口和入口。,2.,输入、输出框（）：表示输入和输出数据。,3.,判断框（）：表示条件判断及产生分支的情况。,4.,连接框（）：连接因页面写不下而断开的流程线。,5.,流程线（）：有向线段，控制流程方向。,6.,开始、结束框（）：表示本段算法的开始或结束。,流程图是人们经常用来描述算法的工具，流程图用图框及流程线来表,例,1,：要设计一个算法，对任意输入的三个整数,x,、,y,和,z,，找出并输出其中的最大值。,按照它的思想，我们只需要先比较,x,和,y,，得到一个较大的值,max,，再用,max,与,z,比较，将两者中较大的值作为结果输出即可。,例1：要设计一个算法，对任意输入的三个整数x、y和z，找出并,用自然语言，可以将这个算法描述为：,（,1,）输入变量,x,、,y,和,z,的值。,（,2,）比较,x,和,y,。如果,xy,，则,x,存入以,max,命名的存储单元中；否则，,y,送,max,。,（,3,）比较,z,和,max,。如果,zmax,，则,z,送,max,。,（,4,）输出结果,max,。,这个算法也可以用下面的流程图来描述。图中的,Y,表示,Yes,，,N,表示,No,。,用自然语言，可以将这个算法描述为：,开始,输入变量,x,、,y,和,z,的值,x y,z max,max x,max y,max z,输出变量,max,的值,结束,图框内的符号,“,”,是赋值号，表示将赋值号右边的表达式运算的结果值存入左边的变量。例如，,“,max x,”,、,i i+1,Y,N,开始输入变量x、y和z的值x yz maxmax,计算机语言：,Input x,y,z,IF xy then,max=x,Else max=y,End if,If zmax then,max=z,End if,Print max,End,计算机语言：,程序的基本控制结构,执行,a,执行,b,（,a,）顺序结构,条件,执行,a,执行,b,Y,N,（,b,）选择结构,分支结构,执行,a,条件,执行,b,Y,N,（,c,）循环结构,程序的基本控制结构执行a执行b（a）顺序结构条件执行a执行b,练习,1:,画出,“,我们走路时躲避障碍,”,这个过程的流程图,Y,N,有障碍吗,?,往前直走,开始,结束,躲避障碍,分支结构,选择结构,观察道路情况,练习1:画出“我们走路时躲避障碍”这个过程的流程图YN有障碍,练习,2,在抽屉中寻找东西的过程。,N,Y,寻找,开始,结束,找到了吗,?,拿东西,循环结构,练习2在抽屉中寻找东西的过程。NY寻找开始结束找到了吗?拿,分支结构和循环结构的异同,:,Y,N,条件,?,执行,a,执行,b,开始,结束,开始,Y,N,执行,a,条件,?,执行,b,开始,分支结构和循环结构的异同:YN条件?执行a执行b开始结束开始,计算机语言。程序三种基本结构：,（,1,）顺序结构；,（,2,）分支结构,:,又称选择结构,（,3,）循环结构,（,1,）顺序结构,:,语句按先后次序依次执行。,例,1,：把华氏温度值转换成摄氏温度值。,Input f,C=(f-32)*5/9,PRINT C,END,注意：在计算机程序设计语言中，乘号一般用“*”号表示，除号一般用“,/”,表示。在,QBASIC,中，赋值号为“,=”,。,计算机语言。程序三种基本结构：（1）顺序结构；（1）顺序,（,2,）分支结构,:,又称选择结构，根据条件判断其是否成立，从而选择执行不同的程序语句。,If,条件,then,语句,End if,if,条件,then,语句,1,else,语句,2,End if,例,2,比较两个同学的身高，输出较高的那个同学的身高值。,Input a,b,If ab then,max=a,Else,max=b,End if,Print max,End,开始,输入变量,a,和,b,的值,ab?,max,a,max,b,输出变量,max,的值,结束,Y,N,（2）分支结构:又称选择结构，根据条件判断其是否成立，从而选,（,3,）循环结构,:,根据条件判断是否成立，决定程序是否重复执行。,WHILE,条件,语句,WEND,例,3,求,n,阶乘（,n,！,=123,n),开始,输入变量,n,的值,f,1 i1,in?,f,f*i ii+1,输出变量,f,的值,结束,Y,N,Input n,f=1,i=1,While i 0?,Y,2,Y,Y+2,A.,循环结构,B.,树型结构,C.,分支结构,D.,顺序结构,C,2.下图所示的流程图片断所属的结构是()X0?,A.A=5,B=A,A=A+B,B.IF XK THEN,PRINT“BIG”,END IF,C.S=0,WHILE IK THENC.S=0D.,4.,如图所示的流程图片断,:,A,20:B30,C,A:AB:BC,该流程图执行过后,A.B,的值分别为,(),A.A=20,B=30 B.A=20,B=20,C.A=30,B=30 D.A=30,B=20,D,4.如图所示的流程图片断:A20:B30CA:AB:,5.,如下图所示的流程图片断,:,s,0,t,0,t=3?,t,t+1,s,s+t,Y,N,该流程图中循环部分结束后,变量,s,的值是,(),t,的值是,(),10,4,5.如下图所示的流程图片断:s0t0t=b?,C,a-b,（,1,）,输出,c,结束,Y,N,A.,c,b-a,B.,输出,a,C.,c,a+b,D.,ab?,A,6.如图所示的是描述问题“判断两个数大小，计算并输出它们的差,
展开阅读全文