高一數(shù)學(xué)人教A版必修3課件：1.3.1 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法

1、-1-1.3算法案例算法案例-2-第1課時(shí)輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航1.理解輾轉(zhuǎn)相除法與更相減損術(shù)的步驟,了解其執(zhí)行過程,并會(huì)求最大公約數(shù).2.掌握秦九韶算法,了解它提高計(jì)算效率的實(shí)質(zhì),并會(huì)求多項(xiàng)式的值.3.進(jìn)一步體會(huì)算法的基本思想.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航1.輾轉(zhuǎn)相除法與更相減損術(shù)(1)輾轉(zhuǎn)相除法.算法步驟:第一步,給定兩個(gè)正整數(shù)m,n.第二步,計(jì)算m除以n所得的余數(shù)r.第三步,m=n,n=r.第四步,

2、若r=0,則m,n的最大公約數(shù)等于m;否則,返回第二步.程序框圖:ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航程序: INPUTm,nDOr=m MOD nm=nn=rLOOP UNTILr=0PRINTmENDZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航(2)更相減損術(shù).算法分析:第一步,任意給定兩個(gè)正整數(shù),判斷它們是否都是偶數(shù).若是,用2約簡;若不是,執(zhí)行第二步.第二步,以較大的數(shù)減去較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作,直到所得的差與減數(shù)

3、相等為止,則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).【做一做1】 用更相減損術(shù)求156和48的最大公約數(shù)時(shí),第一步是.答案:用2約簡ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航2.秦九韶算法(1)概念:求多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0的值時(shí),常用秦九韶算法,這種算法的運(yùn)算次數(shù)較少,是多項(xiàng)式求值比較先進(jìn)的算法,其實(shí)質(zhì)是轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,共進(jìn)行n次乘法運(yùn)算和n次加法運(yùn)算.其過程是:改寫多項(xiàng)式為:f(x)=anxn+an-1xn-1+a1x+a0=(anxn-1+an-1xn-2+a1

4、)x+a0=(anxn-2+an-1xn-3+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0.設(shè)v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航(2)算法步驟:第一步,輸入多項(xiàng)式的次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值.第二步,將v的值初始化為an,將i的值初始化為n-1.第三步,輸入i次項(xiàng)的系數(shù)ai.第四步,v=vx+ai,i=i-1.第五步,判斷i是否大于或等于0.若是,則返回第三步;否則,輸出多項(xiàng)式的值v .Z

5、HISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航(3)程序框圖: ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航(4)程序: INPUT“n=”;nINPUT“an=”;aINPUT“x=”;xv=ai=n-1WHILEi=0PRINT“i=”;iINPUT“ai=”;av=v x+ai=i-1WENDPRINTvENDZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航【做一做2】 設(shè)計(jì)程序框圖,用秦九韶算法求多項(xiàng)式的值,所選用的

6、結(jié)構(gòu)是()A.順序結(jié)構(gòu) B.條件結(jié)構(gòu)C.循環(huán)結(jié)構(gòu) D.以上都有答案:DZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航1.更相減損術(shù)與輾轉(zhuǎn)相除法的區(qū)別與聯(lián)系剖析:如表所示.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航2.秦九韶算法是比較先進(jìn)的算法剖析:同一個(gè)問題有多種算法,如果某個(gè)算法比其他算法的步驟少,運(yùn)算的次數(shù)少,那么這個(gè)算法就是比較先進(jìn)的算法.判斷算法是否先進(jìn)的一個(gè)重要標(biāo)志就是運(yùn)算的次數(shù)越少越好.求多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0的值時(shí),通常是先計(jì)算

7、anxn,進(jìn)行n次乘法運(yùn)算;再計(jì)算an-1xn-1,進(jìn)行n-1次乘法運(yùn)算;這樣繼續(xù)下去但是用秦九韶算法時(shí),改寫多項(xiàng)式為f(x)=anxn+an-1xn-1+a1x+a0=(anxn-1+an-1xn-2+a1)x+a0=(anxn-2+an-1xn-3+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航先計(jì)算v1=anx+an-1,需1次乘法運(yùn)算,1次加法運(yùn)算;v2=v1x+an-2,需1次乘法運(yùn)算,1次加法運(yùn)算;vn=vn-1x+a0,需1次乘法運(yùn)算,1次加法

8、運(yùn)算.所以需進(jìn)行n次乘法運(yùn)算,n次加法運(yùn)算,共進(jìn)行2n次運(yùn)算.因此說秦九韶算法與其他算法相比運(yùn)算次數(shù)少,秦九韶算法是比較先進(jìn)的算法.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三【例1】 (1)用輾轉(zhuǎn)相除法求840與1 785的最大公約數(shù);(2)用更相減損術(shù)求612與468的最大公約數(shù).分析:本題是關(guān)于輾轉(zhuǎn)相除法和更相減損術(shù)的直接應(yīng)用.輾轉(zhuǎn)相除法的操作是較大的數(shù)除以較小的數(shù);更相減損術(shù)的操作是以大數(shù)減小數(shù).解:(1)用輾轉(zhuǎn)相除法求840和1 785的最大公約數(shù).1 785=8402+105,840=1058.所以840

9、和1 785的最大公約數(shù)是105.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三(2)首先612和468都是偶數(shù),所以用2約簡,得到306和234,還是偶數(shù),需要再用2約簡,得到153和117,最后用更相減損術(shù)計(jì)算得153-117=36, 117-36=81,81-36=45,45-36=9,36-9=27,27-9=18,18-9=9.所以612和468的最大公約數(shù)是922=36.反思求兩個(gè)正整數(shù)的最大公約數(shù)的問題,可以用輾轉(zhuǎn)相除法,也可以用更相減損術(shù).用輾轉(zhuǎn)相除法,即根據(jù)a=nb+r這個(gè)式子,反復(fù)相除,直到r=0為

10、止;用更相減損術(shù),即根據(jù)r=|a-b|這個(gè)式子,反復(fù)相減,直到r=0為止.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三【變式訓(xùn)練1】 求228與1 995的最大公約數(shù).解法一:(輾轉(zhuǎn)相除法)1 995=8228+171,228=1171+57,171=357,所以228與1 995的最大公約數(shù)為57.解法二:(更相減損術(shù))1 995-228=1 767,1 767-228=1 539,1 539-228=1 311,1 311-228=1 083,1 083-228=855,855-228=627,627-228=3

11、99,399-228=171,228-171=57,171-57=114,114-57=57.所以228與1 995的最大公約數(shù)為57.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三求多項(xiàng)式的值【例2】 用秦九韶算法求多項(xiàng)式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x當(dāng)x=3時(shí)的值.分析:解決本題首先需要將原多項(xiàng)式化成f(x)=(7x+6)x+5)x+4)x+3)x+2)x+1)x的形式,其次再弄清v0,v1,v2,v7分別是多少,再針對這些式子進(jìn)行計(jì)算.ZHISHISHULI知識(shí)梳理DIANLITOU

12、XI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三解:f(x)=(7x+6)x+5)x+4)x+3)x+2)x+1)x,所以有v0=7;v1=73+6=27;v2=273+5=86;v3=863+4=262;v4=2623+3=789;v5=7893+2=2 369;v6=2 3693+1=7 108;v7=7 1083=21 324.故當(dāng)x=3時(shí),多項(xiàng)式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x的值為21 324.反思秦九韶算法的關(guān)鍵在于把n次多項(xiàng)式轉(zhuǎn)化為一次多項(xiàng)式,注意體會(huì)遞推的實(shí)現(xiàn)過程,實(shí)施運(yùn)算時(shí)要由內(nèi)向外,一步一步執(zhí)行.ZHISHISHULI知

13、識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三【變式訓(xùn)練2】 用秦九韶算法求f(x)=3x5+8x4-3x3+5x2+12x-6當(dāng)x=2時(shí)的值.解:根據(jù)秦九韶算法,把多項(xiàng)式改寫成如下形式:f(x)=(3x+8)x-3)x+5)x+12)x-6,按照從內(nèi)到外的順序,依次計(jì)算一次多項(xiàng)式當(dāng)x=2時(shí)的值.v0=3,v1=v02+8=32+8=14,v2=v12-3=142-3=25,v3=v22+5=252+5=55,v4=v32+12=552+12=122,v5=v42-6=1222-6=238,所以當(dāng)x=2時(shí),多項(xiàng)式的值為238.ZHISHISH

14、ULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三易錯(cuò)辨析易錯(cuò)點(diǎn):利用秦九韶算法求含空項(xiàng)的n次多項(xiàng)式的值時(shí)易出現(xiàn)錯(cuò)誤【例3】 已知f(x)=3x4+2x2+4x+2,利用秦九韶算法求f(-2)的值.錯(cuò)解:f(x)=(3x2+2)x+4)x+2,v1=3(-2)2+2=14;v2=14(-2)+4=-24;v3=-24(-2)+2=50.故f(-2)=50.錯(cuò)因分析:所求f(-2)的值是正確的,但是錯(cuò)解中沒有抓住秦九韶算法原理的關(guān)鍵,正確改寫多項(xiàng)式,并使每一次計(jì)算只含有x的一次項(xiàng).ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析

15、ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三正解:f(x)=3x4+0 x3+2x2+4x+2=(3x+0)x+2)x+4)x+2,v1=3(-2)+0=-6;v2=-6(-2)+2=14;v3=14(-2)+4=-24;v4=-24(-2)+2=50.故f(-2)=50.反思利用秦九韶算法計(jì)算多項(xiàng)式的值的關(guān)鍵是能正確地將所給多項(xiàng)式改寫,依次計(jì)算一次多項(xiàng)式,由于后項(xiàng)計(jì)算用到前項(xiàng)的結(jié)果,故應(yīng)認(rèn)真、細(xì)心,確保中間結(jié)果的準(zhǔn)確性.若在多項(xiàng)式中有幾項(xiàng)不存在,可將這些項(xiàng)的系數(shù)看成0,即把這些項(xiàng)看成0 xn.ZHISHISHULI知識(shí)梳理DIANLITOUXI典例透析ZHONGNANJUJIAO重難聚焦目標(biāo)導(dǎo)航題型一題型二題型三【變式訓(xùn)練3】 用秦九韶算法求多項(xiàng)式f(x