《错解剖析得真知-24》由会员分享，可在线阅读，更多相关《错解剖析得真知-24（9页珍藏版）》请在金锄头文库上搜索。
1、错解剖析得真知(四十) 3 算法案例 一、知识导学.算法设计思想： （1）“韩信点兵孙子问题”对正整数m从2开始逐个检查条件,若三个条件中有任何一种不满足,则m递增1,始终到m同步满足三个条件为止(循环过程用o语句实现)(2)用辗转相除法找出的最大公约数的环节是:计算出的余数,若，则为的最大公约数；若,则把前面的除数作为新的被除数,继续运算，直到余数为0，此时的除数即为正整数的最大公约数.更相减损术的环节:（1）任意给出两个正数,判断它们与否都是偶数.若是，用2约简；若不是，执行第二步.（2)以较大的数减去较小的数,接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为
2、止，则这个数（等数)就是所求的最大公约数.（3)二分法求方程在区间内的一种近似解的解题环节可表达为S1 取的中点,将区间一分为二；S若，则就是方程的根;否则鉴别根在的左侧还是右侧:若，,以替代；若，则，以替代； 若，计算终结，此时,否则转S1. 二、疑难知识导析 1表达不超过的整数部分，如，但当是负数时极易出错，如就是错误的，应为-2.表达除以所得的余数,也可用 表达.3.辗转相除法与更相减损术求最大公约数的联系与区别:(1）都是求最大公约数的措施，计算上辗转相除法以除法为主，更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少，特别当两个数字大社区别较大时计算次数的区别较明显.（2)从
3、成果体现形式来看，辗转相除法体现成果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到.用二分法求方程近似解，必须先判断方程在给定区间上与否有解,即持续且满足.并在二分搜索过程中需对中点处函数值的符号进行多次循环鉴定，故需要选择构造、循环构造,即可用Goo语句和条件语句实现算法. 三、典型例题导讲 例1 , , , 7= .A16，-1,4,3 B15,0,4,3 .5，-1,3，4 15,-1，4，3错解:根据表达不超过的整数部分，表达除以所得的余数,选择B.错因:对表达的含义理解不透彻，将不超过-05的整数错觉得是0,将负数的大小比较与正数的大小比较相混淆正解:不超过00的整数是-
4、，因此答案为D.例2 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一种不小于0且不不小于100的整数与否为同构数错解： 算法思想:求出输入数的平方,考虑其个位或最后两位或最后三位与输入数与否相等,若相等,则为同构数. Rea x If r or hen Prnt Endif nd 错因：在表达个位或最后两位或最后三位浮现错误，“/”仅表达除，y/0,y/100，y1000都仅仅表达商正解:可用来表达个位,最后两位以及最后三位.Rd If o r Then Prnt x En if End例3孙子算经中的“物不知数”问题:“今有物不知其数,三三数之剩二,五五数之剩三，七七数之
5、剩二,问物几何?”可以用下面的算法解决：先在纸上写上,每次加,加成5除余3的时候停下来,再在这个数上每次加15，到得出7除的时候，就是答数.试用流程图和伪代码表达这一算法.解:流程图为: 伪代码为：1 2 30 f Then ot2040 If Th Pin Gto 00 d f60 70 ot 480 En 点评:这是孙子思想的体现,重要是依次满足三个整除条件.例4分别用辗转相除法、更相减损法求92与81的最大公约数解：辗转相除法： S1 S2 3 S4 S5 故3是19 与8 的最大公约数.更相减损法：S1 S2 3 S4 S5 S6 S7 S8 S9 故3 是192与81的最大公约数.点
6、评：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数,更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数. 例5为了设计用区间二分法求方程在0，1上的一种近似解(误差不超过.00）的算法，流程图的各个框图如下所示,请重新排列各框图,并用带箭头的流线和判断符号“Y”、“N”构成对的的算法流程图,并写出其伪代码.(其中分别表达区间的左右端点) 图13-2流程图为 图3- 伪代码为0 Red 20 0 50 If Thn Got12060 If The 100 En if
7、 80 Else9 10 Ed if11 If Then Goto 012 Print 30 d 点评：二分法的基本思想在必修一中已渗入,这里运用算法将二分法求方程近似解的环节更清晰的表述出来例6 用秦九韶算法计算多项式在时的值时, 的值为 .解： 根据秦九韶算法，此多项式可变形为按照从内到外的顺序,依次计算一次多项式当时的值： 故当时多项式的值为点评：秦九韶算法的核心是n次多项式的变形.把一种次多项式改写成,求多项式的值，一方面计算最内层括号内一次多项式的值，然后由内向外逐级计算一次多项式的值，这样把求次多项式的值问题转化为求个一次多项式的值的问题,这种措施成为秦九韶算法这种算法中有反复执行
8、的环节，因此，可考虑用循环构造实现 四、典型习题导练 1如下短文摘自古代孙子算经一书，其引申出的“大衍求一术”称为“中国剩余原理”:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二，问物几何？”答曰( ）. A.二十一 B.二十二 C.二十三 D二十四2.用辗转相除法求5与3的最大公约数的循环次数为（ ）.A1次 B.2次 C.次 D.5次下面程序功能是记录随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和.For I fr to 10 Pin x； f Then Ese Ed Id forintPrint “奇数个数=”;,“偶数个数=”；4若一种数的各因子之和正好等于该数自身,则该数成为完数请补充完整下列找出1100之间的所有完数的伪代码.For rom2 t 10For bfom 2 o I mod(,b)0 hen En ind Fo If TenPrint aEn if End FrEd5.设计求被除余，被11除余的最小正整数的算法，画出流程图，写出伪代码.运用辗转相除法或更相减损术求32，243,13的最大公约数.
