時(shí)輾轉(zhuǎn)相除法與更相減損術(shù)秦九韶算法學(xué)習(xí)教案

1、會計(jì)學(xué)1時(shí)輾轉(zhuǎn)相除法時(shí)輾轉(zhuǎn)相除法(chf)與更相減損術(shù)秦九韶算與更相減損術(shù)秦九韶算法法第一頁，共33頁。1. 回顧算法的三種表述：回顧算法的三種表述：自然語言自然語言程序框圖（三種邏輯結(jié)構(gòu)程序框圖（三種邏輯結(jié)構(gòu)(jigu)）程序語言（五種基本語句）程序語言（五種基本語句）第1頁/共33頁第二頁，共33頁。2.思考：思考：小學(xué)學(xué)過的求兩個(gè)數(shù)最大公約數(shù)的方法小學(xué)學(xué)過的求兩個(gè)數(shù)最大公約數(shù)的方法(fngf)？先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.第2頁/共33頁第三頁，共

2、33頁。輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 （歐幾里得算法）（歐幾里得算法）思考思考(sko)1:求兩個(gè)正整數(shù)的最大公約數(shù)求兩個(gè)正整數(shù)的最大公約數(shù)（1）求）求25和和35的最大公約數(shù)的最大公約數(shù)（2）求）求49和和63的最大公約數(shù)的最大公約數(shù)25（1） 5535749（2） 77639所以所以(suy)(suy)，2525和和3535的最大公約數(shù)為的最大公約數(shù)為5.5.所以所以(suy)(suy)，4949和和6363的最大公約數(shù)為的最大公約數(shù)為7.7.除了用這種方法外還有沒有其他方法？除了用這種方法外還有沒有其他方法？第3頁/共33頁第四頁，共33頁。思考思考2：算出：算出8251和和6105的最大公約數(shù)

3、的最大公約數(shù).第一步：用兩數(shù)中較大第一步：用兩數(shù)中較大(jio d)的數(shù)除以較小的數(shù)，求得商和余數(shù)的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論：結(jié)論：8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(shù)，求8251和和6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公約數(shù)就可以了的公約數(shù)就可以了.第二步：對第二步：對6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)的最大公約數(shù).為什么？為什么？

4、第4頁/共33頁第五頁，共33頁。完整完整(wnzhng)的過程的過程:8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0 顯然顯然(xinrn)37是是148和和37的最大公約數(shù)，也就是的最大公約數(shù)，也就是8251和和6105的最大公約數(shù)的最大公約數(shù).第5頁/共33頁第六頁，共33頁。例例1 用輾轉(zhuǎn)相除法用輾轉(zhuǎn)相除法(chf)求求225和和135的最大公約數(shù)的最大公約數(shù).顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是225和和135的最大公約數(shù)的最大公約數(shù). 22

5、5=1351+90135=901+4590=452第6頁/共33頁第七頁，共33頁。思考思考3：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？S1：用大數(shù)：用大數(shù)(d sh)除以小數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)：重復(fù)S1，直到余數(shù)為，直到余數(shù)為0思考思考4：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu). 第7頁/共33頁第八頁，

6、共33頁。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=nm=nq qr r用程序框圖表示用程序框圖表示(biosh)出右邊的過程出右邊的過程r=m MOD nm = nn = rr=0?是是否否第8頁/共33頁第九頁，共33頁。輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法(chf)（歐幾里得算法）（歐幾里得算法）（1）算理：所謂輾轉(zhuǎn)相除法）算理：所謂輾轉(zhuǎn)相除法(chf)，就是對于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)，就是對于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù).若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的

7、一對數(shù)，繼續(xù)上面的除法若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法(chf)，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù).第9頁/共33頁第十頁，共33頁。（2 2）算法步驟）算法步驟第一步：輸入兩個(gè)正整數(shù)第一步：輸入兩個(gè)正整數(shù)m,n(mn).m,n(mn).第二步：計(jì)算第二步：計(jì)算m m除以除以n n所得的余數(shù)所得的余數(shù)r.r.第三步：第三步：m=n,n=r.m=n,n=r.第四步：若第四步：若r r0,0,則則m,nm,n的最大公約數(shù)等于的最大公約數(shù)等于(dngy)m(dngy)m； 否則轉(zhuǎn)到

8、第二步否則轉(zhuǎn)到第二步. . 第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)m.m.第10頁/共33頁第十一頁，共33頁。（3 3）程序框圖）程序框圖（4 4）程序）程序(chngx)(chngx)INPUT “m,n=”;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否第11頁/共33頁第十二頁，共33頁。更相減損術(shù)更相減損術(shù) 算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之算理：可半者半之，不可半者，副置分母、子之

9、數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之.第一步：任意給定兩個(gè)正整數(shù)，判斷他們是否都是偶數(shù)第一步：任意給定兩個(gè)正整數(shù)，判斷他們是否都是偶數(shù).若是，則用若是，則用2約簡；若不是則執(zhí)行第二步約簡；若不是則執(zhí)行第二步.第二步：以較大的數(shù)減較小的數(shù)，接著第二步：以較大的數(shù)減較小的數(shù)，接著(ji zhe)把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)或其與約簡的數(shù)的乘積就是所求的最大公約數(shù)繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)或其與約簡的數(shù)的乘積就是所求的最大公約數(shù).第12頁/共33頁第十三頁，共3

10、3頁。更相減損術(shù)更相減損術(shù)（1）算理：所謂更相減損術(shù)，就是對于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成）算理：所謂更相減損術(shù)，就是對于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成(guchng)新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(shù)的最大公約數(shù)新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(shù)的最大公約數(shù).第13頁/共33頁第十四頁，共33頁。（2 2）算法步驟）算法步驟第一步：輸入兩個(gè)正整數(shù)第一步：輸入兩個(gè)正整數(shù)a,b(ab);a,b(a

11、b);第二步：若第二步：若a a不等于不等于b ,b ,則執(zhí)行則執(zhí)行(zhxng)(zhxng)第三步；否則轉(zhuǎn)到第五步；第三步；否則轉(zhuǎn)到第五步；第三步：把第三步：把a(bǔ)-ba-b的差賦予的差賦予r;r;第四步：如果第四步：如果br, br, 那么把那么把b b賦給賦給a,a,把把r r賦給賦給b;b;否則把否則把r r賦給賦給a a，執(zhí)行，執(zhí)行(zhxng)(zhxng)第二步；第二步；第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)b.b.第14頁/共33頁第十五頁，共33頁。（3 3）程序框圖）程序框圖開始開始輸入輸入m，nnk？m=n是是輸出輸出m結(jié)束結(jié)束mn？k=m-n是是否否n=km=k否

12、否第15頁/共33頁第十六頁，共33頁。（4 4）程序）程序(chngx)(chngx)INPUT “a,b=“;a,bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND第16頁/共33頁第十七頁，共33頁。例例2 用更相減損術(shù)求用更相減損術(shù)求98與與63的最大公約數(shù)的最大公約數(shù)解：由于解：由于63不是偶數(shù)，把不是偶數(shù)，把98和和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721217141477所以所以(suy)，98和和63的最大公約數(shù)等于的最大公約數(shù)等于7 第17頁

13、/共33頁第十八頁，共33頁。秦九韶算法的基本思想秦九韶算法的基本思想對于求對于求n次多項(xiàng)式的值，在我國古代數(shù)學(xué)中有一個(gè)優(yōu)秀算法，即秦九韶算法，我們將對這個(gè)算法作些了解和探究次多項(xiàng)式的值，在我國古代數(shù)學(xué)中有一個(gè)優(yōu)秀算法，即秦九韶算法，我們將對這個(gè)算法作些了解和探究(tnji).思考思考1:對于多項(xiàng)式對于多項(xiàng)式f(x)=x5+x4+x3+x2+x+1，求，求f(5)的值的值. 若先計(jì)算各項(xiàng)的值，然后再相加，那么一共要做多少次乘法運(yùn)算和多少次加法運(yùn)算？若先計(jì)算各項(xiàng)的值，然后再相加，那么一共要做多少次乘法運(yùn)算和多少次加法運(yùn)算？4+3+2+1=10次乘法運(yùn)算，次乘法運(yùn)算，5次加法運(yùn)算次加法運(yùn)算. 第1

14、8頁/共33頁第十九頁，共33頁。思考思考2:在上述問題中，若先計(jì)算在上述問題中，若先計(jì)算x2的值，然后的值，然后(rnhu)依次計(jì)算依次計(jì)算x2x，(x2x)x，(x2x)x)x的值，這樣每次都可以利用上一次計(jì)算的結(jié)果，再將這些數(shù)與的值，這樣每次都可以利用上一次計(jì)算的結(jié)果，再將這些數(shù)與x和和1相加，那么一共做了多少次乘法運(yùn)算和多少次加法運(yùn)算？相加，那么一共做了多少次乘法運(yùn)算和多少次加法運(yùn)算？ 4次乘法運(yùn)算，次乘法運(yùn)算，5次加法運(yùn)算次加法運(yùn)算. 第19頁/共33頁第二十頁，共33頁。思考思考(sko)3:利用后一種算法求多項(xiàng)式利用后一種算法求多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+

15、a0的值，這個(gè)多項(xiàng)式應(yīng)寫成哪種形式？的值，這個(gè)多項(xiàng)式應(yīng)寫成哪種形式？f(x)=anxn+an-1xn-1+a1x+a0 =(anxn-1+an-1xn-2+a2x+a1)x+a0=(anxn-2+an-1xn-3+a2)x+a1)x+a0 =(anx+an-1)x+an-2)x+a1)x+a0.第20頁/共33頁第二十一頁，共33頁。思考思考(sko)4:對于對于f(x)=(anx+an-1)x+an-2)x+a1)x+a0，由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟如何？，由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟如何？第一步第一步:計(jì)算計(jì)算v1=anx+an-1. 第二步第二步:計(jì)算計(jì)算v

16、2=v1x+an-2.第三步第三步:計(jì)算計(jì)算v3=v2x+an-3. 第第n步步:計(jì)算計(jì)算vn=vn-1x+a0.第21頁/共33頁第二十二頁，共33頁。思考思考5:上述求多項(xiàng)式上述求多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0的值的方法稱為秦九韶算法，利用的值的方法稱為秦九韶算法，利用(lyng)該算法求該算法求f(x0)的值，一共需要多少次乘法運(yùn)算，多少次加法運(yùn)算？的值，一共需要多少次乘法運(yùn)算，多少次加法運(yùn)算？思考思考6:在秦九韶算法中，記在秦九韶算法中，記v0=an，那么第，那么第k步的算式是什么？步的算式是什么？vk=vk-1x+an-k (k=1，2，n)第22頁/共33

17、頁第二十三頁，共33頁。秦九韶算法的程序設(shè)計(jì)秦九韶算法的程序設(shè)計(jì) 思考思考1:用秦九韶算法求多項(xiàng)式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？用秦九韶算法求多項(xiàng)式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？第一步第一步:輸入多項(xiàng)式的次數(shù)輸入多項(xiàng)式的次數(shù)n，最高次項(xiàng)的系數(shù)，最高次項(xiàng)的系數(shù)an和和x的值的值. 第二步第二步:令令v=an，i=n-1. 第三步第三步:輸入輸入i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)ai. 第四步第四步:v=vx+ai，i=i-1.第五步第五步:判斷判斷i0是否成立是否成立(chngl).若是，則返回第三步；否則，輸出多項(xiàng)式的值若是，則返回第三步；否則，輸出多項(xiàng)

18、式的值v. 第23頁/共33頁第二十四頁，共33頁。思考思考2:該算法的程序框圖如何該算法的程序框圖如何(rh)表示？表示？開始開始輸入輸入n，an，x的值的值v=anv=vx+ai輸入輸入aii0？i=n-1i=i-1結(jié)束結(jié)束是是 輸出輸出v 否否第24頁/共33頁第二十五頁，共33頁。思考思考(sko)3:該程序框圖對應(yīng)的程序如何表述？該程序框圖對應(yīng)的程序如何表述？開始開始輸入輸入n，an，x的的值值v=anv=vx+ai輸入輸入aii0？i=n-1i=i-1結(jié)束結(jié)束是是輸出輸出v 否否INPUT “n=”；nINPUT “an =”；aINPUT “x=”；x v=a i=n-1WHIL

19、E i=0 PRINT “i=”;i INPUT “ai=”；a v=v*x+a i=i-1WENDPRINT vEND第25頁/共33頁第二十六頁，共33頁。例例3 已知一個(gè)已知一個(gè)(y )5次多項(xiàng)式為次多項(xiàng)式為f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8 用秦九韶算法求用秦九韶算法求f(5)的值的值.f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=45+2=22；v2=225+3.5=113.5；v3=113.55-2.6=564.9；v4=564.95+1.7=2826.2；v5=2826.25-0.8=14130.2.所以所以f(5)=

20、14130.2.第26頁/共33頁第二十七頁，共33頁。例例4 閱讀下列程序，說明閱讀下列程序，說明(shumng)它解決的實(shí)際問題是什么？它解決的實(shí)際問題是什么？求多項(xiàng)式求多項(xiàng)式 f(x)=1+2x+3x2+4x3+5x4在在x=a時(shí)的值時(shí)的值. INPUT “x=”；an=0y=0WHILE n5 y=y+(n+1)*an n=n+1WENDPRINT yEND第27頁/共33頁第二十八頁，共33頁。1.利用輾轉(zhuǎn)利用輾轉(zhuǎn)(zhnzhun)相除法求兩數(shù)相除法求兩數(shù)4081與與20723的最大公約數(shù)的最大公約數(shù).20723=40815+318;4081=31812+265;318=2651+53;265=535+0. (53)(53)第28頁/共33頁第二十九頁，共33頁。2.用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解解:首先將原多項(xiàng)式改寫成如下形式首先將原多項(xiàng)式改寫成如下形式(xngsh) : f(x)=(2x-5)x-4)x+3)x-6)x+7然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即即v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=