高中数学必修3-算法初步

高中数学必修3-算法初步§13.1流程图一、知识导学1.流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序.2．算法的三种基本的逻辑结构：顺序结构、条件结构、循环结构.3．根据对条件的不同处理，循环结构又分为两种：直到型(until型)循环：在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体.满足则停止.如图13-1-3，先执行A框，再判断给定的条件p是否为“假”，若p为“假”，则再执行A，如此反复，直到p为“真”为止.当型（while型）循环：在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环体，不满足则停止.如图13-1-4，当给定的条件p成立（“真”）时，反复执行A框操作，直到条件p为“假”时才停止循环.图13-1-1图13-1-2二、疑难知识1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：（1）有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的.（2）确定性：算法的每一步骤和次序应当是确定的.（3）有效性：算法的每一步骤都必须是有效的.2.画流程图时必须注意以下几方面：（1）使用标准的图形符号.（2）流程图一般按从上到下、从左到右的方向画.（3）除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号.（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果.（5）在图形符号内描述的语言要非常简练清楚.3.算法三种逻辑结构的几点说明：（1）顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.在流程图中的体现就是用流程线自上而下地连接起来，按顺序执行算法步骤.（2）一个条件结构可以有多个判断框.（3）循环结构要在某个条件下终止循环，这就需要条件结构来判断.在循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.三、经典例题[例1]已知三个单元存放了变量x，y，z的值，试给出一个算法，顺次交换x，y，z的值（即y取x的值，z取y的值，x取z的值），并画出流程图.错解：第一步xy第二步yz第三步zx流程图为图13-1-3错因：未理解赋值的含义，由上面的算法使得y，z均取x的值.举一形象的例子：有蓝和黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤完成算法.我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换.正确的解法应为：S1取一只空的墨水瓶，设其为白色；S2将黑墨水瓶中的蓝墨水装入白瓶中；S3将蓝墨水瓶中的黑墨水装入黑瓶中；S4将白瓶中的蓝墨水装入蓝瓶中；S5交换结束.正解：第一步zp｛先将z的值赋给变量p，这时存放z的单元可作它用}第二步yz｛再将y的值赋给z，这时存放y的单元可作它用}第三步xy｛同样将x的值赋给y，这时存放x的单元可作它用}第四步px｛最后将p的值赋给y，三个变量x，y，z的值就完成了交换}流程图为图13-1-4点评：在计算机中，每个变量都分配了一个存储单元，为了达到交换的目的，需要一个单元存放中间变量p.[例2]已知三个数a，b，c.试给出寻找这三个数中最大的一个算法，画出该算法的流程图.解：流程图为图13-1-5点评：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰.若改为求100个数中的最大数或最小数的问题则选择此法较繁琐，可采用假设第一数最大（最小）将第一个数与后面的数依依比较，若后面的数较大（较小），则进行交换，最终第一个数即为最大（最小）值.点评：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构.[例3]画出求222222100994321的值的算法流程图.解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号.思路一：采用-1的奇偶次方（利用循环变量）来解决正负符号问题；图13-1-6图13-1-7思路二：采用选择结构分奇偶项求和；图13-1-8思路三：可先将222222100994321化简成1991173，转化为一个等差数列求和问题，易利用循环结构求出结果.[例4]设计一算法，求使20063212222n成立的最小正整数n的值.解：流程图为图13-1-9点评：这道题仍然是考察求和的循环结构的运用问题，需要强调的是求和语句的表示方法.若将题改为求使20063212222n成立的最大正整数n的值时，则需注意的是输出的值.[例5]任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判断.解：算法为：S1判断n是否等于2，若n=2，则n是质数；若n2，则执行S2S2依次从2～n-1检验是不是的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数.点评：要验证是否为质数首先必须对质数的本质含义作深入分析：（1）质数是只能被1和自身整除的大于1的整数.（2）要判断一个大于1的整数n是否为质数，只要根据定义，用比这个整数小的数去除n.如果它只能被1和本身整除，而不能被其它整数整除，则这个数便是质数.图13-1-10[例6]设计一个求无理数2的近似值的算法.分析：无理数2的近似值可看作是方程022x的正的近似根，因此该算法的实质是设计一个求方程022x的近似根的算法.其基本方法即运用二分法求解方程的近似解.解：设所求近似根与精确解的差的绝对值不超过0.005,算法:S1令2)(2xxf.因为0)2(,0)1(ff,所以设2,121xxS2令2)(21xxm,判断)(mf是否为0,若是,则m为所求;若否,则继续判断)()(1mfxf大于0还是小于0.S3若)()(1mfxf0,则mx1;否则,令mx2.S4判断005.021xx是否成立，若是，则21,xx之间的任意值均为满足条件的近似根；若否，则返回第二步.点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述.四、典型习题1．已知两个单元分别存放了变量A和B的值，则可以实现变量BA,交换的算法是（）.A．S1ABB．S1ACC．S1ACD．S1ACS2BAS2CBS2BAS2BDS3BCS3CB1．下面流程图中的错误是（）图13-1-11A．i没有赋值B．循环结构有错C．S的计算不对D．判断条件不成立3.将“打电话”的过程描述成一个算法，这个算法可表示为，由此说明算法具有下列特性.4.在表示求直线0cbyax（a，b为常数，且a，b不同时为0）的斜率的算法的流程图中，判断框中应填入的内容是5.3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在，画出这个算法的流程图.6.一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩，这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示.§13.2基本算法语句一、知识导学1．赋值语句用符号“←”表示，“yx”表示将y的值赋给x，其中x是一个变量，y是一个与x同类型的变量或表达式.2．条件语句主要有两种形式：“行If语句”和“块If语句”.“行If语句”的一般形式为：IfAThenB[ElseC].一个行If语句必须在一行中写完，其中方括号中的Else部分可以缺省.“块If语句”的一般格式为:IfAThenBElseCEndifThen部分和Else部分是可选的，但块If语句的出口“Endif”不能省.3．循环语句主要有两种类型：For语句和While语句.当循环的次数已经确定，可用“For”语句表示.“For”语句的一般形式为：ForIfrom“初值”tostep“步长”…Endfor上面“For”和“Endfor”之间缩进的步骤称为循环体.当循环次数不能确定是，可用“While”语句来实现循环.“While”语句的一般形式为：WhileA…Endwhile其中A表示判断执行循环的条件.上面“While”和“EndWhile”之间缩进的步骤称为循环体.二、疑难知识1.有的条件语句可以不带“Else”分支，即满足条件时执行B，否则不执行任何操作.条件语句也可以进行嵌套，在进行条件语句的嵌套时，书写要有层次.例如：IfAThenBElseifCThenDElseEEndif2.“For”语句是在执行过程中先操作，后判断.而“While”语句的特点是“前测试”，即先判断，后执行.若初始条件不成立，则一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现.三、经典例题[例1]下列程序的运行结果是.9X8YIfX5Then7YYIfX4Then6YYIfX3Then6YYPrintY错解：8+7=15错因：误认为在一个程序中只执行一个条件语句，与在一个条件语句中只选择其中一个分支相混淆.IfAThenB[ElseC]若满足条件A则执行B，否则是执行C，B和C是这个条件语句的分支，而这个程序省略了Else部分.正解：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27.[例2]下面的伪代码的效果是0iWhilei102iiEndWhileEnd错解：执行10次循环错因：将For语句和While语句混淆.For语句中有步长使循环变量不断变化，而While语句则无.正解：无限循环下去，这是因为这里i始终为0，总能满足条件“10i”，故是一个“死循环”.点评：“死循环”是设计循环结构的大忌，此题可改变i的初始值或每一次循环i都增加一个值.[例3]下面的程序运行时输出的结果是（）1IWhile5I0S1IIIISSEndwhilePrintSEnd错解：第一次循环时，I被赋予2，S被赋予4；第二次循环时，I被赋予3，S被赋予4+23=13；第三次循环时，I被赋予4，S被赋予13+24=29；第四次循环时，I被赋予5，S被赋予545292.由于此时5I，故循环终止，输出S为54.正解：由于0S在循环内，每经过一次循环后S都被赋值0，因此，只要求满足条件的最后一次循环S的值，即当4I时，16440S.[例4]用语句描述求使10007531n成立的最大正整数n的算法过程.解：1n1TWhile1000T2nnnTTEndwhilePrint2n点评：此题易错的是输出值，根据While循环语句的特征当1000T时跳出循环体，此时n的值是1000T时的最小的整数，则使1000T的最大整数应为n的前一个奇数即2n.[例5]已知当100100x时，1xy，当100x时，4y，当100x时，4xy，设计一算法求y的值.解：ReadxIf100100xthen1xyElseif100xThen4xyElse4yEndifEnd点评：嵌套If语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，则需注意一个块If语句对应一个EndIf，不可省略或缺少.[例6]设计一个算法，使得输入一个正整数n，输出1！+2！+3！+…+n！的值.写出伪代码.解：思路一：利用单循环，循环体中必须包括一个求各项阶乘的语句以及一个求和语句.Readn01STForIfrom1tonTSSITTEndForPrintS思路二：运用内外双重循环，但尤其注意的是每一次外循环T的值都要从1开始.Readn