第2課時案例2秦九韶算法

1、第 2 課時 案例 2 秦九韶算法導入新課 思路 1 (情境導入) 大家都喜歡吃蘋果吧， 我們吃蘋果都是從外到里一口一口的吃， 而蟲子卻是先鉆到蘋果里面從里到外一口一口的吃， 由此看來處理同一個問題的方法多種多樣 .怎樣求多項式 f(x)=x 5+x4+x3+x2+x+1 當 x=5 時的值呢？方法也是多種多樣的， 今天我們開始學習秦九韶算法 .推進新課新知探究提出問題(1) 求多項式 f(x)=x 5+x4+x3+x2+x+1 當 x=5 時的值有哪些方法？比較它們的特點 .( 2 )什么是秦九韶算法？( 3)怎樣評價一個算法的好壞？ 討論結果：1+2+3+4=10( 1)怎樣求多項式 f(

2、x)=x 5+x4+x3+x2+x+1 當 x=5 時的值呢？一個自然的做法就是把5代入多項式f(x)，計算各項的值，然后把它們加起來，這時，我們一共做了次乘法運算， 5 次加法運算 .另一種做法是先計算 x2的值，然后依次計算 x2x, ( x2x) x, (x2x) x ) 的值，這樣每次都可以利用上一次計 算的結果，這時，我們一共做了 4次乘法運算， 5 次加法運算 .第二種做法與第一種做法相比，乘法的運算次數(shù)減少了，因而能夠提高運算效率，對于計算機來說，做一次乘法運 算所用的時間比做一次加法運算要長得多，所以采用第二種做法，計算機能更快地得到結果.(2) 上面問題有沒有更有效的算法呢？

3、我國南宋時期的數(shù)學家秦九韶(約12021261)在他的著作數(shù)書九章中提出 了下面的算法：把一個n次多項式f(x)=a nxn+an-ixn-1 +aix+a0改寫成如下形式：f(x)=a nxn+an-ixn-1 +aix+a0 =(anxn'1+an-ixn'2+ +ai) x+ a0 =(anxn-2+an-ixn-3+a2)x+ai)x+a0 =(anx+an-1)x+an-2) x+ +ai) x+ao.求多項式的值時，首先計算最內(nèi)層括號內(nèi)一次多項式的值，即 v1=anx+an-1 ，然后由內(nèi)向外逐層計算一次多項式的值，即 v2=v1x+an-2，v3=v2x+an-3

4、， vn=vn-1x+a0，這樣，求n次多項式f (X)的值就轉(zhuǎn)化為求 n個一次多項式的值.上述方法稱為秦九韶算法.直到今天，這種算法仍是多項式求值比較先進的算法.如果一個(3)計算機的一個很重要的特點就是運算速度快，但即便如此，算法好壞的一個重要標志仍然是運算的次數(shù) 算法從理論上需要超出計算機允許范圍內(nèi)的運算次數(shù)，那么這樣的算法就只能是一個理論的算法.應用示例例 1 已知一個 5 次多項式為 f(x) =5x5+2x4+3.5x3-2.6x2+1.7x-0.8， 用秦九韶算法求這個多項式當 x=5 時的值 .解： 根據(jù)秦九韶算法，把多項式改寫成如下形式：f(x)= (5x+2)x+3.5)x

5、-2.6)x+1.7)x-0.8 ，按照從內(nèi)到外的順序，依次計算一次多項式當 x=5 時的值：v0=5；vi=5 X5+2=27;V2=27 X5+3.5=138.5;v3=138.5 3-2.6=689.9;V4=689.9 5+1.7=3 451.2;V5=3 415.2 5-0.8=17 255.2;所以，當x=5時，多項式的值等于17 255.2.算法分析：觀察上述秦九韶算法中的n個一次式，可見Vk的計算要用到vk-1的值，若令vo=an，我們可以得到下面的公式：an ,VkVk 1X an k(k 1,2,n).Vo這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現(xiàn) 算法步

6、驟如下：第一步，輸入多項式次數(shù)第二步，第三步，第四步，第五步，n、最高次的系數(shù)an和X的值.將V的值初始化為an,將i的值初始化為n-1. 輸入i次項的系數(shù)ai.v=vx+ai,i=i-1.判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項式的值V.程序框圖如下圖：程序：INPUTINPUTINPUTa ”n=; na”an=； aa ”x=; xf-n-lv=ai=n-1WHILE iP RINT> =0INPUT v=v*x+a i=i-1“ ”. i=; ia ”ai=; aWENDP RINT VEND，是一個典點評：本題是古老算法與現(xiàn)代計算機語言的完美結合，詳盡介紹了思

7、想方法、算法步驟、程序框圖和算法語句 型的算法案例.變式訓練請以5次多項式函數(shù)為例說明秦九韶算法，并畫出程序框圖.解： 設 f (x) =a5x5+a4x4+a3x3+a2x2+a1x+a0首先，讓我們以5次多項式一步步地進行改寫：f (x) = (a5X4+a4X3+a3X2+a2X+a1)x+ao=(a5x +a4x + a3x+a2)x+a1)x+a。=(a5x2+a4x+ a3)x+a2)x+a1) x+ao=(a5X+a4) x+ a3)x+a2)x+a1) x+ao.直到最外層的括號，然后加上面的分層計算，只用了小括號，計算時，首先計算最內(nèi)層的括號，然后由里向外逐層計算， 上常數(shù)項

8、即可.x(k結束/櫛Aj；屁屮沁口、/ irj = l,T nJ/箍【巾/程序框圖如下圖： 例2已知n次多項式Pn(x)=a oxn+a1xn-1 +an-1x+an，如果在一種算法中，計算(k=2 , 3, 4,，n)的值需要k - 1次乘法，計算 P3(x0)的值共需要9次運算(6 次乘法，3次加法)，那么計算P10(X0)的值共需要 次運算.下面給出一種減少運算次數(shù)的算法：P0(x)=a0,Pk+1(x)=xPk(x)+ak+1 (k= 0, 1, 2，n 1).利用該算法，計算P3(X0)的值共需要6次運算，計算P10(X0)的值共需要 次運算.答案：6520點評：秦九韶算法適用一般的

9、多項式一，加法最多n次.秦九韶算法通過轉(zhuǎn)化把乘法運算的次數(shù)減少到最多2例3 已知多項式函數(shù) f(x)=2x 5 5x4 4x3+3x2 6x+7，求當x=5 解析：把多項式變形為：f(x)=2x 5 5x4 4x3+3x2 6x+7 =(2x 5)x 4)x+3)x 6)x+7.計算的過程可以列表表示為：最后的系數(shù)2 677即為所求的值.算法過程：f(x)=anxn+an-1xn-1 +a1x+ao的求值問題.直接法乘法運算的次數(shù)最多可到達n次，加法最多n次.時的函數(shù)的值.0¥|05 540 "加/ I / 扌 / i T/ i5 2il IOS 5理 3 677*5V0=

10、2;vi=2 X5 5=5 ;V2=5 X5 4=21 ;V3=21 X5+3=108 ;V4=1O8 >5 6=534;V5=534 >5+7=2 677.點評：如果多項式函數(shù)中有缺項的話，要以系數(shù)為0的項補齊后再計算.知能訓練當x=2時，用秦九韶算法求多項式f(x)=3x 5+8x4-3x3+5x2+12x-6的值.解法一：根據(jù)秦九韶算法，把多項式改寫成如下形式：f(x)=(3x+8)x-3)x+5)x+12) x-6.x=2時的值.按照從內(nèi)到外的順序，依次計算一次多項式當vo=3;V1=vo ><2+8=3 ><2+8=14;V2=V1 ><

11、;2-3=14 >-3=25;V3=V2 ><2+5=25 >2+5=55;V4=V3 ><2+12=55 >+12=122;V5=V4 ><2-6=122 >-6=238.當x=2時，多項式的值為 238.解法二：f(x)=(3x+8)x-3)x+5)x+12) x-6,則 f(2)=(3 2+8) X2 3) >2+5) X2+12) > 6= 238.拓展提升用秦九韶算法求多項式 f(x)=7x 7+6x6+5x5+4x4+3x3+2x2+x當x=3時的值.解：f(x)=(7x+6)+5)x+4)x+3)x+2)x+

12、1)xvo=7 ;V1=7 X3+6=27;V2=27 X3+5=86;V3=86 X3+4=262 ;V4=262 X3+3=789 ;V5=789 X3+2=2 369;V6=2 369 X+1=7 108 ;V7=7 108 3+0=21 324. f(3)=21 324.課堂小結1. 秦九韶算法的方法和步驟.2. 秦九韶算法的計算機程序框圖.作業(yè)已知函數(shù) f(x)=x 3 2x2 5x+8,求 f(9)的值.解：f(x)=x 3 2x2 5x+8=(x 2 2x 5)x+8=(x 2)x 5)x+8 f(9)=(9 2) >9 5) >9+8=530.設計感想古老的算法散發(fā)

13、濃郁的現(xiàn)代氣息，這是一節(jié)充滿智慧的課.本節(jié)主要介紹了秦九韶算法 .通過對秦九韶算法的學習，對算法本身有哪些進一步的認識？ 教師引導學生思考、討論、概括，小結時要關注如下幾點：（ 1）算法具有通用的特點，可以解決一類問題； （ 2）解決同一類問題，可以有不同的算法，但計算的效率是不同的，應該選擇高效的算法；（ 3）算法的種類雖多，但三種邏輯結構可以有效地表達各種算法等等 .第 3 課時 案例 3 進位制導入新課情境導入 在日常生活中，我們最熟悉、最常用的是十進制，據(jù)說這與古人曾以手指計數(shù)有關，愛好天文學的古人也曾經(jīng)采用 七進制、十二進制、六十進制，至今我們?nèi)匀皇褂靡恢芷咛?、一年十二個月、一小時六

14、十分的歷法.今天我們來學習一下進位制 .推進新課新知探究提出問題（1）（2）（3）（4）活動： 先讓學生思考或討論后再回答，經(jīng)教師提示、點撥，對回答正確的學生及時表揚，對回答不準確的學生提示引導 考慮問題的思路討論結果： （1）進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的計數(shù)系統(tǒng)，約定滿二進一，就是二進制；滿十進一，就是十進制；滿 十二進一，就是十二進制；滿六十進一，就是六十進制等等.也就是說： “滿幾進一 ”就是幾進制，幾進制的基數(shù)（都是大于 1 的整數(shù)）就是幾 .（2）在日常生活中，我們最熟悉、最常用的是十進制，據(jù)說這與古人曾以手指計數(shù)有關，愛好天文學的古人也曾經(jīng)采 用七進制、十二進制、六十進制

15、，至今我們?nèi)匀皇褂靡恢芷咛臁⒁荒晔€月、一小時六十分的歷法 .（ 3）十進制使用 09 十個數(shù)字 .計數(shù)時，幾個數(shù)字排成一行，從右起，第一位是個位，個位上的數(shù)字是幾，就表示幾個一；第二位是十位，十位上的數(shù)字是幾，就表示幾個十；接著依次是百位、千位、萬位例如：十進制數(shù) 3 721中的 3 表示 3個千， 7 表示 7個百， 2表示 2個十， 1 表示 1個一.于是，我們得到下面的式子：3 721=3 >103+7 X1O2+2 XI01+1 X100.與十進制類似，其他的進位制也可以按照位置原則計數(shù)制用 0 和 1 兩個數(shù)字，七進制用 06 七個數(shù)字 .一般地，若 k 是一個大于 1 的

16、整數(shù)，那么以 k 為基數(shù)的 k 進制數(shù)可以表示為一串數(shù)字連寫在一起的形式anan-iaia0 （k） （Ov anv k, 0<a-i, ,ai, aov k）. 其他進位制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)的冪的乘積之和的形式，如 ii0 0ii（2）=iX25+iX24+0X23+0X22+iX2i+iX20，7 342（8）=7 X83+3 X82+4 X8i+2 X80. 非十進制數(shù)轉(zhuǎn)換為十進制數(shù)比較簡單，只要計算下面的式子值即可： anan-1 a iao（k）=anXkn+an-i >kn-1 +ai Xk+ao.第一步：從左到右依次取出k進制數(shù)anan-1aiao（k

17、）各位上的數(shù)字，乘以相應的k的幕，k的幕從n開始取值，每次遞減1，遞減到 0,艮卩 an>kn,an-i Xkn-1,，aXk,aoXk0； 第二步：把所得到的乘積加起來，所得的結果就是相應的十進制數(shù).（ 4）關于進位制的轉(zhuǎn)換，教科書上以十進制和二進制之間的轉(zhuǎn)換為例講解，并推廣到十進制和其他進制之間的轉(zhuǎn)換 樣做的原因是，計算機是以二進制的形式進行存儲和計算數(shù)據(jù)的，而一般我們傳輸給計算機的數(shù)據(jù)是十進制數(shù)據(jù)，因此 計算機必須先將十進制數(shù)轉(zhuǎn)換為二進制數(shù)，再處理，顯然運算后首次得到的結果為二進制數(shù)，同時計算機又把運算結果 由二進制數(shù)轉(zhuǎn)換成十進制數(shù)輸出 .1 °十進制數(shù)轉(zhuǎn)換成非十進制數(shù)把

18、十進制數(shù)轉(zhuǎn)換為二進制數(shù)，教科書上提供了 取余法 ”.2°非十進制之間的轉(zhuǎn)換你都了解哪些進位制？ 舉出常見的進位制 . 思考非十進制數(shù)轉(zhuǎn)換為十進制數(shù)的轉(zhuǎn)化方法 . 思考十進制數(shù)轉(zhuǎn)換成非十進制數(shù)及非十進制之間的轉(zhuǎn)換方法.由于每一種進位制的基數(shù)不同，所用的數(shù)字個數(shù)也不同.如二進.這除 2 取余法 ”，我們可以類比得到十進制數(shù)轉(zhuǎn)換成 k 進制數(shù)的算法 “除 k一個自然的想法是利用十進制作為橋梁.教科書上提供了一個二進制數(shù)據(jù)與16進制數(shù)據(jù)之間的互化的方法，也就是先由二進制數(shù)轉(zhuǎn)化為十進制數(shù)，再由十進制數(shù)轉(zhuǎn)化成為16進制數(shù).應用示例思路1例1把二進制數(shù)110 011 (2)化為十進制數(shù).解：110

19、 011(2)=1 X25+1 X24+O X23+0 X22+1 X21+1 X20=1 X32+1 X16+1 >2+1=51.點評：先把二進制數(shù)寫成不同位上數(shù)字與2的幕的乘積之和的形式，再按照十進制的運算規(guī)則計算出結果.變式訓練設計一個算法，把 k進制數(shù)a (共有n位)化為十進制數(shù) b.算法分析：從例1的計算過程可以看出，計算k進制數(shù)a的右數(shù)第i位數(shù)字4與ki-1的乘積ai ki-1，再將其累加，這是個重復操作的步驟.所以，可以用循環(huán)結構來構造算法.算法步驟如下：第一步，輸入a, k和n的值.第二步，將b的值初始化為0, i的值初始化為1.第三步，b=b+aiki-1, i=i+1

20、.第四步，判斷i>n是否成立.若是，則執(zhí)行第五步；否則，返回第三步第五步，輸出b的值.程序框圖如右圖：程序：INPUT “ a,k n= ”； a, k, nb=0i=1t=a MOD 10DO1 "b=b+t*kA (i-1)a=a10t=a MOD 10i=i+1LOOP UNTIL i > nP RINT bEND例2把89化為二進制數(shù).解：根據(jù)二進制數(shù) 滿二進一”的原則，可以用2連續(xù)去除89或所得商，然后取余數(shù).具體計算方法如下:因為 89=2X44+1 , 44=2X22+0 ,22=2 21+0,11=2 25+1 ,5=2 X2+1,2=2 X1+0,1=2

21、 >0+1,所以：89=2X (2X (2X (2X (2X2+1) +1) +0) +0) +1=2 X (2 X ( 2 X (2 X (22+1 ) +1) +0) +0) +1= =1 x2+0 X25+1 X24+1 X23+0 X22+0 X21+1 X20441號220211(5A3t21(01=1 011 001 (2).這種算法叫做除2取余法，還可以用下面的除法算式表示：把上式中各步所得的余數(shù)從下到上排列，得到89=1 011 001(2).上述方法也可以推廣為把十進制數(shù)化為k進制數(shù)的算法，稱為除k取余變式訓練設計一個程序，實現(xiàn)除k取余法”.算法分析：從例2的計算過程可

22、以看出如下的規(guī)律：若十制數(shù)a除以k所得商是q0,余數(shù)是r0,即a=k 0+r0,則m是a的k進制數(shù)的右數(shù)第1位數(shù).若qo除以k所得的商是qi，余數(shù)是門，即q0=k qi+門，則門是a的k進制數(shù)的左數(shù)第2位數(shù).若qn-1除以k所得的商是0，余數(shù)是rn,即qn-1=rn，貝U rn是a的k進制數(shù)的左數(shù)第1位數(shù). 這樣，我們可以得到算法步驟如下：第一步，給定十進制正整數(shù)a和轉(zhuǎn)化后的數(shù)的基數(shù) k.第二步，求出a除以k所得的商q,余數(shù)r.第三步，把得到的余數(shù)依次從右到左排列.第四步，若qMQ貝y a=q,返回第二步；否則，輸出全部余數(shù)r排列得到的k進制數(shù).程序框圖如右圖：程序：INPUT “a k= ”； a, kb=0i=0祀得和的余數(shù)依氏從蘇到攔打!和DOq=akr=a MOD k冷£b=b+r*10i/輸出全部余例得訓的£遲制數(shù)/i=i+1a=qLOOP UNTIL q=0P RINT bEND思路2例1將8進制數(shù)314 706(8)化為十進制數(shù)，并編寫出一個實現(xiàn)算法的程序解：314 706(8)=3 X85+1 X84+4 X83+7 X82+0 X81+6 X80=104 902.所以，化為十進制數(shù)是1