高中数学经典错因正解汇总：第十三章算法初步.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 点评：二分法的基本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来.例6 用秦九韶算法计算多项式在时的值时， 的值为 .解： 根据秦九韶算法，此多项式可变形为按照从内到外的顺序，依次计算一次多项式当时的值： 故当时多项式的值为.点评：秦九韶算法的关键是n次多项式的变形.把一个次多项式改写成，求多项式的值，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值，这样把求次多项式的值问题转化为求个一次多项式的值的问题，这种方法成为秦九韶算法.这种算法中有反复执行的步骤，因此，可考虑用循环结构实现.四、典型习题1以下短文摘自古代孙子算经一书，其引申出的“大衍求一术”称为“中国剩余原理”：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”答曰（ ）. A二十一 B.二十二 C.二十三 D.二十四2用辗转相除法求52与39的最大公约数的循环次数为（ ）.A1次 B.2次 C.3次 D.5次3下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和.For I from 1 to 10 Print x; If Then Else End IfEnd forPrintPrint “奇数个数=”； ，“偶数个数=”；4若一个数的各因子之和正好等于该数本身，则该数成为完数.请补充完整下列找出1100之间的所有完数的伪代码.For from 2 to 100For b from 2 to If mod(a,b)=0 Then End ifEnd For If Then Print aEnd if End ForEnd 5设计求被9除余4，被11除余3的最小正整数的算法，画出流程图，写出伪代码.6利用辗转相除法或更相减损术求324,243,135的最大公约数.17