第十三章算法初步§13.1流程图一、知识导学1.流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序.2．算法的三种根本的逻辑构造：顺序构造、条件构造、循环构造.3．根据对条件的不同处理，循环构造又分为两种：直到型(until型)循环：在执行了一次循环体之后，对控制循环条件进展判断，当条件不满足时执行循环体.满足那么停顿.如图13-1-3，先执行A框，再判断给定的条件是否为“假”，假设为“假”，那么再执行A，如此反复，直到为“真”为止.当型（while型）循环：在每次执行循环体前对控制循环条件进展判断，当条件满足时执行循环体，不满足那么停顿.如图13-1-4，当给定的条件成立（“真”）时，反复执行A框操作，直到条件为“假”时才停顿循环.图13-1-1图13-1-2二、疑难知识导析1.“算法“没有一个准确化的定义，教科书只对它作了描述性说明，算法具有如下特点：23/23\n（1）有限性：一个算法的步骤是有限的，必须在有限操作之后停顿，不能是无限的.（2）确定性：算法的每一步骤和次序应当是确定的.（3）有效性：算法的每一步骤都必须是有效的.2.画流程图时必须注意以下几方面：（1）使用标准的图形符号.（2）流程图一般按从上到下、从左到右的方向画.（3）除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号.（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果.（5）在图形符号内描述的语言要非常简练清楚.3.算法三种逻辑构造的几点说明：（1）顺序构造是最简单的算法构造，语句与语句之间，框与框之间是按从上到下的顺序进展的.在流程图中的表达就是用流程线自上而下地连接起来，按顺序执行算法步骤.（2）一个条件构造可以有多个判断框.（3）循环构造要在某个条件下终止循环，这就需要条件构造来判断.在循环构造中都有一个计数变量和累加变量.计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.三、经典例题导讲[例1]已知三个单元存放了变量，，23/23\n的值，试给出一个算法，顺次交换，，的值（即取的值，取的值，取的值），并画出流程图.错解：第一步第二步第三步流程图为图13-1-3错因：未理解赋值的含义，由上面的算法使得，均取的值.举一形象的例子：有蓝和黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤完成算法.我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进展直接交换.正确的解法应为：S1取一只空的墨水瓶，设其为白色；S2将黑墨水瓶中的蓝墨水装入白瓶中；S3将蓝墨水瓶中的黑墨水装入黑瓶中；S4将白瓶中的蓝墨水装入蓝瓶中；S5交换完毕.正解：第一步｛先将的值赋给变量，这时存放的单元可作它用}23/23\n第二步｛再将的值赋给，这时存放的单元可作它用}第三步｛同样将的值赋给，这时存放的单元可作它用}第四步｛最后将的值赋给，三个变量，，的值就完成了交换}流程图为图13-1-4点评：在计算机中，每个变量都分配了一个存储单元，为了到达交换的目的，需要一个单元存放中间变量.[例2]已知三个数，，.试给出寻找这三个数中最大的一个算法，画出该算法的流程图.解：流程图为23/23\n图13-1-5点评：条件构造可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰.假设改为求100个数中的最大数或最小数的问题那么选择此法较繁琐，可采用假设第一数最大（最小）将第一个数与后面的数依依比较，假设后面的数较大（较小），那么进展交换，最终第一个数即为最大（最小）值.点评：求和时根据过程的类同性可用循环构造来实现，而不用顺序构造.[例3]画出求的值的算法流程图.解：这是一个求和问题，可采用循环构造实现设计算法，但要注意奇数项为正号，偶数项为负号.思路一：采用-1的奇偶次方（利用循环变量）来解决正负符号问题；图13-1-6图13-1-7思路二：采用选择构造分奇偶项求和；23/23\n图13-1-8思路三：可先将化简成，转化为一个等差数列求和问题，易利用循环构造求出结果.[例4]设计一算法，求使成立的最小正整数的值.解：流程图为图13-1-9点评23/23\n：这道题仍然是考察求和的循环构造的运用问题，需要强调的是求和语句的表示方法.假设将题改为求使成立的最大正整数的值时，那么需注意的是输出的值.[例5]任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判断.解：算法为：S1判断n是否等于2，假设n=2，那么n是质数；假设n>2，那么执行S2S2依次从2～n-1检验是不是的因数，即整除n的数，假设有这样的数，那么n不是质数；假设没有这样的数，那么n是质数.点评：要验证是否为质数首先必须对质数的本质含义作深入分析：（1）质数是只能被1和自身整除的大于1的整数.（2）要判断一个大于1的整数n是否为质数，只要根据定义，用比这个整数小的数去除n.如果它只能被1和本身整除，而不能被其它整数整除，那么这个数便是质数.23/23\n图13-1-10[例6]设计一个求无理数的近似值的算法.分析：无理数的近似值可看作是方程的正的近似根，因此该算法的实质是设计一个求方程的近似根的算法.其根本方法即运用二分法求解方程的近似解.解：设所求近似根与准确解的差的绝对值不超过0.005,算法:S1令.因为,所以设S2令,判断是否为0,假设是,那么m为所求;假设否,那么继续判断大于0还是小于0.S3假设>0,那么;否那么,令.S4判断是否成立，假设是，那么之间的任意值均为满足条件的近似根；假设否，那么返回第二步.点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述.四、典型习题导练1．已知两个单元分别存放了变量和的值，那么可以实现变量交换的算法是（）.A．S1B．S1C．S1D．S1S2S2S2S2S3S31．下面流程图中的错误是（）23/23\n图13-1-11A．没有赋值 B．循环构造有错C．S的计算不对D．判断条件不成立3.将“打电话”的过程描述成一个算法，这个算法可表示为，由此说明算法具有以下特性.4.在表示求直线（，为常数，且，不同时为0）的斜率的算法的流程图中，判断框中应填入的内容是5.3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在，画出这个算法的流程图.6.一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩，这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示.§13.2根本算法语句一、知识导学1．赋值语句用符号“←”表示，“”表示将的值赋给，其中是一个变量，是一个与同类型的变量或表达式.23/23\n1．条件语句主要有两种形式：“行If语句”和“块If语句”.“行If语句”的一般形式为：IfAThenB[ElseC].一个行If语句必须在一行中写完，其中方括号中的Else局部可以缺省.“块If语句”的一般格式为:IfAThenBElseCEndifThen局部和Else局部是可选的，但块If语句的出口“Endif”不能省.2．循环语句主要有两种类型：For语句和While语句.当循环的次数已经确定，可用“For”语句表示.“For”语句的一般形式为：ForIfrom“初值”tostep“步长”…Endfor上面“For”和“Endfor”之间缩进的步骤称为循环体.当循环次数不能确定是，可用“While”语句来实现循环.“While”语句的一般形式为：WhileA…Endwhile其中A表示判断执行循环的条件.上面“While”和“EndWhile”之间缩进的步骤称为循环体.二、疑难知识导析1.有的条件语句可以不带“Else”分支，即满足条件时执行B，否那么不执行任何操作.条件语句也可以进展嵌套，在进展条件语句的嵌套时，书写要有层次.例如：IfAThenB23/23\nElseifCThenDElseEEndif2.“For”语句是在执行过程中先操作，后判断.而“While”语句的特点是“前测试”，即先判断，后执行.假设初始条件不成立，那么一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现.三、经典例题导讲[例1]以下程序的运行结果是.If>5ThenIf>4ThenIf>3ThenPrint错解：8+7=15错因：误认为在一个程序中只执行一个条件语句，与在一个条件语句中只选择其中一个分支相混淆.IfAThenB[ElseC]假设满足条件A那么执行B，否那么是执行C，B和C是这个条件语句的分支，而这个程序省略了Else局部.正解：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27.[例2]下面的伪代码的效果是While<10EndWhileEnd错解：执行10次循环23/23\n错因：将For语句和While语句混淆.For语句中有步长使循环变量不断变化，而While语句那么无.正解：无限循环下去，这是因为这里始终为0，总能满足条件“”，故是一个“死循环”.点评：“死循环”是设计循环构造的大忌，此题可改变的初始值或每一次循环都增加一个值.[例3]下面的程序运行时输出的结果是（）WhileEndwhilePrintSEnd错解：第一次循环时，I被赋予2，S被赋予4；第二次循环时，I被赋予3，S被赋予4+=13；第三次循环时，I被赋予4，S被赋予13+=29；第四次循环时，I被赋予5，S被赋予.由于此时，故循环终止，输出S为54.正解：由于在循环内，每经过一次循环后S都被赋值0，因此，只要求满足条件的最后一次循环S的值，即当时，.[例4]用语句描述求使成立的最大正整数的算法过程.解：WhileEndwhilePrint23/23\n点评：此题易错的是输出值，根据While循环语句的特征当时跳出循环体，此时的值是时的最小的整数，那么使的最大整数应为的前一个奇数即.[例5]已知当时，，当时，，当时，，设计一算法求的值.解：ReadxIfthenElseifThenElseEndifEnd点评：嵌套If语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，那么需注意一个块If语句对应一个EndIf，不可省略或缺少.[例6]设计一个算法，使得输入一个正整数，输出1！+2！+3！+…+！的值.写出伪代码.解：思路一：利用单循环，循环体中必须包括一个求各项阶乘的语句以及一个求和语句.ReadnForIfrom1tonEndForPrintS23/23\n思路二：运用内外双重循环，但尤其注意的是每一次外循环T的值都要从1开场.ReadnForIfrom1tonForJfrom1toIEndForEndForPrintS四、典型习题导练1．以下的循环语句循环的次数为（）ForIfrom1to7ForJfrom1to9PintI+JEndforEndforEndA.7次B.9次C.63次D.16次2．运行下面的程序后输出的结果是，假设将程序中的A语句与B语句的位置互换，再次执行程序后输出的结果为.While′A语句′B语句EndWhilePrintx,yEnd3.伪代码描述的求T的代数式是,求的代数式是.Readn23/23\nForIfrom1tonEndforPrintT,S4.运行下面程序后输出的结果为ForIfrom10to1step-2PrintIEndforEnd5.将100名学生的一门功课的成绩依次输入并计算输出平均成绩.§13．3算法案例一、知识导学1．算法设计思想：（1）“韩信点兵—孙子问题”对正整数m从2开场逐一检验条件，假设三个条件中有任何一个不满足，那么m递增1，一直到m同时满足三个条件为止(循环过程用Goto语句实现)（2）用辗转相除法找出的最大公约数的步骤是：计算出的余数，假设，那么为的最大公约数；假设，那么把前面的除数作为新的被除数，继续运算，直到余数为0，此时的除数即为正整数的最大公约数.2.更相减损术的步骤：（1）任意给出两个正数，判断它们是否都是偶数.假设是，用2约简；假设不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，那么这个数（等数）就是所求的最大公约数.（3）二分法求方程在区间内的一个近似解的解题步骤可表示为23/23\nS1取[]的中点，将区间一分为二；S2假设，那么就是方程的根；否那么判别根在的左侧还是右侧：假设，，以代替；假设，那么，以代替；S3假设，计算终止，此时，否那么转S1.二、疑难知识导析1．表示不超过的整数局部，如，但当是负数时极易出错，如就是错误的，应为-2.2．表示除以所得的余数，也可用表示.3．辗转相除法与更相减损术求最大公约数的联系与区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果表达形式来看，辗转相除法表达结果是以相除余数为0那么得到，而更相减损术那么以减数与差相等而得到.4．用二分法求方程近似解，必须先判断方程在给定区间[]上是否有解,即连续且满足.并在二分搜索过程中需对中点处函数值的符号进展屡次循环判定，故需要选择构造、循环构造，即可用Goto语句和条件语句实现算法.三、经典例题导讲[例1]，，23/23\n，7=.A．16，-1，4，3B.15，0，4，3C.15,-1,3,4D.15,-1,4,3错解：根据表示不超过的整数局部,表示除以所得的余数,选择B.错因:对表示的含义理解不透彻,将不超过-0.05的整数错认为是0,将负数的大小比较与正数的大小比较相混淆.正解：不超过-0.05的整数是-1,所以答案为D.[例2]所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于0且小于1000的整数是否为同构数.错解：算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相等，假设相等，那么为同构数.ReadxIfororThenPrintxEndifEnd错因：在表示个位或最后两位或最后三位出现错误，“/”仅表示除，y/10,y/100,y/1000都仅仅表示商.正解：可用来表示个位，最后两位以及最后三位.ReadxIfororThenPrintxEndif23/23\nEnd[例3]《孙子算经》中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上2，每次加3，加成5除余3的时候停下来，再在这个数上每次加15，到得出7除2的时候，就是答数.试用流程图和伪代码表示这一算法.解：流程图为：伪代码为：102030IfThenGoto2040IfThenPrintGoto8050Endif6070Goto4080End点评：这是孙子思想的表达，主要是依次满足三个整除条件.23/23\n[例4]分别用辗转相除法、更相减损法求192与81的最大公约数.解：辗转相除法：S1S2S3S4S5故3是192与81的最大公约数.更相减损法：S1S2S3S4S5S6S7S8S9故3是192与81的最大公约数.点评：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停顿除法运算，此时的小数就是两者的最大公约数，更相减损术是当大数减去小数的差等于小数时减法停顿，较小的数就是最大公约数.[例5]为了设计用区间二分法求方程在[0，1]上的一个近似解（误差不超过0.001）的算法,流程图的各个框图如下所示,请重新排列各框图,并用带箭头的流线和判断符号“Y”、“N”组成正确的算法流程图,并写出其伪代码.(其中分别表示区间的左右端点)23/23\n图13-3-2流程图为图13-3-3伪代码为10Read20304050IfThenGoto12023/23\n60IfThen70100Endif80Else90100Endif110IfThenGoto20120Print130End点评：二分法的根本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来.[例6]用秦九韶算法计算多项式在时的值时，的值为.解：根据秦九韶算法，此多项式可变形为按照从内到外的顺序，依次计算一次多项式当时的值：故当时多项式的值为.点评：秦九韶算法的关键是n次多项式的变形.把一个次多项式改写成23/23\n，求多项式的值，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值，这样把求次多项式的值问题转化为求个一次多项式的值的问题，这种方法成为秦九韶算法.这种算法中有反复执行的步骤，因此，可考虑用循环构造实现.四、典型习题导练1．以下短文摘自古代《孙子算经》一书，其引申出的“大衍求一术”称为“中国剩余原理”：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”答曰（）.A．二十一B.二十二C.二十三D.二十四2．用辗转相除法求52与39的最大公约数的循环次数为（）.A．1次B.2次C.3次D.5次3．下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和.ForIfrom1to10Printx;IfThenElseEndIfEndforPrintPrint“奇数个数=”；，“偶数个数=”；4．假设一个数的各因子之和正好等于该数本身，那么该数成为完数.请补充完整以下找出1～100之间的所有完数的伪代码.Forfrom2to100Forbfrom2toIfmod(a,b)=0ThenEndif23/23\nEndForIfThenPrintaEndifEndForEnd5．设计求被9除余4，被11除余3的最小正整数的算法，画出流程图，写出伪代码.6．利用辗转相除法或更相减损术求324,243,135的最大公约数.23/23
