1、高中高中信息技术基础信息技术基础(必修)(必修)算法及其实现算法及其实现 所谓“算法”(algorithm)就是解题方法的精确描述。“算法算法”的含义十分广泛,并不是只有的含义十分广泛,并不是只有“计算计算”的问题才有算的问题才有算法。法。1.1.一元二次方程一元二次方程axax2 2+bx+c=0+bx+c=0的解法是算法。的解法是算法。2.2.乐谱是乐队演奏的算法,菜谱是厨师做菜的算法。乐谱是乐队演奏的算法,菜谱是厨师做菜的算法。3.3.计算机的操作步骤等都是算法。计算机的操作步骤等都是算法。有两个瓶子A和B,A瓶装有雪碧,B瓶是可乐,问如何把雪碧和可乐互换。即A瓶原来雪碧,现改为盛可乐,
2、B瓶则相反。第一步 准备好一个空瓶子C第二步 把A瓶里的雪碧倒入瓶子C中第三步 把B瓶里的可乐倒入A瓶中第四步 把C瓶里的雪碧倒入B瓶 算法的特点是求解步骤必须是有限的,而且每个环节都必须是明确和可行的。(1)有穷性)有穷性(2)确定性)确定性(3)可执行性)可执行性 数学家华罗庚的统筹方法中著名的”泡泡茶算法茶算法”:灌凉水洗茶壶拿茶叶泡茶喝洗茶杯洗开水壶烧开水灌凉水洗茶壶拿茶叶泡茶喝洗茶杯洗开水壶烧开水灌凉水洗茶壶拿茶叶泡茶喝洗茶杯洗开水壶烧开水方法甲方法丙方法乙t(请同学们对这几种算法进行评价请同学们对这几种算法进行评价!)!)为了表示一个算法,常用的算法表示形式有:。常用的计算机语言有
3、:和等。自然语言表示法自然语言表示法 自然语言就是人们日常使用的语言自然语言就是人们日常使用的语言,可可以是汉语、英语或数学语言等以是汉语、英语或数学语言等.用自然语言用自然语言描述算法的优点是通俗易懂描述算法的优点是通俗易懂,当算法中的操当算法中的操作步骤都是顺序执行时比较容易理解作步骤都是顺序执行时比较容易理解.缺点缺点是通常所用文字会比较冗长,还容易出现是通常所用文字会比较冗长,还容易出现“歧义性歧义性”.歧义性语句:歧义性语句:1)爸爸看见我不高兴。)爸爸看见我不高兴。2)开刀的是他父亲。)开刀的是他父亲。3)一边站着一位同学,守卫着校门。)一边站着一位同学,守卫着校门。流程图流程图是
4、人们经常用来描述算法的工具,流程图用图框及流程线来表示算法形象直观。美国国家标准化协会(ANSI)规定了流程图符号。1.处理框():框中指出要处理的内容,有出口和入口。2.输入、输出框():表示输入和输出数据。3.判断框():表示条件判断及产生分支的情况。4.连接框():连接因页面写不下而断开的流程线。5.流程线():有向线段,控制流程方向。6.开始、结束框():表示本段算法的开始或结束。例1:要设计一个算法,对任意输入的三个整数x、y和z,找出并输出其中的最大值。按照它的思想,我们只需要先比较x和y,得到一个较大的值max,再用max与z比较,将两者中较大的值作为结果输出即可。用自然语言,可
5、以将这个算法描述为:用自然语言,可以将这个算法描述为:(1 1)输入变量)输入变量x x、y y和和z z的值。的值。(2 2)比较)比较x x和和y y。如果。如果xyxy,则,则x x存入以存入以maxmax命名命名的存储单元中;否则,的存储单元中;否则,y y送送maxmax。(3 3)比较)比较z z和和maxmax。如果。如果zmaxzmax,则,则z z送送maxmax。(4 4)输出结果)输出结果maxmax。这个算法也可以用下面的流程图来描述。图这个算法也可以用下面的流程图来描述。图中的中的Y Y表示表示YesYes,N N表示表示NoNo。开始开始输入变量输入变量x、y和和z
6、的值的值x yz maxmax xmax ymax z输出变量输出变量max的值的值结束结束图框内的符号图框内的符号“”是赋值是赋值号,表示将赋号,表示将赋值号右边的表值号右边的表达式运算的结达式运算的结果值存入左边果值存入左边的变量。例如,的变量。例如,“max xmax x”、i i+1i i+1YN计算机语言:Input x,y,zIF xy then max=xElse max=yEnd ifIf zmax then max=zEnd ifPrint maxEnd程序的基本控制结构程序的基本控制结构执行执行a执行执行b(a)顺序结构)顺序结构条件条件执行执行a执行执行bYN(b)选择结
7、构)选择结构 分支结构分支结构执行执行a条件条件执行执行bYN(c)循环结构)循环结构练习1:画出“我们走路时躲避障碍”这个过程的流程图YN有障碍吗?往前直走开始结束躲避障碍分支结构分支结构选择结构选择结构 观察道路情况NY寻找开始结束找到了吗?拿东西分支结构和循环结构的异同:YN条件?执行a执行b开始结束开始YN执行a条件?执行b开始计算机语言。程序三种基本结构:计算机语言。程序三种基本结构:(1)顺序结构;)顺序结构;(2)分支结构)分支结构:又称选择结构又称选择结构 (3)循环结构)循环结构(1)顺序结构)顺序结构:语句按先后次序依次执行。语句按先后次序依次执行。例例1:把华氏温度值转换
8、成摄氏温度值。:把华氏温度值转换成摄氏温度值。Input fC=(f-32)*5/9PRINT CEND注意:在计算机程序设计语言中,乘号一般用注意:在计算机程序设计语言中,乘号一般用“*”号表示,除号一般用号表示,除号一般用“/”表示。在表示。在QBASIC中,赋值号为中,赋值号为“=”。(2)分支结构)分支结构:又称选择结构,根据条件判断其是否又称选择结构,根据条件判断其是否成立,从而选择执行不同的程序语句。成立,从而选择执行不同的程序语句。If 条件条件 then 语句语句 End ifif 条件条件 then 语句语句1 else 语句语句2 End if例例2 比较两个同学的身高,输
9、出较高的那个同学的身高值。比较两个同学的身高,输出较高的那个同学的身高值。Input a,bIf ab then max=aElse max=bEnd ifPrint maxEnd开始开始输入变量输入变量a和和b的值的值ab?maxamaxb输出变量输出变量max的值的值结束结束YN(3)循环结构)循环结构:根据条件判断是否成立,决定程序是否重复执行。根据条件判断是否成立,决定程序是否重复执行。WHILE 条件条件 语句语句 WEND例例3 求求n阶乘(阶乘(n!=123n)开始开始输入变量输入变量n的值的值f1 i1in?ff*i ii+1输出变量输出变量f的值的值结束结束YNInput n
10、f=1i=1While i 0?Y2YY+2 A.循环结构循环结构 B.树型结构树型结构 C.分支结构分支结构 D.顺序结构顺序结构CA.A=5 B=A A=A+BB.IF XK THEN PRINT“BIG”END IFC.S=0 WHILE I=10 J=I*I S=S+J I=I+1 WENDD.IF INT(X/2)=X/2 THEN PRINT“偶数偶数”ELSE PRINT“奇数奇数”END IFC3.下列四段程序中下列四段程序中,主要控制结构属于循环结构的是主要控制结构属于循环结构的是()4.如图所示的流程图片断如图所示的流程图片断:A20:B30CA:AB:BC该流程图执行过后该流程图执行过后,A.B的值分别为的值分别为()A.A=20,B=30 B.A=20,B=20C.A=30,B=30 D.A=30,B=20D5.如下图所示的流程图片断如下图所示的流程图片断:s0t0t=b?Ca-b(1)输出输出c结束结束YNA.cb-aB.输出输出aC.ca+bD.ab?A