例說算法初步中常見的易錯點

■內蒙古通遼實驗中學 姬恩澤

作為《新課程標準》增加的新內容，算法走進了中學數學。在中學數學課程的學習中，除了要讓同學們了解算法的基本含義和學習基本算法語句，更重要的是讓同學們體會和應用算法思想。新課標不但要求同學們要掌握算法的基本知識，而且要求將算法思想貫穿到高中數學的始終。然而，在具體學習過程中，發現同學們對“算法”的學習重視不夠，對算法概念的認識不夠全面，對簡單的算法問題經常出現各類錯誤，下面就舉例辨析在算法初步中常見的易錯點。

一、秦九韶算法

要點闡述：把一個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。