聚焦高考中的算法

梅磊

算法初步，可以概括為一種思想、三種結(jié)構(gòu)、五種語句及三個(gè)案例.具體而言，一種思想就是程序化的思想；三種結(jié)構(gòu)就是順序結(jié)構(gòu)、條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)；五種語句就是輸入語句、輸出語句、賦值語句、條件語句和循環(huán)語句；三個(gè)案例就是輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法以及進(jìn)位制.

考點(diǎn)1 算法思想

算法實(shí)際上就是解決某一類問題的程序化方法，它通常以一系列明確有限的步驟的形式出現(xiàn).算法的基本特征程序性、明確性和有限性.高中階段，學(xué)習(xí)算法，主要在于體會(huì)算法思想. 高考對(duì)算法思想的考查往往結(jié)合程序框圖、算法語句、算法案例或其他有關(guān)內(nèi)容進(jìn)行.

例1 （2014年湖北卷理13）設(shè)[a]是一個(gè)各位數(shù)字都不是0且沒有重復(fù)數(shù)字的三位數(shù).將組成[a]的3個(gè)數(shù)字按從小到大排成的三位數(shù)記為[I（a）]，按從大到小排成的三位數(shù)記為[D（a）]（例如[a=815]，則[I（a）=158]，[D（a）=851]）. 閱讀如圖所示的程序框圖，運(yùn)行相應(yīng)的程序，任意輸入一個(gè)[a]，輸出的結(jié)果[b=] .

解析 輸入[a=815]，按照程序框圖，運(yùn)行相應(yīng)的程序即可.

當(dāng)[a=815]時(shí)，則[b=851-158=693≠815]，從而進(jìn)入循環(huán)，[a=693].

當(dāng)[a=693]時(shí)，則[b=963-369=594≠693]，從而繼續(xù)循環(huán)，[a=594].

當(dāng)[a=594]時(shí)，則[b=945-459=495≠594]，從而繼續(xù)循環(huán)，[a=495].

當(dāng)[a=495]時(shí)，則[b=945-459=495=a]，從而終止循環(huán)，故輸出[b=495].

點(diǎn)撥 本題是一道開放性試題，輸入的[a]任意的，但輸出的[b]是確定的.既然輸入的[a]是任意的，我們不妨選擇題設(shè)所給的例子[a=815]，按照程序框圖，運(yùn)行相應(yīng)的程序即可得到[b=495].還可以選擇[a=123]等. 本題的背景是“數(shù)字黑洞”問題，意蘊(yùn)深厚，充滿著數(shù)學(xué)的奇異美和統(tǒng)一美. 類似地，四位數(shù)的數(shù)字黑洞是6174.

考點(diǎn)2 程序框圖

程序框圖的題型主要有三類：計(jì)算輸出結(jié)果、補(bǔ)充程序框圖、計(jì)算輸入數(shù)值.因?yàn)檠h(huán)結(jié)構(gòu)程序框圖中必然包含順序結(jié)構(gòu)和條件結(jié)構(gòu)，所以循環(huán)結(jié)構(gòu)是考查的重點(diǎn)和熱點(diǎn).處理循環(huán)結(jié)構(gòu)的程序框圖時(shí)，循環(huán)次數(shù)容易出錯(cuò)，要特別注意程序終止的條件，即何時(shí)退出循環(huán).必要時(shí)可以從開始和結(jié)尾處檢驗(yàn)算法是否正確.循環(huán)結(jié)構(gòu)中往往出現(xiàn)多個(gè)變量，在執(zhí)行算法框圖時(shí)，必須嚴(yán)格按照流程線箭頭的方向來執(zhí)行算法步驟，千萬不要將循環(huán)體中算法的先后次序搞錯(cuò).

例2 （2014年湖北卷文14）閱讀如圖所示的程序框圖，運(yùn)行相應(yīng)的程序，若輸入[n]的值為9，則輸出[S]的值為 .

解析 第一次運(yùn)行時(shí)，

[S=0+21+1=21+1]，[k=1+1].

第二次運(yùn)行時(shí)，

[S=（21+1）+（22+2）]，[k=2+1].

……

所以框圖運(yùn)算的是

[S=（21+1）+（22+2）+…+（29+9）=1067].

點(diǎn)撥 程序框圖含有循環(huán)結(jié)構(gòu)且循環(huán)次數(shù)比較多時(shí)，不要盲目地重復(fù)運(yùn)算，否則運(yùn)算量會(huì)較大甚至?xí)悴怀鰜?可以先循環(huán)幾次，再找出規(guī)律，規(guī)律往往涉及數(shù)列求和.這樣，理解了循環(huán)結(jié)構(gòu)的含義，往往會(huì)簡(jiǎn)化計(jì)算，起到事半功倍的效果.

考點(diǎn)3 算法語句

了解幾種基本算法語句——輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句的含義.其中容易出錯(cuò)的是賦值語句.賦值語句的一般格式：變量=表達(dá)式.顧名思義，賦值語句就是將表達(dá)式所代表的值賦給變量.賦值語句中的“=”稱作賦值號(hào).執(zhí)行賦值語句時(shí)，先計(jì)算“=”右邊表達(dá)式的值，然后把這個(gè)值賦給“=”左邊的變量.賦值號(hào)的左右兩邊不能對(duì)換，如“[A=B]”“[B=A]”的含義運(yùn)行結(jié)果是不同的.

例3 （2013年陜西卷文4理3）根據(jù)下列算法語句，當(dāng)輸入[x]為60時(shí)，輸出[y]的值為（ ）

[輸入[x]：

IF [x<=50] THEN

[y=0.5?x]

ELSE

[y=25+0.6?（x-50）]

END IF

輸出[y]]

A. 25 B. 30

C. 31 D. 61

解析 當(dāng)[x=60]時(shí)，[y=25+0.6（60-50）][=31].

答案 C

點(diǎn)撥 本題實(shí)際上是一個(gè)分段函數(shù)求值問題.分段函數(shù)問題可以通過條件語句來實(shí)現(xiàn).

考點(diǎn)4 算法案例

輾轉(zhuǎn)相除法與更相減損術(shù)都是求兩個(gè)正整數(shù)的最大公約數(shù)的方法. 二者的算理卻是相似的，有異曲同工之妙.主要區(qū)別在于輾轉(zhuǎn)相除法進(jìn)行的是除法運(yùn)算，即輾轉(zhuǎn)相除；而更相減損術(shù)進(jìn)行的是減法運(yùn)算，但實(shí)質(zhì)都是一個(gè)不斷遞歸的過程.

秦九韶算法是求一元多項(xiàng)式值的一種方法. 秦九韶算法的特點(diǎn)在于把求一個(gè)[n]次多項(xiàng)式的值轉(zhuǎn)化為求[n]個(gè)一次多項(xiàng)式的值. 通過這種轉(zhuǎn)化，把運(yùn)算的次數(shù)由至多[n（n+1）2]次乘法運(yùn)算和[n]次加法運(yùn)算，減少為至多[n]次乘法運(yùn)算和[n]次加法運(yùn)算，大大提高了運(yùn)算效率.

例4 已知[n]次多項(xiàng)式[Pn（x）=anxn+an-1xn-1+][…+a1x+a0].如果在一種算法中，計(jì)算[xk0]（[k=2，3，4，…，n]）的值需要[k-1]次乘法，計(jì)算[P3（x0）]的值共需要9次運(yùn)算（6次乘法，3次加法），那么計(jì)算[Pn（x0）]的值共需要 次運(yùn)算.

下面給出一種減少運(yùn)算次數(shù)的算法：[P0（x）=a0]，[Pk+1（x）=xPk（x）+ak+1]（[k=0，1，2，…，n-1]）.利用該算法，計(jì)算[P3（x0）]的值共需要6次運(yùn)算，計(jì)算[Pn（x0）]的值共需要 次運(yùn)算.

解析 第一種算法中，計(jì)算[Pn（x0）]的值共需要[n（n+1）2]次乘法運(yùn)算和[n]次加法運(yùn)算，故總運(yùn)算次數(shù)為[n（n+3）2].第二種算法中，計(jì)算[Pn（x0）]的值共需要[n]次乘法運(yùn)算和[n]次加法運(yùn)算，故總運(yùn)算次數(shù)為[2n].

點(diǎn)撥 第一種算法為直接算法，其優(yōu)點(diǎn)是簡(jiǎn)單、易懂，缺點(diǎn)是運(yùn)算次數(shù)太多，運(yùn)算效率不高.第二種算法是秦九韶算法，其特點(diǎn)是把求一個(gè)[n]次多項(xiàng)式的值轉(zhuǎn)化為求[n]個(gè)一次多項(xiàng)式的值，避免了對(duì)自變量[x]單獨(dú)作冪的運(yùn)算，而與系數(shù)一起逐步增長(zhǎng)冪次，從而減少運(yùn)算次數(shù)，提高運(yùn)算效率.endprint

算法初步，可以概括為一種思想、三種結(jié)構(gòu)、五種語句及三個(gè)案例.具體而言，一種思想就是程序化的思想；三種結(jié)構(gòu)就是順序結(jié)構(gòu)、條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)；五種語句就是輸入語句、輸出語句、賦值語句、條件語句和循環(huán)語句；三個(gè)案例就是輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法以及進(jìn)位制.

考點(diǎn)1 算法思想

算法實(shí)際上就是解決某一類問題的程序化方法，它通常以一系列明確有限的步驟的形式出現(xiàn).算法的基本特征程序性、明確性和有限性.高中階段，學(xué)習(xí)算法，主要在于體會(huì)算法思想. 高考對(duì)算法思想的考查往往結(jié)合程序框圖、算法語句、算法案例或其他有關(guān)內(nèi)容進(jìn)行.

例1 （2014年湖北卷理13）設(shè)[a]是一個(gè)各位數(shù)字都不是0且沒有重復(fù)數(shù)字的三位數(shù).將組成[a]的3個(gè)數(shù)字按從小到大排成的三位數(shù)記為[I（a）]，按從大到小排成的三位數(shù)記為[D（a）]（例如[a=815]，則[I（a）=158]，[D（a）=851]）. 閱讀如圖所示的程序框圖，運(yùn)行相應(yīng)的程序，任意輸入一個(gè)[a]，輸出的結(jié)果[b=] .

解析 輸入[a=815]，按照程序框圖，運(yùn)行相應(yīng)的程序即可.

當(dāng)[a=815]時(shí)，則[b=851-158=693≠815]，從而進(jìn)入循環(huán)，[a=693].

當(dāng)[a=693]時(shí)，則[b=963-369=594≠693]，從而繼續(xù)循環(huán)，[a=594].

當(dāng)[a=594]時(shí)，則[b=945-459=495≠594]，從而繼續(xù)循環(huán)，[a=495].

當(dāng)[a=495]時(shí)，則[b=945-459=495=a]，從而終止循環(huán)，故輸出[b=495].

點(diǎn)撥 本題是一道開放性試題，輸入的[a]任意的，但輸出的[b]是確定的.既然輸入的[a]是任意的，我們不妨選擇題設(shè)所給的例子[a=815]，按照程序框圖，運(yùn)行相應(yīng)的程序即可得到[b=495].還可以選擇[a=123]等. 本題的背景是“數(shù)字黑洞”問題，意蘊(yùn)深厚，充滿著數(shù)學(xué)的奇異美和統(tǒng)一美. 類似地，四位數(shù)的數(shù)字黑洞是6174.

考點(diǎn)2 程序框圖

程序框圖的題型主要有三類：計(jì)算輸出結(jié)果、補(bǔ)充程序框圖、計(jì)算輸入數(shù)值.因?yàn)檠h(huán)結(jié)構(gòu)程序框圖中必然包含順序結(jié)構(gòu)和條件結(jié)構(gòu)，所以循環(huán)結(jié)構(gòu)是考查的重點(diǎn)和熱點(diǎn).處理循環(huán)結(jié)構(gòu)的程序框圖時(shí)，循環(huán)次數(shù)容易出錯(cuò)，要特別注意程序終止的條件，即何時(shí)退出循環(huán).必要時(shí)可以從開始和結(jié)尾處檢驗(yàn)算法是否正確.循環(huán)結(jié)構(gòu)中往往出現(xiàn)多個(gè)變量，在執(zhí)行算法框圖時(shí)，必須嚴(yán)格按照流程線箭頭的方向來執(zhí)行算法步驟，千萬不要將循環(huán)體中算法的先后次序搞錯(cuò).

例2 （2014年湖北卷文14）閱讀如圖所示的程序框圖，運(yùn)行相應(yīng)的程序，若輸入[n]的值為9，則輸出[S]的值為 .

解析 第一次運(yùn)行時(shí)，

[S=0+21+1=21+1]，[k=1+1].

第二次運(yùn)行時(shí)，

[S=（21+1）+（22+2）]，[k=2+1].

……

所以框圖運(yùn)算的是

[S=（21+1）+（22+2）+…+（29+9）=1067].

點(diǎn)撥 程序框圖含有循環(huán)結(jié)構(gòu)且循環(huán)次數(shù)比較多時(shí)，不要盲目地重復(fù)運(yùn)算，否則運(yùn)算量會(huì)較大甚至?xí)悴怀鰜?可以先循環(huán)幾次，再找出規(guī)律，規(guī)律往往涉及數(shù)列求和.這樣，理解了循環(huán)結(jié)構(gòu)的含義，往往會(huì)簡(jiǎn)化計(jì)算，起到事半功倍的效果.

考點(diǎn)3 算法語句

了解幾種基本算法語句——輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句的含義.其中容易出錯(cuò)的是賦值語句.賦值語句的一般格式：變量=表達(dá)式.顧名思義，賦值語句就是將表達(dá)式所代表的值賦給變量.賦值語句中的“=”稱作賦值號(hào).執(zhí)行賦值語句時(shí)，先計(jì)算“=”右邊表達(dá)式的值，然后把這個(gè)值賦給“=”左邊的變量.賦值號(hào)的左右兩邊不能對(duì)換，如“[A=B]”“[B=A]”的含義運(yùn)行結(jié)果是不同的.

例3 （2013年陜西卷文4理3）根據(jù)下列算法語句，當(dāng)輸入[x]為60時(shí)，輸出[y]的值為（ ）

[輸入[x]：

IF [x<=50] THEN

[y=0.5?x]

ELSE

[y=25+0.6?（x-50）]

END IF

輸出[y]]

A. 25 B. 30

C. 31 D. 61

解析 當(dāng)[x=60]時(shí)，[y=25+0.6（60-50）][=31].

答案 C

點(diǎn)撥 本題實(shí)際上是一個(gè)分段函數(shù)求值問題.分段函數(shù)問題可以通過條件語句來實(shí)現(xiàn).

考點(diǎn)4 算法案例

輾轉(zhuǎn)相除法與更相減損術(shù)都是求兩個(gè)正整數(shù)的最大公約數(shù)的方法. 二者的算理卻是相似的，有異曲同工之妙.主要區(qū)別在于輾轉(zhuǎn)相除法進(jìn)行的是除法運(yùn)算，即輾轉(zhuǎn)相除；而更相減損術(shù)進(jìn)行的是減法運(yùn)算，但實(shí)質(zhì)都是一個(gè)不斷遞歸的過程.

秦九韶算法是求一元多項(xiàng)式值的一種方法. 秦九韶算法的特點(diǎn)在于把求一個(gè)[n]次多項(xiàng)式的值轉(zhuǎn)化為求[n]個(gè)一次多項(xiàng)式的值. 通過這種轉(zhuǎn)化，把運(yùn)算的次數(shù)由至多[n（n+1）2]次乘法運(yùn)算和[n]次加法運(yùn)算，減少為至多[n]次乘法運(yùn)算和[n]次加法運(yùn)算，大大提高了運(yùn)算效率.

例4 已知[n]次多項(xiàng)式[Pn（x）=anxn+an-1xn-1+][…+a1x+a0].如果在一種算法中，計(jì)算[xk0]（[k=2，3，4，…，n]）的值需要[k-1]次乘法，計(jì)算[P3（x0）]的值共需要9次運(yùn)算（6次乘法，3次加法），那么計(jì)算[Pn（x0）]的值共需要 次運(yùn)算.

下面給出一種減少運(yùn)算次數(shù)的算法：[P0（x）=a0]，[Pk+1（x）=xPk（x）+ak+1]（[k=0，1，2，…，n-1]）.利用該算法，計(jì)算[P3（x0）]的值共需要6次運(yùn)算，計(jì)算[Pn（x0）]的值共需要 次運(yùn)算.

解析 第一種算法中，計(jì)算[Pn（x0）]的值共需要[n（n+1）2]次乘法運(yùn)算和[n]次加法運(yùn)算，故總運(yùn)算次數(shù)為[n（n+3）2].第二種算法中，計(jì)算[Pn（x0）]的值共需要[n]次乘法運(yùn)算和[n]次加法運(yùn)算，故總運(yùn)算次數(shù)為[2n].

點(diǎn)撥 第一種算法為直接算法，其優(yōu)點(diǎn)是簡(jiǎn)單、易懂，缺點(diǎn)是運(yùn)算次數(shù)太多，運(yùn)算效率不高.第二種算法是秦九韶算法，其特點(diǎn)是把求一個(gè)[n]次多項(xiàng)式的值轉(zhuǎn)化為求[n]個(gè)一次多項(xiàng)式的值，避免了對(duì)自變量[x]單獨(dú)作冪的運(yùn)算，而與系數(shù)一起逐步增長(zhǎng)冪次，從而減少運(yùn)算次數(shù)，提高運(yùn)算效率.endprint

算法初步，可以概括為一種思想、三種結(jié)構(gòu)、五種語句及三個(gè)案例.具體而言，一種思想就是程序化的思想；三種結(jié)構(gòu)就是順序結(jié)構(gòu)、條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu)；五種語句就是輸入語句、輸出語句、賦值語句、條件語句和循環(huán)語句；三個(gè)案例就是輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法以及進(jìn)位制.

考點(diǎn)1 算法思想

算法實(shí)際上就是解決某一類問題的程序化方法，它通常以一系列明確有限的步驟的形式出現(xiàn).算法的基本特征程序性、明確性和有限性.高中階段，學(xué)習(xí)算法，主要在于體會(huì)算法思想. 高考對(duì)算法思想的考查往往結(jié)合程序框圖、算法語句、算法案例或其他有關(guān)內(nèi)容進(jìn)行.

例1 （2014年湖北卷理13）設(shè)[a]是一個(gè)各位數(shù)字都不是0且沒有重復(fù)數(shù)字的三位數(shù).將組成[a]的3個(gè)數(shù)字按從小到大排成的三位數(shù)記為[I（a）]，按從大到小排成的三位數(shù)記為[D（a）]（例如[a=815]，則[I（a）=158]，[D（a）=851]）. 閱讀如圖所示的程序框圖，運(yùn)行相應(yīng)的程序，任意輸入一個(gè)[a]，輸出的結(jié)果[b=] .

解析 輸入[a=815]，按照程序框圖，運(yùn)行相應(yīng)的程序即可.

當(dāng)[a=815]時(shí)，則[b=851-158=693≠815]，從而進(jìn)入循環(huán)，[a=693].

當(dāng)[a=693]時(shí)，則[b=963-369=594≠693]，從而繼續(xù)循環(huán)，[a=594].

當(dāng)[a=594]時(shí)，則[b=945-459=495≠594]，從而繼續(xù)循環(huán)，[a=495].

當(dāng)[a=495]時(shí)，則[b=945-459=495=a]，從而終止循環(huán)，故輸出[b=495].

點(diǎn)撥 本題是一道開放性試題，輸入的[a]任意的，但輸出的[b]是確定的.既然輸入的[a]是任意的，我們不妨選擇題設(shè)所給的例子[a=815]，按照程序框圖，運(yùn)行相應(yīng)的程序即可得到[b=495].還可以選擇[a=123]等. 本題的背景是“數(shù)字黑洞”問題，意蘊(yùn)深厚，充滿著數(shù)學(xué)的奇異美和統(tǒng)一美. 類似地，四位數(shù)的數(shù)字黑洞是6174.

考點(diǎn)2 程序框圖

程序框圖的題型主要有三類：計(jì)算輸出結(jié)果、補(bǔ)充程序框圖、計(jì)算輸入數(shù)值.因?yàn)檠h(huán)結(jié)構(gòu)程序框圖中必然包含順序結(jié)構(gòu)和條件結(jié)構(gòu)，所以循環(huán)結(jié)構(gòu)是考查的重點(diǎn)和熱點(diǎn).處理循環(huán)結(jié)構(gòu)的程序框圖時(shí)，循環(huán)次數(shù)容易出錯(cuò)，要特別注意程序終止的條件，即何時(shí)退出循環(huán).必要時(shí)可以從開始和結(jié)尾處檢驗(yàn)算法是否正確.循環(huán)結(jié)構(gòu)中往往出現(xiàn)多個(gè)變量，在執(zhí)行算法框圖時(shí)，必須嚴(yán)格按照流程線箭頭的方向來執(zhí)行算法步驟，千萬不要將循環(huán)體中算法的先后次序搞錯(cuò).

例2 （2014年湖北卷文14）閱讀如圖所示的程序框圖，運(yùn)行相應(yīng)的程序，若輸入[n]的值為9，則輸出[S]的值為 .

解析 第一次運(yùn)行時(shí)，

[S=0+21+1=21+1]，[k=1+1].

第二次運(yùn)行時(shí)，

[S=（21+1）+（22+2）]，[k=2+1].

……

所以框圖運(yùn)算的是

[S=（21+1）+（22+2）+…+（29+9）=1067].

點(diǎn)撥 程序框圖含有循環(huán)結(jié)構(gòu)且循環(huán)次數(shù)比較多時(shí)，不要盲目地重復(fù)運(yùn)算，否則運(yùn)算量會(huì)較大甚至?xí)悴怀鰜?可以先循環(huán)幾次，再找出規(guī)律，規(guī)律往往涉及數(shù)列求和.這樣，理解了循環(huán)結(jié)構(gòu)的含義，往往會(huì)簡(jiǎn)化計(jì)算，起到事半功倍的效果.

考點(diǎn)3 算法語句

了解幾種基本算法語句——輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句的含義.其中容易出錯(cuò)的是賦值語句.賦值語句的一般格式：變量=表達(dá)式.顧名思義，賦值語句就是將表達(dá)式所代表的值賦給變量.賦值語句中的“=”稱作賦值號(hào).執(zhí)行賦值語句時(shí)，先計(jì)算“=”右邊表達(dá)式的值，然后把這個(gè)值賦給“=”左邊的變量.賦值號(hào)的左右兩邊不能對(duì)換，如“[A=B]”“[B=A]”的含義運(yùn)行結(jié)果是不同的.

例3 （2013年陜西卷文4理3）根據(jù)下列算法語句，當(dāng)輸入[x]為60時(shí)，輸出[y]的值為（ ）

[輸入[x]：

IF [x<=50] THEN

[y=0.5?x]

ELSE

[y=25+0.6?（x-50）]

END IF

輸出[y]]

A. 25 B. 30

C. 31 D. 61

解析 當(dāng)[x=60]時(shí)，[y=25+0.6（60-50）][=31].

答案 C

點(diǎn)撥 本題實(shí)際上是一個(gè)分段函數(shù)求值問題.分段函數(shù)問題可以通過條件語句來實(shí)現(xiàn).

考點(diǎn)4 算法案例

輾轉(zhuǎn)相除法與更相減損術(shù)都是求兩個(gè)正整數(shù)的最大公約數(shù)的方法. 二者的算理卻是相似的，有異曲同工之妙.主要區(qū)別在于輾轉(zhuǎn)相除法進(jìn)行的是除法運(yùn)算，即輾轉(zhuǎn)相除；而更相減損術(shù)進(jìn)行的是減法運(yùn)算，但實(shí)質(zhì)都是一個(gè)不斷遞歸的過程.

秦九韶算法是求一元多項(xiàng)式值的一種方法. 秦九韶算法的特點(diǎn)在于把求一個(gè)[n]次多項(xiàng)式的值轉(zhuǎn)化為求[n]個(gè)一次多項(xiàng)式的值. 通過這種轉(zhuǎn)化，把運(yùn)算的次數(shù)由至多[n（n+1）2]次乘法運(yùn)算和[n]次加法運(yùn)算，減少為至多[n]次乘法運(yùn)算和[n]次加法運(yùn)算，大大提高了運(yùn)算效率.

例4 已知[n]次多項(xiàng)式[Pn（x）=anxn+an-1xn-1+][…+a1x+a0].如果在一種算法中，計(jì)算[xk0]（[k=2，3，4，…，n]）的值需要[k-1]次乘法，計(jì)算[P3（x0）]的值共需要9次運(yùn)算（6次乘法，3次加法），那么計(jì)算[Pn（x0）]的值共需要 次運(yùn)算.

下面給出一種減少運(yùn)算次數(shù)的算法：[P0（x）=a0]，[Pk+1（x）=xPk（x）+ak+1]（[k=0，1，2，…，n-1]）.利用該算法，計(jì)算[P3（x0）]的值共需要6次運(yùn)算，計(jì)算[Pn（x0）]的值共需要 次運(yùn)算.

解析 第一種算法中，計(jì)算[Pn（x0）]的值共需要[n（n+1）2]次乘法運(yùn)算和[n]次加法運(yùn)算，故總運(yùn)算次數(shù)為[n（n+3）2].第二種算法中，計(jì)算[Pn（x0）]的值共需要[n]次乘法運(yùn)算和[n]次加法運(yùn)算，故總運(yùn)算次數(shù)為[2n].

點(diǎn)撥 第一種算法為直接算法，其優(yōu)點(diǎn)是簡(jiǎn)單、易懂，缺點(diǎn)是運(yùn)算次數(shù)太多，運(yùn)算效率不高.第二種算法是秦九韶算法，其特點(diǎn)是把求一個(gè)[n]次多項(xiàng)式的值轉(zhuǎn)化為求[n]個(gè)一次多項(xiàng)式的值，避免了對(duì)自變量[x]單獨(dú)作冪的運(yùn)算，而與系數(shù)一起逐步增長(zhǎng)冪次，從而減少運(yùn)算次數(shù)，提高運(yùn)算效率.endprint