高中数学经典错因正解汇总：第十三章算法初步.doc

第十三章 算法初步 13.1 流程图一、 知识导学1. 流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序.2算法的三种基本的逻辑结构：顺序结构、条件结构、循环结构.3根据对条件的不同处理，循环结构又分为两种：直到型(until型)循环：在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体.满足则停止.如图13-1-3，先执行A框，再判断给定的条件是否为“假”，若为“假”，则再执行A，如此反复，直到为“真”为止. 当型（while型）循环：在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环体，不满足则停止.如图13-1-4，当给定的条件成立（“真”）时，反复执行A框操作，直到条件为“假”时才停止循环. 图13-1-1 图13-1-2二、疑难知识1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：（1）有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的.（2）确定性：算法的每一步骤和次序应当是确定的.（3）有效性：算法的每一步骤都必须是有效的.2. 画流程图时必须注意以下几方面： （1）使用标准的图形符号. （2）流程图一般按从上到下、从左到右的方向画. （3）除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号. （4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果. （5）在图形符号内描述的语言要非常简练清楚.3. 算法三种逻辑结构的几点说明：（1）顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.在流程图中的体现就是用流程线自上而下地连接起来，按顺序执行算法步骤.（2）一个条件结构可以有多个判断框.（3）循环结构要在某个条件下终止循环，这就需要条件结构来判断.在循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.三、经典例题例1 已知三个单元存放了变量，的值，试给出一个算法，顺次交换， 的值（即取的值，取的值，取的值），并画出流程图.错解：第一步 第二步 第三步 流程图为 图13-1-3 错因：未理解赋值的含义，由上面的算法使得，均取的值.举一形象的例子：有蓝和黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤完成算法. 我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换.正确的解法应为：S1 取一只空的墨水瓶，设其为白色； S2 将黑墨水瓶中的蓝墨水装入白瓶中； S3 将蓝墨水瓶中的黑墨水装入黑瓶中； S4 将白瓶中的蓝墨水装入蓝瓶中； S5 交换结束.正解：第一步 先将的值赋给变量，这时存放的单元可作它用 第二步 再将的值赋给，这时存放的单元可作它用 第三步 同样将的值赋给，这时存放的单元可作它用 第四步 最后将的值赋给，三个变量，的值就完成了交换流程图为 图13-1-4点评：在计算机中，每个变量都分配了一个存储单元，为了达到交换的目的，需要一个单元存放中间变量.例2已知三个数，.试给出寻找这三个数中最大的一个算法，画出该算法的流程图. 解：流程图为图13-1-5点评：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰.若改为求100个数中的最大数或最小数的问题则选择此法较繁琐，可采用假设第一数最大（最小）将第一个数与后面的数依依比较，若后面的数较大（较小），则进行交换，最终第一个数即为最大（最小）值.点评：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构.例3画出求的值的算法流程图.解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号. 思路一：采用-1的奇偶次方（利用循环变量）来解决正负符号问题； 图13-1-6 图13-1-7 思路二：采用选择结构分奇偶项求和； 图13-1-8 思路三：可先将化简成，转化为一个等差数列求和问题，易利用循环结构求出结果. 例4 设计一算法，求使成立的最小正整数的值.解： 流程图为 图13-1-9 点评：这道题仍然是考察求和的循环结构的运用问题，需要强调的是求和语句的表示方法.若将题改为求使成立的最大正整数的值时，则需注意的是输出的值.例5任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判断. 解：算法为：S1 判断n是否等于2，若n=2，则n是质数；若n2，则执行S2S2 依次从2n-1检验是不是的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数.点评：要验证是否为质数首先必须对质数的本质含义作深入分析：（1）质数是只能被1和自身整除的大于1的整数. （2）要判断一个大于1的整数n是否为质数，只要根据定义，用比这个整数小的数去除n.如果它只能被1和本身整除，而不能被其它整数整除，则这个数便是质数. 图13-1-10 例6设计一个求无理数的近似值的算法.分析：无理数的近似值可看作是方程的正的近似根，因此该算法的实质是设计一个求方程的近似根的算法.其基本方法即运用二分法求解方程的近似解.解：设所求近似根与精确解的差的绝对值不超过0.005,算法:S1 令.因为,所以设S2 令,判断是否为0,若是,则m为所求;若否,则继续判断大于0还是小于0.S3 若0,则;否则,令.S4 判断是否成立，若是，则之间的任意值均为满足条件的近似根；若否，则返回第二步.点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述.四、典型习题1已知两个单元分别存放了变量和的值，则可以实现变量交换的算法是（ ）. AS1 BS1 CS1 DS1 S2 S2 S2 S2 S3 S3 1 下面流程图中的错误是（ ） 图13-1-11 A没有赋值 B循环结构有错 CS的计算不对 D判断条件不成立3.将“打电话”的过程描述成一个算法，这个算法可表示为 ，由此说明算法具有下列特性 . 4. 在表示求直线（，为常数，且，不同时为0）的斜率的算法的流程图中，判断框中应填入的内容是 5. 3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在，画出这个算法的流程图.6.一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩，这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示.13.2基本算法语句一、知识导学1 赋值语句用符号“”表示，“”表示将 的值赋给，其中是一个变量，是一个与同类型的变量或表达式.2 条件语句主要有两种形式：“行If 语句”和“块If语句”. “行If 语句”的一般形式为：If A Then B Else C .一个行If 语句必须在一行中写完，其中方括号中的Else部分可以缺省.“块If 语句”的一般格式为: If A Then B Else C End if Then 部分和 Else 部分是可选的，但块If语句的出口“End if”不能省.3 循环语句主要有两种类型：For语句和While语句.当循环的次数已经确定，可用“For”语句表示.“For”语句的一般形式为：For I from“初值” to step“步长” End for 上面“For”和“End for”之间缩进的步骤称为循环体.当循环次数不能确定是，可用“While”语句来实现循环.“While”语句的一般形式为：While AEnd while其中A表示判断执行循环的条件.上面“While”和“End While”之间缩进的步骤称为循环体.二、疑难知识1. 有的条件语句可以不带“Else”分支，即满足条件时执行B，否则不执行任何操作.条件语句也可以进行嵌套，在进行条件语句的嵌套时，书写要有层次.例如：If A Then BElse if C Then DElse EEnd if2.“For”语句是在执行过程中先操作，后判断.而“While”语句的特点是“前测试”，即先判断，后执行.若初始条件不成立，则一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现.三、经典例题例1 下列程序的运行结果是 .If 5 Then If 4 Then If 3 Then Print 错解：8+7=15错因：误认为在一个程序中只执行一个条件语句，与在一个条件语句中只选择其中一个分支相混淆.If A Then B Else C 若满足条件A 则执行B，否则是执行C，B和C是这个条件语句的分支，而这个程序省略了Else部分.正解：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27.例2 下面的伪代码的效果是 While 10End WhileEnd错解：执行10次循环错因：将For语句和While语句混淆. For语句中有步长使循环变量不断变化，而While语句则无.正解：无限循环下去，这是因为这里始终为0，总能满足条件“”，故是一个“死循环”.点评：“死循环”是设计循环结构的大忌，此题可改变的初始值或每一次循环都增加一个值. 例3下面的程序运行时输出的结果是（ ）While End while Print SEnd 错解：第一次循环时，I被赋予2，S被赋予4；第二次循环时，I被赋予3，S被赋予4+=13；第三次循环时，I被赋予4，S被赋予13+=29；第四次循环时，I被赋予5，S被赋予.由于此时，故循环终止，输出S为54.正解：由于在循环内，每经过一次循环后S都被赋值0，因此，只要求满足条件的最后一次循环S的值，即当时，.例4用语句描述求使成立的最大正整数的算法过程.解： While End while Print 点评：此题易错的是输出值，根据While循环语句的特征当时跳出循环体，此时的值是时的最小的整数，则使的最大整数应为的前一个奇数即.例5已知当时，当时，当时，设计一算法求的值.解： Read xIf then Else if Then Else End if End 点评：嵌套If语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，则需注意一个块If语句对应一个End If，不可省略或缺少. 例6设计一个算法，使得输入一个正整数，输出1！+2！+3！+！的值.写出伪代码.解：思路一：利用单循环，循环体中必须包括一个求各项阶乘的语句以及一个求和语句. Read n For I from 1 to n End For Print S 思路二：运用内外双重循环，但尤其注意的是每一次外循环T的值都要从1开始. Read n For I from 1 to n For J from 1 to I End For End For Print S四 、典型习题1 下列的循环语句循环的次数为（ ）For I from 1 to 7 For J from 1 to 9 Pint I+J End for End forEndA.7次 B.9次 C.63次 D.16次2运行下面的程序后输出的结果是 ，若将程序中的A语句与B语句的位置互换，再次执行程序后输出的结果为 .While A语句 B语句End WhilePrint x,yEnd3.伪代码描述的求T的代数式是 ,求的代数式是 . Read n For I from 1 to n End forPrint T,S4.运行下面程序后输出的结果为 For I from 10 to 1 step -2 Print I End forEnd 5. 将100名学生的一门功课的成绩依次输入并计算输出平均成绩. 133 算法案例一、知识导学1算法设计思想：（1）“韩信点兵孙子问题”对正整数m从2开始逐一检验条件，若三个条件中有任何一个不满足，则m递增1，一直到m同时满足三个条件为止(循环过程用Goto语句实现)（2）用辗转相除法找出的最大公约数的步骤是：计算出的余数，若，则为的最大公约数；若，则把前面的除数作为新的被除数，继续运算，直到余数为0，此时的除数即为正整数的最大公约数.2.更相减损术的步骤：（1）任意给出两个正数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.（3）二分法求方程在区间内的一个近似解的解题步骤可表示为S1 取的中点，将区间 一分为二；S2 若，则就是方程的根；否则判别根在的左侧还是右侧：若，以代替；若，则，以代替；S3 若，计算终止，此时，否则转S1.二、疑难知识 1表示不超过的整数部分，如，但当是负数时极易出错，如就是错误的，应为-2.2表示除以所得的余数，也可用 表示.3辗转相除法与更相减损术求最大公约数的联系与区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.4用二分法求方程近似解，必须先判断方程在给定区间上是否有解,即连续且满足.并在二分搜索过程中需对中点处函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用Goto 语句和条件语句实现算法.三、经典例题例1 ， ， ， 7= .A16，-1，4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3错解：根据表示不超过的整数部分, 表示除以所得的余数,选择B.错因:对表示的含义理解不透彻,将不超过-0.05的整数错认为是0,将负数的大小比较与正数的大小比较相混淆.正解：不超过-0.05的整数是-1,所以答案为D.例2 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于0且小于1000的整数是否为同构数.错解： 算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相等，若相等，则为同构数. Read x If or or Then Print x End if End 错因：在表示个位或最后两位或最后三位出现错误，“/”仅表示除，y/10,y/100,y/1000都仅仅表示商.正解：可用来表示个位，最后两位以及最后三位.Read x If or or Then Print x End if End 例3孙子算经中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上2，每次加3，加成5除余3的时候停下来，再在这个数上每次加15，到得出7除2的时候，就是答数.试用流程图和伪代码表示这一算法.解：流程图为： 伪代码为：10 20 30 If Then Goto 2040 If Then Print Goto 8050 End if60 70 Goto 4080 End 点评：这是孙子思想的体现，主要是依次满足三个整除条件.例4分别用辗转相除法、更相减损法求192与81的最大公约数.解：辗转相除法： S1 S2 S3 S4 S5 故3是192 与81 的最大公约数.更相减损法：S1 S2 S3 S4 S5 S6 S7 S8 S9 故3 是192与81的最大公约数.点评：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数，更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数. 例5为了设计用区间二分法求方程在0，1上的一个近似解（误差不超过0.001）的算法,流程图的各个框图如下所示,请重新排列各框图,并用带箭头的流线和判断符号“Y”、“N”组成正确的算法流程图,并写出其伪代码.(其中分别表示区间的左右端点) 图13-3-2流程图为 图13-3-3伪代码为10 Read 20 30 40 50 If Then Goto 12060 If Then70 100 End if80 Else90 100 End if110 If Then Goto 20120 Print 130 End 点评：二分法的基本思想在