13.3《算法案例》错误解题分析

1、13.3算法案例错误解题分析一、知识导学1、算法设计思想：（1） “韩信点兵一孙子问题”对正整数m从2开始逐一检验条件，若三个条件中有任何一 个不满足，则 m递增1, 一直到m同时满足三个条件为止（循环过程用Goto语句实现）（2） 用辗转相除法找出 a.b的最大公约数的步骤是：计算出a b的余数r，若r 0，则b 为a,b的最大公约数；若r 0，则把前面的除数 b作为新的被除数，继续运算，直到余数为0,此时的除数即为正整数 a,b的最大公约数。2、 更相减损术的步骤：（1）任意给出两个正数， 判断它们是否都是偶数。若是，用2约简; 若不是，执行第二步。（2）以较大的数减去较小的数，接着把较小

2、的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最 大公约数。（3） 二分法求方程 f（x） 0在区间a,b内的一个近似解 x*的解题步骤可表示为1S1取a,b的中点x0a b，将区间一分为二；2S2若f X。0，则Xo就是方程的根；否则判别根 x在Xo的左侧还是右侧：若 fa f Xo0， x* Xo,b，以 Xo 代替 a ；若 fa f X00，则 x* a, X0，以 x° 代替 b ；S3若a b c，计算终止，此时 xX0，否则转S1。二、疑难知识导析1、 int（ x）表示不超过x的整数部分，如int（5.86） 5,i

3、nt（0.32） 0，但当x是负数时极易出错，如int（ 1.14）1就是错误的，应为-2。2、mod（a,b）表示a除以b所得的余数，也可用 a mod b表示。3、辗转相除法与更相减损术求最大公约数的联系与区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。4、用二分法求方程近似解，必须先判断方程在给定区间a,b上是否有解，即f x连续且满足f a f b0。并在二分

4、搜索过程中需对中点处函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用Goto语句和条件语句实现算法。三、经典例题导讲例 1 int(5 ) ，int( 0.05) ，mod(67,9)，45 mod 7=。A 16，-1，4，3 B 、15，0，4，3 C 、15,-1,3,4 D 、15,-1,4,3【错解】根据int(x)表示不超过x的整数部分，mod(a,b)表示a除以b所得的余数,选择B。【错因】对int( x)表示的含义理解不透彻，将不超过-0。05的整数错认为是 0,将负数的大小 比较与正数的大小比较相混淆。【正解】不超过-0。05的整数是-1,所以答案为Db例2所谓

5、同构数是指此数的平方数的最后几位与该数相等。请设计一算法判断一个大于0且小于1000的整数是否为同构数。【错解】算法思想：求出输入数的平方， 考虑其个位或最后两位或最后三位与输入数是否相 等，若相等，则为同构数。Read xy x xIf (x y 10) or (x y 100) or (x y 1000) ThenPrint xEnd ifEnd【错因】在表示个位或最后两位或最后三位出现错误，“/”仅表示除，y/10,y/100,y/1000都仅仅表示商。【正解】可用mod( y,10), mod( y,100), mod( y,1000)来表示个位，最后两位以及最后三位。Read xy

6、x xIf (x mod(y,10) or (x mod(y,100) or (x mod(y,1000) ThenPrint xEnd ifEnd例3孙子算经中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ ”可以用下面的算法解决：先在纸上写上2，每次加3，加成5除余3的时候停下来，再在这个数上每次加15,至懦出7除2的时候，就是答数。试用流程图和伪代码表示这一算法。解：流程图为：伪代码为:10 m220 mm 330 If mod m,53 Then Goto 20 40 If mod(m,7) 2 ThenPrintmGoto 80 50 En

7、d if60 m m 1570 Goto 4080 End【点评】这是孙子思想的体现，主要是依次满足三个整除条件。例 4分别用辗转相除法、更相减损法求192与 81的最大公约数。解：辗转相除法：S1192 81 230S28130221S3302119S421923S5 9 3 3 0 故 3 是 192 与 81 的最大公约数。 更相减损法：S119281111S21118130S3813051S4513021S530219S621912S71293S8936S9633故 3 是 192 与 81 的最大公约数。【点评】 辗转相除法以除法为主， 更相减损术以减法为主， 计算次数上辗转相除法计

8、算次数 相对较少。 辗转相除法是当大数被小数整除时停止除法运算， 此时的小数就是两者的最大公 约数，更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数。 例 5 为了设计用区间二分法求方程 x3 x2 1 0 在0 ，1 上的一个近似解（误差不超过 0。001）的算法 , 流程图的各个框图如下所示 , 请重新排列各框图 , 并用带箭头的流线和判断符号“丫”、 “N'组成正确的算法流程图，并写出其伪代码。（其中a,b分别表示区间的左右端点）流程图为/轴人耳鸟/心l （十占）/2/输出 /图 13-3-3伪代码为10 Read a, b20 xo(a b). 230

9、f (a) a3 a2140f(x)X。3X。2150Iff(x0)0 ThenGoto 12060If f(a)f(X0)0The n70bXo100End if80Else90aXo100End if110Ifa b 0.001The n Goto 20120PrintX0130End【点评】二分法的基本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来。例6用秦九韶算法计算多项式 f(x) 12 35x 8x2 79x3 6x4 5x5 3x6在x4时的值时， V3的值为。解：根据秦九韶算法，此多项式可变形为f Xx x x x x 3x 567983512按照

10、从内到外的顺序，依次计算一次多项式当x 4时的值:V04V13 ( 4)57V2(4) ( 7)634V3(4) 347957故当X4时多项式的值为57。【点评】秦九韶算法的关键是 n 次多项式的变形。把一个 n 次多项式f (x) anxn an 1xn 1a1x a0 改写成f(x) ( (anx an 1)x an 2)x a1)x a0 ，求多项式的值，首先计算最内层括号 内一次多项式的值， 然后由内向外逐层计算一次多项式的值， 这样把求 n 次多项式的值问题 转化为求 n 个一次多项式的值的问题， 这种方法成为秦九韶算法。 这种算法中有反复执行的 步骤，因此，可考虑用循环结构实现。仅供个人用于学习、研究；不得用于商业用途。For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommerziellen Zweckerwerdet werden.Pour l ' e tude et