例说算法初步中常见的易错点

■内蒙古通辽实验中学 姬恩泽

作为《新课程标准》增加的新内容，算法走进了中学数学。在中学数学课程的学习中，除了要让同学们了解算法的基本含义和学习基本算法语句，更重要的是让同学们体会和应用算法思想。新课标不但要求同学们要掌握算法的基本知识，而且要求将算法思想贯穿到高中数学的始终。然而，在具体学习过程中，发现同学们对“算法”的学习重视不够，对算法概念的认识不够全面，对简单的算法问题经常出现各类错误，下面就举例辨析在算法初步中常见的易错点。

一、秦九韶算法

要点阐述：把一个n次多项式f（x）=anxn+an-1xn-1+…+a1x+a0改写成如下形式：f（x）=（…（（anx+an-1）x+an-2）x+…+a1）x+a0，求多项式的值时，首先计算最内层括号内一次多项式的值，即v0=an，然后由内向外逐层计算一次多项式的值，即：

v1=v0x+an-1；

v2=v1x+an-2；

v3=v2x+an-3；

……

vn=vn-1x+a0。

这样，求n次多项式f（x）的值就转化为求n个一次多项式的值。

解题技巧：利用秦九韶算法计算多项式的值，关键是能正确地将所给多项式改写，然后由内到外逐次计算，由于后项计算需用到前项的结果，故应认真、细心，确保中间结果的正确性。

典型例题1用秦九韶算法求f（x）=x5-5x4+x3-1当x=2时的值。

易错点辨析：当n次多项式中出现空项时，要把系数为零的相应项补齐，否则，在处理问题时，多项式的运算次数会达不到对应的次数，从而得出错误的结果。

正解：将f（x）改写为f（x）=x5-5x4+x3+0×x2+0×x-1=（（（（x-5）x+1）x+0）x+0）x-1，由内向外逐层计算一次多项式当x=2时的值，有：

v0=1；

v1=1×2-5=-3；

v2=（-3）×2+1=-5；

v3=（-5）×2+0=-10；

v4=（-10）×2+0=-20；

v5=（-20）×2-1=-41。

所以f（2）=-41。

二、辗转相除法

要点阐述：辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法。而我国古代的更相减损术与辗转相除法在本质上是有区别的。

算法步骤：第一步，给定两个正整数m，n（m＞n）。

第二步，计算m除以n所得的余数r。

第三步，m=n，n=r。

第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步。

典型例题2用辗转相除法求288与123的最大公约数。

易错点辨析：辗转相除法的最后一步中的除数是题目所给两个正整数的最大公约数。辗转相除法通过逐次辗转相除，剩下的两数越来越小，但并没有改变它们的最大公约数。到最后的两数，大数能被小数整除，说明小数就是原来两数的最大公约数。

正解：由辗转相除法得：

288=123×2+42；

123=42×2+39；

42=39×1+3；

39=3×13。

故288与123的最大公约数是3。

归纳总结：由除法的性质知，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出它们的最大公约数。

三、更相减损术

要点阐述：《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之”。最重要一点是若所给的整数都是偶数，除以若干个2后，最后结果要乘以相同多个2。

解题步骤：第一步，任意给定两个正整数，判断它们是否都是偶数。若都是偶数，用2约简；若不是，执行第二步。

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的减数和差相等为止，则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

典型例题3用更相减损术求两个整数84与72的最大公约数。

易错点辨析：本题所给的两个整数84与72都是偶数，除以4后，最后的结果要乘以4才是原题给的两个整数的最大公约数。

正解：因为84=21×4，72=18×4，

所以21-18=3；

18-3=15；

15-3=12；

12-3=9；

9-3=6；

6-3=3。

所以21和18的最大公约数等于3。

所以84和72的最大公约数等于12。

四、程序框图

要点阐述：对于程序框图的客观题，首先要理清所要实现的算法的结构特点及流程规则，对于包含条件结构和循环结构的程序框图，要确定循环结构的条件或找出循环次数，然后确定是否能取得“=”。

规律方法：要注意循环条件、变量初值、循环体各语句之间的影响。

（1）注意各个语句顺序不同对结果的影响；

（2）注意各个变量初始值不同对结果的影响；

（3）要对循环开始和结束的变量及结束时变量的值认真检验，以免出现多循环或漏循环。

典型例题4（河北省衡水中学2020届高三卫冕联考理科数学8）执行如图1所示的程序框图，则输出S的结果为（ ）。

图1

易错点辨析：对于包含条件结构和循环结构的程序框图，当循环次数过多时，尤其注意执行最后一次循环语句时，要对循环结束时变量的值认真检验，以免出现多循环或漏循环。本题当n=2019时执行最后一次循环，进入循环体后，应先执行语句n=n+1，计算出n=2020，然后计算出，所以S=S+a=S+。

正解：当n=2019时执行最后一次循环，进入循环体，应先执行语句n=n+1，得n=2020，所以故选C。