1、1.3 算法案例 第1課時 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法,1.理解輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法中蘊含的數(shù)學原理，并能根據(jù)這些原理進行算法分析，解決一些與其相關(guān)的問題； 2.能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序框圖并寫出算法程序.,1. 回顧算法的三種表述： 自然語言 程序框圖（三種邏輯結(jié)構(gòu)） 程序語言（五種基本語句）,2.思考： 小學學過的求兩個數(shù)最大公約數(shù)的方法？ 先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.,輾轉(zhuǎn)相除法 （歐幾里得算法） 思考1:求兩個正整數(shù)的最大公約數(shù) （1）求25和35的最大公約數(shù) （2）求49和63的最大公

2、約數(shù),所以，25和35的最大公約數(shù)為5.,所以，49和63的最大公約數(shù)為7.,除了用這種方法外還有沒有其他方法？,思考2：算出8251和6105的最大公約數(shù). 第一步：用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146 結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了. 第二步：對6105和2146重復第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù).,為什么？,完整的過程:,8251=61051+2146,6105=2

3、1462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù).,例1 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù). 顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù).,225=1351+90,135=901+45,90=452,思考3：從上面的兩個例子可以看出計算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù) S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù) S3：重復S1，直到余數(shù)為0 思考4：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等

4、于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu).,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,m=nqr,用程序框圖表示出右邊的過程,r=m MOD n,m = n,n = r,r=0?,是,否,輾轉(zhuǎn)相除法（歐幾里得算法） （1）算理：所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù).若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù).,（2）算法步驟 第一步：輸入兩個正整數(shù)m,n(mn). 第二

5、步：計算m除以n所得的余數(shù)r. 第三步：m=n,n=r. 第四步：若r0,則m,n的最大公約數(shù)等于m； 否則轉(zhuǎn)到第二步. 第五步：輸出最大公約數(shù)m.,（3）程序框圖,（4）程序,INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,更相減損術(shù) 算理：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之. 第一步：任意給定兩個正整數(shù)，判斷他們是否都是偶數(shù).若是，則用2約簡；若不是則執(zhí)行第二步. 第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的

6、減數(shù)和差相等為止，則這個等數(shù)或其與約簡的數(shù)的乘積就是所求的最大公約數(shù).,更相減損術(shù) （1）算理：所謂更相減損術(shù)，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù).,（2）算法步驟 第一步：輸入兩個正整數(shù)a,b(ab); 第二步：若a不等于b ,則執(zhí)行第三步；否則轉(zhuǎn)到第五步； 第三步：把a-b的差賦予r; 第四步：如果br, 那么把b賦給a,把r賦給b;否則把r賦給a，執(zhí)行第二步； 第五步：輸出最大公約數(shù)b.,（3）程序框圖,（4）程序,INPUT “a,b=“

7、;a,b WHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IF WEND PRINT b END,例2 用更相減損術(shù)求98與63的最大公約數(shù) 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721 21714 1477 所以，98和63的最大公約數(shù)等于7,秦九韶算法的基本思想 對于求n次多項式的值，在我國古代數(shù)學中有一個優(yōu)秀算法，即秦九韶算法，我們將對這個算法作些了解和探究. 思考1:對于多項式f(x)=x5+x4+x3+x2+x+1，求f(5)的值. 若先計算各項的值，然后再相加，那么一共要做多少

8、次乘法運算和多少次加法運算？ 4+3+2+1=10次乘法運算，5次加法運算.,思考2:在上述問題中，若先計算x2的值，然后依次計算x2x，(x2x)x，(x2x)x)x的值，這樣每次都可以利用上一次計算的結(jié)果，再將這些數(shù)與x和1相加，那么一共做了多少次乘法運算和多少次加法運算？ 4次乘法運算，5次加法運算.,思考3:利用后一種算法求多項式f(x)=anxn+an-1xn-1 +a1x+a0的值，這個多項式應寫成哪種形式？ 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

9、= =(anx+an-1)x+an-2)x+a1)x+a0.,思考4:對于f(x)=(anx+an-1)x+an-2)x+a1)x+a0，由內(nèi)向外逐層計算一次多項式的值，其算法步驟如何？ 第一步:計算v1=anx+an-1. 第二步:計算v2=v1x+an-2. 第三步:計算v3=v2x+an-3. 第n步:計算vn=vn-1x+a0.,思考5:上述求多項式f(x)=anxn+an-1xn-1+a1x+a0的值的方法稱為秦九韶算法，利用該算法求f(x0)的值，一共需要多少次乘法運算，多少次加法運算？ 思考6:在秦九韶算法中，記v0=an，那么第k步的算式是什么？ vk=vk-1x+an-k (

10、k=1，2，n),秦九韶算法的程序設(shè)計 思考1:用秦九韶算法求多項式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？ 第一步:輸入多項式的次數(shù)n，最高次項的系數(shù)an和x的值. 第二步:令v=an，i=n-1. 第三步:輸入i次項的系數(shù)ai. 第四步:v=vx+ai，i=i-1. 第五步:判斷i0是否成立.若是，則返回第三步；否則，輸出多項式的值v.,思考2:該算法的程序框圖如何表示？,思考3:該程序框圖對應的程序如何表述？,INPUT “n=”；n INPUT “an =”；a INPUT “x=”；x v=a i=n-1 WHILE i=0 PRINT “i=”;i INPUT “a

11、i=”；a v=v*x+a i=i-1 WEND PRINT v END,例3 已知一個5次多項式為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)=14130.2.,例4 閱讀下列程序，說明它解決的實際問題是什么？ 求多項式 f(x)=1+2x+3x2+4x3+5x4

12、在x=a時的值.,INPUT “x=”；a n=0 y=0 WHILE n5 y=y+(n+1)*an n=n+1 WEND PRINT y END,1.利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù). 20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0.,(53),2.用秦九韶算法求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當 x=5時的值. 解:首先將原多項式改寫成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7 然后由內(nèi)向外逐層計算一次多項式的值,即 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 所以,當x=5時,多項式的值是2677.,1.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)