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

§1.3算法案例第一課時(shí)輾轉(zhuǎn)相除法與更相減損術(shù)?秦九韶算法編輯ppt自學(xué)導(dǎo)引 1.理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義,了解執(zhí)行過程.2.掌握秦九韶算法的計(jì)算過程,了解它在數(shù)學(xué)計(jì)算中的應(yīng)用.3.進(jìn)一步體會(huì)算法的基本思想.編輯ppt課前熱身 1.輾轉(zhuǎn)相除法是用于求_____________________的一種方法,這種算法由歐幾里得在公元前300年左右首先提出,因而又叫________.2.所謂輾轉(zhuǎn)相除法,就是對于給定的兩個(gè)數(shù),用________除以________,若余數(shù)不為零,則將___________構(gòu)成新的一對數(shù),繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡,則這時(shí)________就是原來兩個(gè)數(shù)的最大公約數(shù).兩個(gè)正整數(shù)的最大公約數(shù)歐幾里得算法較大的數(shù)較小的數(shù)除數(shù)與余數(shù)除數(shù)編輯ppt3.更相減損術(shù)是我國古代數(shù)學(xué)專著__________中介紹的一種求兩數(shù)最大公約數(shù)的方法.其基本過程是:對于給定的兩數(shù),用___________,接著把所得的________與________比較,并以大數(shù)減小數(shù),繼續(xù)這個(gè)操作,直到所得的數(shù)________為止,則這個(gè)數(shù)就是所求的最大公約數(shù).4.秦九韶算法是我國南宋數(shù)學(xué)家________在他的代表作___________中提出的一種用于計(jì)算一元n次多項(xiàng)式的值的方法.《九章算術(shù)》大數(shù)減小數(shù)差減數(shù)相等秦九韶《數(shù)書九章》編輯ppt 名師講解1.輾轉(zhuǎn)相除法編輯ppt(1)輾轉(zhuǎn)相除的原理.設(shè)m,n是兩個(gè)整數(shù)(不妨設(shè)m>n),用m除以n,若商為q1,余數(shù)為r1(0≤r1<n),則m=n·q1+r1,顯然若x是m和n的公約數(shù),即x能整除m和n,則x也必然能整除r1,這樣x也是n和r1的公約數(shù),故求m和n的公約數(shù)就是求n和r1的公約數(shù);同理,用n除以r1,得n=r1·q2+r2(0≤r2<r1),所以n和r1的公約數(shù)就是r1和r2的公約數(shù),…,依次下去,由于m>n>r1>r2>…,所以到某一步必然有ri=ri+1·qi+2,即ri恰能被ri+1整除,這時(shí)ri+1是ri和ri+1的公約數(shù),它也必然是ri-1和ri,ri-2和ri-1,…,r1與r2,n和r1,m和n的最大公約數(shù).編輯ppt

(2)輾轉(zhuǎn)相除法的算法分析.由以上輾轉(zhuǎn)相除法的原理可以發(fā)現(xiàn),輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù),考慮到算法中的賦值語句可以對同一變量多次賦值,我們可以把較大的數(shù)用變量m表示,把較小的數(shù)用變量n表示,這樣式子m=n·q+r(0≤r<n)就是一個(gè)反復(fù)執(zhí)行的步驟,因此可以用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)算法.如上圖.編輯ppt(3)任何兩個(gè)數(shù),用輾轉(zhuǎn)相除法求其最大公約數(shù)的程序框圖.由于輾轉(zhuǎn)相除法總是用較大的數(shù)去除以較小的數(shù),所以首先要對一開始給定的兩數(shù)的大小進(jìn)行判斷,并將大數(shù)賦給m,小數(shù)賦給n,然后再執(zhí)行下面的過程.程序框圖如下圖所示:編輯ppt編輯ppt(4)輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)的程序設(shè)計(jì).INPUT“a,b”;a,bIFa<bTHENt=aa=bb=tENDIFr=aMODbWHILEr<>0a=bb=rr=aMODbWENDPRINTbEND編輯ppt2.更相減損術(shù)(1)更相減損術(shù)求兩數(shù)最大公約數(shù)的過程與算法設(shè)計(jì):對于給定的兩個(gè)數(shù),用較大的數(shù)減去較小的數(shù),接著把得到的差與較小的數(shù)比較,用這時(shí)兩個(gè)數(shù)中的較大的數(shù)減去較小的數(shù),繼續(xù)這樣的操作(大數(shù)減小數(shù)),直到所得的數(shù)相等為止,那么這個(gè)數(shù)(等數(shù))就是所求的最大公約數(shù).顯然,上述過程中大數(shù)減去小數(shù)是一個(gè)重復(fù)執(zhí)行的過程,因此只需將大數(shù)賦給變量m,小數(shù)賦給變量n,那么m-n就可以通過循環(huán)結(jié)構(gòu)實(shí)現(xiàn)算法.編輯ppt(2)更相減損術(shù)求最大公約數(shù)的程序設(shè)計(jì):INPUT“a,b”;a,bWHILEa<>bIFa>bTHENa=a-bELSEb=b-aENDIFWENDPRINTaEND編輯ppt3.秦九韶算法(1)秦九韶算法過程分析:設(shè)Pn(x)=anxn+an-1xn-1+…+a1x+a0,將其改寫為Pn(x)=(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令vk=(…((anx+an-1)x+an-2)x+…+an-(k-1))x+an-k,編輯ppt這樣我們便可由a0依次求出v1,v2,…,vn:v1=v0x+an-1,v2=v1x+an-2,v3=v2x+an-3,…,vn=vn-1x+a0.顯然,用秦九韶算法求n次多項(xiàng)式的值時(shí)只需做n次乘法和n次加法運(yùn)算.編輯ppt

(2)秦九韶算法程序框圖:以5次多項(xiàng)式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)x=x0時(shí)為例,如下圖:編輯ppt編輯ppt典例剖析 題型一求兩個(gè)數(shù)的最大公約數(shù)編輯ppt例1:分別用輾轉(zhuǎn)相除法和更相減損術(shù)逐步列出求(1)98和63;(2)8251和6105的最大公約數(shù)的步驟,你有什么發(fā)現(xiàn)?對優(yōu)劣作出評判.分析:輾轉(zhuǎn)相除法是做兩個(gè)數(shù)的帶余除法,更相減損術(shù)是做兩個(gè)數(shù)的減法.編輯ppt解:(1)98和63輾轉(zhuǎn)相除法S198=63×1+35,S263=35×1+28,S335=28×1+7,S428=4×7,最大公約數(shù)為7.編輯ppt更相減損術(shù)S198-63=35,S263-35=28,S335-28=7,S428-7=21,S521-7=14,S614-7=7,故98和63的最大公約數(shù)為7.編輯ppt

(2)8251和6105輾轉(zhuǎn)相除法S18251=6105×1+2146,S26105=2146×2+1813,S32146=1813×1+333,S41813=333×5+148,S5333=148×2+37,S6148=37×4,最大公約數(shù)為37.編輯ppt輾轉(zhuǎn)相除法和更相減損術(shù)本質(zhì)是一致的,除法運(yùn)算若用加法與減法運(yùn)算定義,x(x≥0)除以y(y>0)就是從x中一次又一次地減去y,直至x<y為止.所減的次數(shù)即為商,所減的余數(shù)就是所求余數(shù).編輯ppt更相減損術(shù)S18251-6105=2146,S26105-2146=3959,S33959-2146=1813,S42146-1813=333,S51813-333=1480,S61480-333=1147,S71147-333=814,編輯pptS8814-333=481,S9481-333=148,S10333-148=185,S11185-148=37,S12148-37=111,S13111-37=74,S1474-37=37,最大公約數(shù)為37.因此(1)中S428=4×7可作四次減法,即28中可減4次7.編輯ppt

(2)中S41813=333×5+148在1813中可減5次333.從形式上看更相減損術(shù)比輾轉(zhuǎn)相除法復(fù)雜,但計(jì)算機(jī)更“喜歡”做加減法.加減法比乘除法快幾百倍.變式訓(xùn)練1:用輾轉(zhuǎn)相除法求80和36的最大公約數(shù),并用更相減損術(shù)檢驗(yàn)所得結(jié)果.分析:將80作為大數(shù),36作為小數(shù),執(zhí)行輾轉(zhuǎn)相除法和更相減損術(shù)的步驟即可.編輯ppt解:用輾轉(zhuǎn)相除法:80=36×2+8,36=8×4+4,8=4×2+0.故80和36的最大公約數(shù)是4.用更相減損術(shù)檢驗(yàn):80-36=44,編輯ppt44-36=8,36-8=28,28-8=20,20-8=12,12-8=4,8-4=4.∴80和36的最大公約數(shù)是4.編輯ppt題型二求三個(gè)數(shù)的最大公約數(shù)例2:求三個(gè)數(shù)175?100?75的最大公約數(shù).分析:求三個(gè)數(shù)的最大公約數(shù)時(shí),可以先求出其中兩個(gè)數(shù)的最大公約數(shù),用這個(gè)最大公約數(shù)再與第三個(gè)數(shù)求最大公約數(shù),所得結(jié)果就是這三個(gè)數(shù)的最大公約數(shù).編輯ppt解:解法1(輾轉(zhuǎn)相除法):先求175與100的最大公約數(shù):175=100×1+75,100=75×1+25,75=25×3.∴175與100的最大公約數(shù)是25.以下再求25與75的最大公約數(shù):75=25×3∴25和75的最大公約數(shù)是25.故25是75和25的最大公約數(shù),也就是175?100?75的最大公約數(shù).編輯ppt解法2(更相減損術(shù)):第一步:先從較大數(shù)中減去較小的數(shù):175-100=75,100-75=25,得75,25,75;第二步:重復(fù)上面的算法:75-25×2=25,75-2×25=25,得25,25,25.∵25,25,25的最大公約數(shù)為25.∴三個(gè)數(shù)175,100,75的最大公約數(shù)為25.編輯ppt注:解法2的過程可簡記為(175,100,75)=(175-100,100-75,75)=(75,25,75)=(75-2×25,25,75-25×2)=(25,25,25)∴三個(gè)數(shù)175,100,25的最大公約數(shù)為25.規(guī)律技巧:本題的解法可以推廣到求多個(gè)數(shù)的最大公約數(shù),只需依次計(jì)算即可.編輯ppt變式訓(xùn)練2:求三個(gè)數(shù)324,243,108的最大公約數(shù).解:解法1:先求324與243的最大公約數(shù),324=243×1+81,243=81×3,∴324與243的最大公約數(shù)為81.下面再求108與81的最大公約數(shù):108=81+27,81=27×3.∴108與81的最大公約數(shù)是27.故324,243,108的最大公約數(shù)為27.編輯ppt解法2:(324,243,108)=(324-243,243-108,108)=(81,135,108)=(81,135-108,108-81)=(81,27,27)=(81-2×27,27,27)=(27,27,27).∴三個(gè)數(shù)324,243,108的最大公約數(shù)為27.編輯ppt題型三秦九韶算法的應(yīng)用例3:用秦九韶算法求多項(xiàng)式f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在x=-0.2的值.分析:可根據(jù)秦九韶算法原理,將所給多項(xiàng)式改寫,然后由內(nèi)到外逐次計(jì)算即可.編輯ppt解:f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5=((((0.00833x+0.04167)x+0.16667)x+0.5)x+1)x+1.而x=-0.2,所以有v0=a5=0.00833,v1=v0x+a4=0.04,v2=v1x+a3=0.15867,v3=v2x+a2=0.46826,v4=v3x+a1=0.90635,v5=v4x+a0=0.81873.即f(-0.2)=0.81873.編輯ppt誤區(qū)警示:利用秦九韶算法計(jì)算多項(xiàng)式值關(guān)鍵是能正確地將所給多項(xiàng)式改寫,然后由內(nèi)向外逐次計(jì)算,由于后項(xiàng)計(jì)算需用到前項(xiàng)的結(jié)果,故應(yīng)認(rèn)真?細(xì)心,確保中間結(jié)果的準(zhǔn)確性.編輯ppt變式訓(xùn)練3:已知f(x)=x5-4x4+2x2-5x+1,求f(3)的值.解:f(x)=x5-4x4+0\5x3+2x2-5x+1=(x4-4x3+0\5x2+2x-5)x+1=((x3-4x2+0\5x+2)x-5)x+1=(((x2-4x+0)x+2)x-5)x+1=((((x-4)x+0)x+2)x-5)x+1.編輯ppt∵x=3,∴v0=a5=1;v1=1×3-4=-1;v2=-1×3+0=-3;v3=-3×3+2=-7;v4=-7×3-5=-26;v5=-26×3+1=-77.∴f(3)=-77.

編輯ppt技能演練 基礎(chǔ)強(qiáng)化

編輯ppt1.用輾轉(zhuǎn)相除法求294和84的最大公約數(shù)時(shí),需要做除法的次數(shù)是()A.1 B.2C.3 D.4解析:294=84×3+42,84=42×2.故需做2次除法.答案:B編輯ppt2.兩個(gè)整數(shù)490和910的最大公約數(shù)是()A.2 B.10C.30 D.70解析:910=91×10,490=49×10,∵91=49×1+42,49=42×1+7,42=7×6.∴91與49的最大公約數(shù)為7.故910與490的最大公約數(shù)為70.答案:D編輯ppt3.用秦九韶算法計(jì)算多項(xiàng)式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1當(dāng)x=0.4時(shí)的值時(shí),需要做乘法和加法的次數(shù)分別是()A.6,6B.5,6C.5,5D.6,5解析:∵f(x)的最高次項(xiàng)為3x6,共含有7項(xiàng),∴用秦九韶算法求x=0.4時(shí)的值時(shí),需作乘法和加法各6次.答案:A編輯ppt4.用更相減損術(shù)求459和357的最大公約數(shù),需作減法的次數(shù)為()A.4B.5C.6D.7解析:459-357=102;357-102=255;255-102=153;153-102=51;102-51=51.共作了5次減法.答案:B編輯ppt5.378與90的最大公約數(shù)為________.解析:378=90×4+18;90=18×5.∴378與90的最大公約數(shù)是18.答案:18編輯ppt6.用秦九韶算法求多項(xiàng)式f(x)=x4-2x3+3x2-7x-5當(dāng)x=4時(shí)的值,給出如下數(shù)據(jù):①0②2③11④37⑤143其運(yùn)算過程中(包括最終結(jié)果)會(huì)出現(xiàn)的數(shù)有________(只填序號).答案:②③④⑤編輯ppt解析:將多項(xiàng)式寫成f(x)=(((x-2)x+3)x-7)x-5.其中v0=a4=1;v1=1×4-2=2;v2=2×4+3=11;v3=11×4-7=37;v4=37×4-5=143.編輯ppt解析:由秦九韶算法知,應(yīng)填an-k.在程序中可以用循環(huán)語句來實(shí)現(xiàn).答案:an-k循環(huán)編輯ppt8.請將以下用“更相減損術(shù)”求兩個(gè)正整數(shù)a,b的最大公約數(shù)的程序補(bǔ)充完整:INPUTaINPUTbWHILEa<>bIFa>bTHENa=a-bELSE編輯ppt___________ENDIFWENDPRINTaEND解析:閱讀程序知,當(dāng)a>b時(shí),作減法a-b,當(dāng)a<b時(shí),作減法b-a,因此應(yīng)填b=b-a.答案:b=b-a編輯ppt能力提升9.用秦九韶算法求多項(xiàng)式f(x)=8x7+5x6+3x4+2x+1當(dāng)x=2時(shí)的值.分析:注意本題中有幾項(xiàng)不存在,此時(shí)在計(jì)算時(shí),我們應(yīng)該將這些項(xiàng)加上,比如含x3這一項(xiàng)可看做0·x3.編輯ppt解:根據(jù)秦九韶算法,把多項(xiàng)式改寫成如下形式:f(x)=8x7+5x6+0·x5+3x4+0·x3+0·x2+2x+1=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1.而x=2,所以有v0=8v1=8×2+5=21,v2=21×2+0=42,v3