1.3 算法案例 第1課時(shí) 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法,1.通過輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法的學(xué)習(xí),進(jìn)一步體會算法思想; 2.通過古代著名的算法,理解掌握輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法的含義;(重點(diǎn)) 3.了解其計(jì)算過程;(重點(diǎn)) 4.了解其算法程序框圖和程序(難點(diǎn)),1. 回顧算法的三種表述： 自然語言 程序框圖（三種邏輯結(jié)構(gòu)） 程序語言（五種基本語句）,2.小學(xué)學(xué)過的求兩個(gè)數(shù)最大公約數(shù)的方法. 先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.,例如：求兩個(gè)正整數(shù)的最大公約數(shù) （1）求25和35的最大公約數(shù) （2）求49和63的最大公約數(shù),所以，25和35的最大公約數(shù)為5.,所以，49和63的最大公約數(shù)為7.,除了用這種方法外還有沒有其他方法嗎？,輾轉(zhuǎn)相除法 （歐幾里得算法）,思考：算出8 251和6 105的最大公約數(shù).,第一步,用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8 251=6 1051+2 146. 結(jié)論：8 251和6 105的公約數(shù)就是6 105和2 146的公約數(shù)，求8 251和6 105的最大公約數(shù)，只要求出6 105和2 146的最大公約數(shù)就可以了.,為什么？,第二步,對6 105和2 146重復(fù)第一步的做法， 6 105=2 1462+1 813， 同理6 105和2 146的最大公約數(shù)也是2 146和1 813的最大公約數(shù).,完整的過程:,8 251=6 1051+2 146,6 105=2 1462+1 813,2 146=1 8131+333,1 813=3335+148,333=1482+37,148=374+0,顯然37是148和37的最大公約數(shù)，也就是8 251和6 105的最大公約數(shù).,所謂輾轉(zhuǎn)相除法，就是對于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù).若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù).,（1）輾轉(zhuǎn)相除法,（2）算法步驟 第一步,輸入兩個(gè)正整數(shù)m,n(mn). 第二步,計(jì)算m除以n所得的余數(shù)r. 第三步,m=n,n=r. 第四步,若r0,則m,n的最大公約數(shù)等于m；否則轉(zhuǎn)到第二步. 第五步,輸出最大公約數(shù)m.,（3）程序框圖,（4）程序,INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,更相減損術(shù) 算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之. 第一步：任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù).若是，則用2約簡；若不是則執(zhí)行第二步. 第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）或其與約簡的數(shù)的乘積就是所求的最大公約數(shù).,更相減損術(shù) （1）算理：所謂更相減損術(shù)，就是對于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟，直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(shù)的最大公約數(shù).,（2）算法步驟 第一步,輸入兩個(gè)正整數(shù)a,b(ab); 第二步,若a不等于b ,則執(zhí)行第三步；否則轉(zhuǎn)到第五步； 第三步,把a(bǔ)-b的差賦予r; 第四步,如果br, 那么把b賦給a,把r賦給b;否則把r賦給a，執(zhí)行第二步； 第五步,輸出最大公約數(shù)b.,（3）程序框圖,（4）程序,INPUT “a,b=“;a,b WHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IF WEND PRINT b END,例1 用更相減損術(shù)求98與63的最大公約數(shù). 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減, 986335 633528 35287 28721 21714 1477 所以，98和63的最大公約數(shù)等于7.,秦九韶算法的基本思想 對于求n次多項(xiàng)式的值，在我國古代數(shù)學(xué)中有一個(gè)優(yōu)秀算法，即秦九韶算法，我們將對這個(gè)算法作些了解和探究. 思考1:對于多項(xiàng)式f(x)=x5+x4+x3+x2+x+1，求f(5)的值. 若先計(jì)算各項(xiàng)的值，然后再相加，那么一共要做多少次乘法運(yùn)算和多少次加法運(yùn)算？ 4+3+2+1=10次乘法運(yùn)算，5次加法運(yùn)算.,思考2:在上述問題中，若先計(jì)算x2的值，然后依次計(jì)算x2x，(x2x)x，(x2x)x)x的值，這樣每次都可以利用上一次計(jì)算的結(jié)果，再將這些數(shù)與x和1相加，那么一共做了多少次乘法運(yùn)算和多少次加法運(yùn)算？ 4次乘法運(yùn)算，5次加法運(yùn)算.,思考3:利用后一種算法求多項(xiàng)式f(x)=anxn+an-1xn-1 +a1x+a0的值，這個(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.,這是怎樣的一種改寫方式？最后的結(jié)果是什么？,思考4:對于f(x)=(anx+an-1)x+an-2)x+a1)x+a0，由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟如何？ 第一步,計(jì)算v1=anx+an-1. 第二步,計(jì)算v2=v1x+an-2. 第三步,計(jì)算v3=v2x+an-3. 第n步,計(jì)算vn=vn-1x+a0.,最后的一項(xiàng)是什么？,思考5:上述求多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0的值的方法稱為秦九韶算法，利用該算法求f(x0)的值，一共需要多少次乘法運(yùn)算，多少次加法運(yùn)算？ 思考6:在秦九韶算法中，記v0=an，那么第k步的算式是什么？ vk=vk-1x+an-k (k=1，2，n),秦九韶算法的程序設(shè)計(jì) 思考1:用秦九韶算法求多項(xiàng)式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？ 第一步:輸入多項(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. 第五步:判斷i0是否成立.若是，則返回第三步；否則，輸出多項(xiàng)式的值v.,思考2:該算法的程序框圖如何表示？,開始,輸入n，an，x的值,v=an,v=vx+ai,輸入ai,i0？,i=n-1,i=i-1,結(jié)束,是,輸出v,否,思考3:該程序框圖對應(yīng)的程序如何表述？,開始,輸入n，an，x的值,v=an,v=vx+ai,輸入ai,i0？,i=n-1,i=i-1,結(jié)束,是,輸出v,否,INPUT “n=”；n INPUT “an =”；a INPUT “x=”；x v=a i=n-1 WHILE i=0 PRINT “i=”;i INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END,例2 已知一個(gè)5次多項(xiàng)式為f(x)=4x5+2x4+3.5x3-2.6x2+ 1.7x-0.8，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5時(shí)的值. 解：根據(jù)秦九韶算法把多項(xiàng)式改寫成如下形式：f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8. 按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x=5時(shí)的值： v0=4; v1=45+2=22； v2=225+3.5=113.5； v3=113.55-2.6=564.9； v4=564.95+1.7=2 826.2； v5=2 826.25-0.8=14 130.2. 所以f(5)=14 130.2.,閱讀下列程序，說明它解決的實(shí)際問題是什么？ 解：求多項(xiàng)式 f(x)=1+2x+3x2+4x3+5x4在x=a時(shí)的值.,INPUT “x=”；a n=0 y=0 WHILE n5 y=y+(n+1)*an n=n+1 WEND PRINT y END,1. 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù). 顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù).,225=1351+90,135=901+45,90=452,2.利用輾轉(zhuǎn)相除法求兩數(shù)4 081與20 723的最大公約數(shù). 20 723 =4 0815+318; 4 081 =31812+265; 318=2651+53; 265=535+0.,所以4 081與20 723的最大公約數(shù)是53.,3.用秦九韶算法求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng) x=5時(shí)的值. 解:首先將原多項(xiàng)式改寫成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7 然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式當(dāng)x=5時(shí)的值,即 v0=2 v1=v0x-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=2 677 所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2 677.,1.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)，計(jì)算次數(shù)的區(qū)別較明顯. （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0而得到，而更相減損術(shù)則以減數(shù)與差相等而得到.,2.評價(jià)一個(gè)算法好壞的一個(gè)重要標(biāo)志是運(yùn)算的次數(shù)，如果一個(gè)算法從理論上需要超出計(jì)算機(jī)允許范圍內(nèi)的運(yùn)算次數(shù)，那么這樣的算法就只能是一個(gè)理論算法.在多項(xiàng)式求值的各種算法中，秦九韶算法是一個(gè)優(yōu)秀算法.,昨天的努力就是今天的收獲，今天的努力就是未來的希望.歲月不饒人，不妨現(xiàn)在就行動！,