届总复习-走向清华北大--51算法复数.ppt

第十一模块 算法初步 数系的扩充与复数的引入 第五十一讲 算法与程序框图基本算法语句,回归课本,1.算法概念 算法通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成. 注意:算法与一般意义上具体问题的解法既有区别又有联系,它们之间是一般和特殊的关系,算法一方面具有具体化程序化机械化的特点,同时又有高度抽象性概括性精确性的特点,所以算法在解决问题中更具条理性逻辑性.,2.程序框图的概念表示及功能 (1)程序框图又称流程图,是一种用规定的图形流程线及文字说明来准确直观地表示算法的图形.,(2)程序框图基本图形及功能:,注意:画程序框图的规则:使用标准的框图的符号;框图一般按从上到下,从左到右的方向画;除判断框外,大多数流程图符号只有一个进入点和一个退出点,而判断框是具有超过一个退出点的唯一符号;在图形符号内描述的语言要非常简练清楚.,3.算法的逻辑结构 算法的三种基本逻辑结构是顺序结构条件结构和循环结构.其中循环结构又分为当型(WHILE型)循环和直到型(UNTIL型)循环. 注意:顺序结构为最简单的算法结构,语句与语句之间框与框之间按从上至下的顺序进行;条件结构中必含有判断框;循环结构一定包含条件结构.,4.基本算法语句 (1)输入输出语句分别用来实现算法的输入和输出功能.其一般格式为: 输入语句:INPUT“提示内容”;变量. 输出语句:PRINT“提示内容”;表达式. 注意:“提示内容”与变量之间必须用分号“;”隔开,“提示内容”的主要作用是能够让程序运行者更清楚地在计算机屏幕上看到程序指令,以便更方便精确地输入相应的变量值.提示内容也可省略不写.,输入语句可以给多个变量赋值.其格式:INPUT“提示内容1,提示内容2,提示内容3,”;变量1,变量2,变量3,特别注意的是各提示信息之间以及各变量之间必须用逗号“,”隔开. 输出语句可以在计算机屏幕上输出常量变量的值和表达式的值以及系统信息.,(2)赋值语句的功能是给变量赋值,其一般格式是:变量=表达式. 注意:赋值语句一般格式中的“=”不同于等式中的“=”,其实质是先计算“=”右边表达式的值,并将该值赋给“=”左边的变量,若该变量已有值,该值将被当前值覆盖,即变量只取当前表达式的值.,(3)条件语句表达算法中条件结构.其一般格式为: 格式1: IF条件 THEN 语句 END IF,格式2: IF条件 THEN 语句1 ELSE 语句2 END IF,(4)循环语句有两种类型,即当型和直到型,其一般格式是: 格式1: DO 循环体 LOOP UNTIL条件,格式2: WHILE条件 循环体 WEND,5.常用符号 运算符号:加+,减-,乘*,除/,乘方,整除取商/,求余数MOD. 逻辑符号:且AND,或OR,大于,等于=,小于=,小于等于. 常用函数:绝对值ABS,平方根SQR,取整INT.,6.算法案例 (1)辗转相除法 辗转相除法是用于求两数的最大公约数的一种方法,这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法. (2)秦九韶算法 秦九韶算法是我国南宋数学家秦九韶在他的代表作数书九章中提出的一种用于计算多项式的值的方法.,(3)进位制 进位制是人们为了计数和运算方便而约定的记数系统,“满k进一”就是k进制,k进制的基数为k,k进制数是0k-1之间的数字构成的. 注意:(1)k进制化为十进制公式: anan-1a1a0(k)=ankn+an-1kn-1+a1k+a0(其中0aik-1,i=0,1,2,n-1;0ank-1).,(2)十进制化为k进制数用“除k求余法”,即把所给十进制数除以k,得到商和余数,再对商除以k,得到商和余数,以此类推,直到商为0,把各步余数从下到上排列,即得k进制数.,考点陪练,1.任何一个算法都必须有的基本结构是( ) A.顺序结构 B.条件分支结构 C.循环结构 D.三个都有 解析:任何一个算法都不离开顺序结构,它是最简单的逻辑结构. 答案:A,2.条件分支结构不同于顺序结构的明显特征是含有( ) A.处理框 B.判断框 C.起止框 D.输入输出框 解析:由条件分支结构与顺序结构定义可知,条件分支结构有判断框,而顺序结构中无判断框. 答案:B,3.下面的程序框图能判断任意输入的数x的奇偶性.其中判断框内的条件是( ),A.m=0 B.m=1 C.x=0 D.x=1 答案:B,4.用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1,当x=0.4时的值时,需要做乘法和加法的次数分别是( ) A.6,6 B.5,6 C.5,5 D.6,5 解析:f(x)=(3x+4)x+5)x+6)x+7)x+8)x+1, 共需乘法6次,加法6次. 答案:A,5.用辗转相除法求294和84的最大公约数时,需要做除法的次数是( ) A.1 B.2 C.3 D.4 解析:294=843+42,84=422.至此最大公约数便已求出. 答案:B,类型一 算法的设计及算法的顺序结构 解题准备:1.算法必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用. 2.算法过程要简练,而且经过有限步后能得出结果. 3.顺序结果是由若干个依次执行的步骤组成的,这是任何一个算法都离不开的基本结构.顺序结构可以用如图所示的程序框图表示.,【典例1】 已知一球的内接正方体表面积为S,画出求球体积的程序框图. 分析 先求球的半径,再求球的体积;先写出算法,再画出框图.,解 算法: S1 输入S; S2 计算正方体的边长 S3 计算正方体的体对角线长 S4 计算球的体积 S5 输出V.,程序框图:,反思感悟 给出一个问题,设计算法应注意: (1)认真分析问题,联系解决此问题的一般数学方法; (2)综合考虑此类问题中可能涉及的各种情况; (3)将解决问题的过程划分为若干个步骤; (4)用简练的语言将各个步骤表示出来.,探究1 求两底面半径分别为1和4且高为4的圆台的表面积及体积,写出该问题的一个算法,并画出程序框图. 分析 采用顺序结构,并结合圆台的表面积及体积公式按照一定逻辑顺序分步写出.,解 算法设计如下: 第一步:r1=1,r2=4,h=4; 第二步: 第三步:S1=r21,S2=r22,S3=(r1+r2)l; 第四步:S=S1+S2+S3,V= (S1+ +S2)h; 第五步:输出S和V.,该算法的程序框图如图:,反思感悟 不明确圆台表面积,体积公式或逻辑顺序不清. 利用公式求解问题,先写出公式,看公式中的条件是否满足,若不满足先求出需要的量,看要求的量需根据哪些条件求解,需要的条件必须先输入,或将已知条件全部输入,求出未知的量,然后将公式中涉及的量全部代入求值即可.,类型二 算法的条件结构及算法的循环结构 解题准备:1.在一个算法中,经常会遇到一些条件的判断,算法的流程要根据条件是否成立有不同的流向,条件结构就是处理这种过程的结构.,2.常见的条件结构可以用程序框图表示为如图(1)(2)所示的两种形式.,3.根据指定条件决定是否重复执行一条或多条指令的控制结构称为循环结构,反复执行的处理步骤称为循环体.显然,循环结构中有关于条件的判断,这个条件我们称为循环结束条件.因此,循环结构中必包含条件分支结构.,4.常见的循环结构有当型循环和直到型循环,如图(1)(2)所示.,【典例2】 到银行办理个人异地汇款(不超过100万)时,银行要收取一定的手续费.汇款额不超过100元,收取1 元手续费;超过100元但不超过5000元,按汇款额的1%收取;超过5000元,一律收取50元手续.设计算法求汇款额为x元时,银行收取的手续费y元,只画出流程图.,分析 先由题意写出函数解析式,对分段函数,因变量在不同范围内函数的关系式不同,因而当给出一个自变量x的值求它对应的函数值时,应先判断x满足的条件,因此需用条件结构来解决.,解 要计算手续费,首先要建立汇款额与手续费之间的函数关系式,依题意知,流程图如图所示.,反思感悟 不理解“否”的含义,误将第二个判断框中的“x5000”写成“100100”,但“是”与“否”也应相应换位.,探究2 某企业2008年的生产总值为200万元,技术创新后预计以后每年的生产总值将比上一年增加5%,问最早哪一年的生产总值将超过300万元?试写出解决该问题的一个算法,并画出相应的程序框图.,分析 设第n年后该企业生产总值为a, 则a=200(1+0.05)n,此时为2008+n年. 解 算法设计如下: S1 n=0,a=200,r=0.05. S2 T=ar(计算年增量). S3 a=a+T(计算年产量). S4 如果a300,那么n=n+1,重复执行S2; 否则执行S5.,S5 N=2008+n. S6 输出N.,程序框图如下: 解法一: 解法二:,反思感悟 注意直到型循环结构和当型循环结构的本质区别,直到型循环结构先执行a=a+T,再判断a300,若不满足,则执行循环体,直到满足才输出N;而当型循环结构先判断a300,若成立,则执行循环体,直到a300不成立才结束循环,输出N.,类型三 输入输出语句赋值语句 解题准备:1.将表达式所代表的值赋给变量的语句叫做赋值语句.变量指的是计算机内存中的一块区域,用来存储数值,一般用英文字母a,b,c或者单词(中间不能加空格)来表示.在应用变量之前,我们必须事先利用赋值语句,将变量赋为确定的值(这是因为变量在应用之前可能存储着某些值,我们称这个过程为“清零”). 它的一般格式为:变量=表达式,赋值语句中的“=”称作赋值号.,2.在很多算法中,变量需要接受我们从键盘输入的数据,完成这个功能的语句叫做输入语句.在这里我们只研究INPUT输入语句. INPUT输入语句的一般格式是: INPUT“提示内容”;变量.,3.任何求解的算法,都要把求解的结果“输出”来,具有这种功能的语句称为输出语句.在这里只研究常用的输出语句PRINT. PRINT输出语句的一般格式是: PRINT“提示内容”;表达式.,【典例3】 画出程序框图并编写一个程序,求用长度为l的细铁丝分别围成一个正方形和一个圆时所围成的正方形和圆的面积.要求输入l的值,输出正方形和圆的面积(取3.14).,解 程序框图:,程序如下: INPUT“l=”;l S1=(l*l)/16 S2=(l*l)/(4*3.14) PRINT“正方形面积为”;S1 PRINT“圆面积为”;S2 END,反思感悟 注意程序语言中运算符号的书写格式,如:乘号为“*”平方为“2”,除号为“/”,这与平时运算符号有所区别,其运算规则为先乘除,后加减,幂优于乘除,同级运算先左后右,括号内最优先. 编写程序的关键在于搞清问题的算法,特别是算法的结构,然后确定采取哪一种算法语句.本题中要用到相关的平面几何的知识来寻求正方形和圆的面积的计算公式,在此基础上确定利用顺序结构实现算法.,类型四 条件语句和循环语句 解题准备:1.IFTHENELSE格式的条件语句 IFTHENELSE格式的条件语句的一般格式如下: IF 条件THEN 语句序列1 ELSE 语句序列2 END IF,程序框图如图所示:,计算机执行这种格式的条件语句时,如果表达式结果为真,则执行表达式后面的语句序列1;如果表达式结果为假,则执行ELSE后面的语句序列2,然后结束这一条件语句.,2.IFTHEN格式的条件语句 IFTHEN格式的条件语句的一般格式如下: IF 条件 THEN 语句序列1 END IF,程序框图如下图所示:,计算机要执行这种格式的条件语句时,先对表达式的结果进行判断,若表达式结果为真,则执行表达式后面的语句序列1,否则直接跳过语句序列1,执行其他语句.,3.循环语句主要用来处理算法中的循环结构,即处理一些有规律的重复计算问题,如累加求和,累乘求积等问题.循环语句包含两种常见的语句:UNTIL循环语句和WHILE循环语句.,(1)UNTIL循环语句的格式如下: DO 循环体 LOOP UNTIL 条件,UNTIL语句对应的基本框图(直到型)如下图(1).,(2)WHILE循环语句的格式如下: WHILE 条件 循环体 WENDWHILE语句对应的基本框图(当型)如图(2).,4.两个循环含有循环变量终止条件和循环体三个要素,当型循环先判断后执行,直到型循环先执行后判断.,【典例4】 国庆期间,某超市对顾客实行购物优惠活动,规定一次购物付款总额:若不超过200元,则不予优惠;若超过200元,但不超过500元,则按标价价格给予9折优惠;如果超过500元,500元的部分按条优惠,超过500元的部分给予7折优惠,编写一个收款程序. 分析 先根据题意,确定分段函数,再利用条件语句写出程序.,解 依题意,付款总额y与标价x之间的关系式为(单位为元),算法分析: 第一步,输入x值. 第二步,判断,如果x200,则输出x,否则执行第三步. 第三步,判断,如果x500成立,则计算y=0.9x,并输出y,否则执行第四步. 第四步,计算y=0.9500+0.7(x-500),并输出y.,程序框图:,程序: INPUT x IF x=200 THEN PRINT x ELSE IF x=500 THEN y=0.9*x PRINT y ELSE y=0.9*500+0.7*(x-500),PRINT y END IF END IF END,反思感悟 条件语句必须以IF语句开始,以END IF语句结束,一个IF语句必须和一个END IF对应,尤其对条件语句的嵌套编程时,往往漏掉END IF. (1)要区别好条件语句的两种格式:IF-THEN-ELSE格式和IF-THEN格式,理解它们的区别与联系,以及在实际编写程序中各自的特点. (2)求分段函数的函数值往往要用条件语句编写程序,有时还要用到多个条件语句的嵌套,这时为防止漏掉相应的END IF,书写时成对的IF和END IF要上下对齐(内嵌的IF依次往右错开),这样不仅层次清楚,而且形式美观.,探究3 高一(2)班共有54名同学参加数学竞赛,现已有这54名同学的竞赛分数,请设计一个将竞赛成绩优秀同学的平均分输出的算法(规定90分以上为优秀),画出程序框图,并设计程序.,分析 由于涉及到54名同学的分数,因此可以使用循环结构控制输入分数,用条件分支结构来判断分数是否高于90分,同时统计高于90分的成绩的总和和人数,从而求平均分.,解 程序框图:,程序: S=0; M=0; i=1; WHILE i90 S=S+x;,M=M+1; END i=i+1; WEND P=S/M; P,反思感悟 在解决实际问题时,要正确理解其中的算法思想,根据题目写出其关系式,再写出相应的算法.在循环语句中,也可以嵌套条件语句,甚至是循环语句,此时需要注意嵌套这些语句需要保证语句的完整性,否则就会造成无法执行.,类型五 算法语句的实际应用与算法案例的有关计算 解题准备:(1)辗转相除法和更相减损术都是求两个正整数最大公约数的算法,区别在于辗转相除法进行的是除法运算,而更相减损术是减法运算.它们都很方便地在计算机上通过循环语句来实现. (2)秦九韶算法是求多项式值的算法,能方便地在计算机上实现,且运算次数大大减少.,【典例5】 填空: (1)779与209的最大公约数是_. (2)在计算多项式f(x)=5x5+4x4+3x3+2x2+ 在x=5处的值时,用一般算法共进行了_次加法和乘法运算,用秦九韶算法,共进行了_次加法和乘法运算. (3)1011101(2)=_(10) 2008(10)=_(5).,分析 (1)利用辗转相除法或利用更相减损术求最大公约数.(2)根据秦九韶算法列式,数出加法与乘法运算次数.(3)二进制化十进制即将该二进制数展成基数为2的幂的运算,十进制化为五进制即将该十进制数连除以5并求各次余数,将各余数反序排列即为五进制数.,解析 (1)解法一:(辗转相除法) 779=2093+152 209=1521+57 152=572+38 57=381+19 38=192 所以779和209的最大公约数为19.,解法二:(更相减损术) 779-209=570 570-209=361 361-209=152 209-152=57 152-57=95 95-57=38,57-38=19 38-19=19 所以779和209的最大公约数为19.,(2)用一般算法共进行了5+4+3+2+1=15次乘法运算进行了5次加法运算,进行加法和乘法共15+5=20次. 用秦九韶算法:,按从内向外的顺序,依次计算多项式当x=5时的值; v0=5 v1=v0x+4 v2=v1x+3 v3=v2x+2 v4=v3x+ v5=v4x+ 由上式易知:共进行了5次加法和5次乘法运算,共进行了5+5=10次加法和乘法运算.,(3)1011101(2)=126+025+124+123+122+021+120=93 所以1011101(2)=93(10) 所以2008(10)=31013(5) 答案 (1)19 (2)20 10 (3)93 31013,错源一 循环结构中的常见错误分析 【典例1】 下列三图是三位同学为计算22+42+62+1002而绘制的算法程序框图,根据程序框图回答后面的问题.,其中正确的程序框图有哪几个?错误的程序框图有哪几个?错误的要指出错在哪里.,正解 以上三个程序框图都不正确. 图1所示的程序框图中,计数变量是i.22,42,62,1002中,指数都是2,而底数是变化的,相邻两项底数相差2,因此计数变量要加2.,故图1有三处错误: 第一处错误,第二个处理框中的“i=42”应该是“i=4”; 第二处错误,第三个处理框中累加的是“i2”而不是“i”,即p=p+i2; 第三处错误,第四个处理框中内容应是“i=i+2”,而不是“i=i+1”;,图2所示的程序框图中共有四处错误: 第一处错误,流程线没有箭头显示程序的执行顺序; 第二处错误,第三个处理框中的内容应是“p=p+i2”,而不是“p=p+i”; 第三处错误,判断框的流程线没有标明“是”和“否”;,第四处错误,在第三个处理框和判断中漏掉了在循环中起主要作用的框图,内容为i=i+2,否则程序无法退出循环. 图3所示的程序框图中有一处错误,判断框中的循环条件错误,导致无法执行循环体,判断框中的内容应是“i100?”.,错源二 对循环语句中的循环终止条件把握不准,错解 程序如下: S=0 i=1 WHILE i S=S+ i=i+1 END WHILE PRINT S,剖析 此解法的错误就在于循环起始终止条件不正确,实际上,在循环结构中,引入循环变量i,一是为了计数,二是为了控制循环,使程序执行后输出结果与实际结果一致.本题中,循环条件应为i100,一般地,写完一个算法程序后,应执行一遍循环体,检验一下自己的算法是否符合格式要求和题目要求.,正解 程序如下: S=0 i=1 WHILE i100 S=S+ i=i+1 WEND PRINT S END,技法一 三种语句和框图的对应转化 【典例1】 以下是一个用基本算法语句编写的程序,根据程序画出其相应的程序框图.,INPUT“x,y=”;x,y x=x/2 y=3*y PRINT x,y x=x-y y=y-1 PRINT x,y END,解题切入点 该程序主要利用了输入语句赋值语句和输出语句进行算法描述,只要按顺序从上到下将输入语句赋值语句输出语句表达的内容填入相应的图框即可.,解 程序框图如下所示.,技法二 三种语句的理解 【典例2】 写出下列语句描述的算法的输出结果. (1) a=5 b=3 d=c*c PRINT“d=”;d,(2) a=1 b=2 c=a+b b=a+c-b PRINT“a=,b=,c=”;a,b,c,(3) a=10 b=20 c=30 a=b b=c c=a PRINT“a=,b=,c=”;a,b,c,解题切入点 此题主要考查对三种语句的理解,只要对三种语句理解透彻,不难得到答案.,解 (1)a=5,b=3, d=c2=16. (2)a=1,b=2,c=a+b, c=3. 又b=a+c-b, b=1+3-2=2. (3)由b=2