1.3

算法案例1/29第1課時輾轉相除法與更相減損術、秦九韶算法2/293/29一、輾轉相除法【問題思索】

1.在小課時,我們利用找條約數方法來求兩個正整數最大條約數.你能利用這種方法求出36與60最大條約數是多少嗎?提醒首先用兩個數公有質因數連續去除,一直除到所得商是互質數為止,然后把全部除數連乘起來即為最大條約數.因為4/292.假如兩個正整數條約數比較大,而且依據我們觀察又不能一下子得到它們條約數,我們又該怎樣求出它們最大條約數?比如,怎樣求出8251與6105最大條約數?觀察等式8251=6105×1+2146,你發覺8251與6105這兩個數條約數和6105與2146條約數有什么關系?提醒8251最大約數是2

146約數,一樣6

105與2

146條約數也是8

251約數,故8

251與6

105最大條約數也是6

105與2

146最大條約數.5/293.又6105=2146×2+1813,同理,6105與2146條約數和2146與1813條約數相等.重復上述操作,你能得到8251與6105這兩個數最大條約數嗎?提醒8251=6

105×1+2

146,6

105=2

146×2+1

813,2

146=1

813×1+333,1

813=333×5+148,333=148×2+37,148=37×4+0.最終除數37是148和37最大條約數,也是8

251與6

105最大條約數.6/294.填空:上述這種求兩個正整數最大條約數方法就是輾轉相除法,又叫歐幾里得算法,是一個求兩個正整數最大條約數古老而有效算法.其算法步驟以下:第一步,給定兩個正整數m,n.第二步,計算m除以n所得余數r.第三步,m=n,n=r.第四步,若r=0,則m,n最大條約數等于m;不然,返回第二步.5.做一做1:求667與928最大條約數.解:928=667×1+261,667=261×2+145,261=145×1+116,145=116×1+29,116=29×4,所以667與928最大條約數是29.

7/29二、更相減損術【問題思索】

1.設兩個不都是偶數正整數m,n(m>n),若m-n=k,則m與n最大條約數和n與k最大條約數相等,重復利用這個原理,可求得98與63最大條約數是多少?提醒98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7,∴98與63最大條約數為7.8/292.填空:上述求兩個正整數最大條約數方法稱為更相減損術.其算法步驟以下:第一步,任意給定兩個正整數,判斷它們是否都是偶數.若是,用2約簡;若不是,執行第二步.第二步,以較大數減去較小數,接著把所得差與較小數比較,并以大數減小數.繼續這個操作,直到所得差與減數相等為止,則這個數(等數)或這個數與約簡數乘積就是所求最大條約數.3.做一做2:342與589最大條約數為

.

解析:589-342=247,342-247=95,247-95=152,152-95=57,95-57=38,57-38=19,38-19=19.所以342與589最大條約數為19.答案:19

9/29三、秦九韶算法【問題思索】

1.已知多項式函數f(x)=x5+x4+x3+x2+x+1,當x=5時f(5)=55+54+53+52+5+1=3906.這種計算求值過程中乘法運算和加法運算次數分別是多少?提醒乘法運算10次,加法運算5次.2.假如我們把上述多項式函數解析式變形為f(x)=((((x+1)x+1)x+1)x+1)x+1,計算當x=5時f(5)值,再統計一下這種計算求值過程中乘法運算和加法運算次數分別是多少.提醒乘法運算4次,加法運算5次.10/293.填空:問題2中算法比問題1中算法少了6次乘法運算,大大簡化了運算過程.問題2中算法就叫秦九韶算法.普通地,f(x)=anxn+an-1xn-1+an-2xn-2+…+a1x+a0=(anxn-1+an-1xn-2+an-2xn-3+…+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.求多項式值時,首先計算最內層括號內一次多項式值,即v1=anx+an-1,然后由內向外逐層計算一次多項式值,即v2=v1x+an-2,v3=v2x+an-3,…,vn=vn-1x+a0,這么,求n次多項式f(x)值就轉化為求n個一次多項式值.

11/294.做一做3:用秦九韶算法求f(x)=2x3+x-3,當x=3時值v2=

.

解析:f(x)=((2x+0)x+1)x-3,v0=2;v1=2×3+0=6;v2=6×3+1=19.答案:1912/29思索辨析判斷以下說法是否正確,正確在后面括號內打“√”,錯誤打“×”.(1)輾轉相除法基本步驟是用較大數除以較小數.(

)(2)用更相減損術求294和84最大條約數時,需做減法次數是3.(

)(3)用秦九韶算法計算f(x)=3x6+4x5+5x4+6x3+7x2+8x+1當x=0.4時值,需要進行乘法運算和加法運算次數均為6.(

)(4)利用秦九韶算法求f(x)=1+2x+3x2+4x3+5x4+6x5當x=2時值時,先求6×2+5,第二步求2×(6×2+5)+4.(

)答案:(1)√

(2)×

(3)√

(4)√13/29探究一探究二思維辨析【例1】

求以下兩數最大條約數:(1)228與2223;(2)612與468.分析228與2

223相差較大,用輾轉相除法求最大條約數;612與468相差較小,用更相減損術求最大條約數.解:(1)用輾轉相除法求228與2

223最大條約數.2

223=228×9+171,228=171×1+57,171=57×3.所以228和2

223最大條約數為57.14/29探究一探究二思維辨析(2)首先612和468都是偶數,所以用2約簡,得到306和234,還是偶數,需要再用2約簡,得到153和117,最終用更相減損術計算.153-117=36,117-36=81,81-36=45,45-36=9,36-9=27,27-9=18,18-9=9.所以612和468最大條約數是9×2×2=36.15/29探究一探究二思維辨析反思感悟1.利用輾轉相除法求給定兩個數最大條約數,即利用帶余除法,用數對中較大數除以較小數,若余數不為零,則將余數和較小數組成新數對,再利用帶余除法,直到大數被小數除盡,這時較小數就是原來兩個數最大條約數.2.利用更相減損術求兩個正整數最大條約數時,首先判斷兩個正整數是否都是偶數.若是,用2約簡.也能夠不除以2,直接求最大條約數,這么不影響最終結果.3.當兩個整數差較大時,利用輾轉相除法計算次數較少.16/29探究一探究二思維辨析變式訓練1分別用輾轉相除法和更相減損術求779與209最大條約數.解:輾轉相除法:779=209×3+152,209=152×1+57,152=57×2+38,57=38×1+19,38=19×2.所以,779與209最大條約數為19.17/29探究一探究二思維辨析更相減損術:779-209=570,570-209=361,361-209=152,209-152=57,152-57=95,95-57=38,57-38=19,38-19=19.所以779和209最大條約數為19.18/29探究一探究二思維辨析【例2】

用秦九韶算法求多項式f(x)=7x7-6x6+4x4+3x3-2x2+x-5當x=3時值.分析解答本題時首先要將原多項式化成f(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+1)x-5形式,然后搞清v0,v1,v2,…,v7分別是多少,最終進行計算.19/29探究一探究二思維辨析解:f(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+1)x-5,v0=7,v1=7×3-6=15;v2=15×3+0=45;v3=45×3+4=139;v4=139×3+3=420;v5=420×3-2=1

258;v6=1

258×3+1=3

775;v7=3

775×3-5=11

320.∴當x=3時,多項式值為11

320.20/29探究一探究二思維辨析反思感悟利用秦九韶算法計算多項式值步驟

21/29探究一探究二思維辨析變式訓練2用秦九韶算法求多項式f(x)=2x4-6x3-5x2+4x-6在x=5時值.解:因為f(x)=2x4-6x3-5x2+4x-6=(((2x-6)x-5)x+4)x-6.依據秦九韶算法,我們有v0=2,v1=2x-6=2×5-6=4,v2=4x-5=4×5-5=15,v3=15x+4=15×5+4=79,v4=79x-6=79×5-6=389.22/29探究一探究二思維辨析用秦九韶算法求多項式值時忽略空項而致誤【典例】

已知f(x)=x5+x3+x2+x+1,用秦九韶算法求f(3)值.錯解因為f(x)=(((x+1)x+1)x+1)x+1,所以當x=3時,v0=1,v1=3+1=4,v2=4×3+1=13,v3=13×3+1=40,v4=40×3+1=120+1=121,所以當x=3時,f(3)=121.以上錯解中都有哪些錯誤?犯錯原因是什么?你怎樣訂正?你怎樣防范?錯因分析忽略了函數f(x)中x4項系數為0這一點,造成結果錯誤.23/29探究一探究二思維辨析正解原多項式可化為f(x)=((((x+0)x+1)x+1)x+1)x+1,當x=3時,v0=1,v1=1×3+0=3,v2=3×3+1=10,v3=10×3+1=31,v4=31×3+1=94,v5=94×3+1=283,所以,當x=3時,f(3)=283.防范辦法當多項式中間出現空項時,用秦九韶算法求函數值要補上系數為0對應項,即把這些項看成是0·xn.24/29探究一探究二思維辨析變式訓練用秦九韶算法求多項式f(x)=x5+0.11x3-0.15x-0.04當x=0.3時值.解:依據秦九韶算法,將f(x)改寫為f(x)=((((x+0)x+0.11)x+0)x-0.15)x-0.04.按照從內到外次序,依次計算一次多項式當x=0.3時值.v0=1,v1=v0×0.3+0=0.3,v2=v1×0.3+0.11=0.2,v3=v2×0.3+0=0.06,v4=v3×0.3-0.15=-0.132,v5=v4×0.3-0.04=-0.079

6.即x=0.3時,f(x)=x5+0.11x3-0.15x-0.04值為-0.079

6.25/2912341.用輾轉相除法求56與264最大條約數,需要做除法次數是(

)A.3 B.4 C.5 D.6解析:264=56×4+40,56=40×1+16,40=16×2+8,16=8×2.即最大條約數為8,做了4次除法,故選B.答案:B26/2912342.用更相減損術求123和48最大條約數是(

)A.3