高中數(shù)學(xué) 1.3 第1課時輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法課件 新人教A版必修3.ppt

《高中數(shù)學(xué) 1.3 第1課時輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法課件 新人教A版必修3.ppt》由會員分享，可在線閱讀，更多相關(guān)《高中數(shù)學(xué) 1.3 第1課時輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法課件 新人教A版必修3.ppt（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1.3 算法案例 第1課時 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法,1.通過輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法的學(xué)習(xí),進(jìn)一步體會算法思想; 2.通過古代著名的算法,理解掌握輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法的含義;(重點) 3.了解其計算過程;(重點) 4.了解其算法程序框圖和程序．(難點),1. 回顧算法的三種表述： 自然語言 程序框圖（三種邏輯結(jié)構(gòu)） 程序語言（五種基本語句）,2.小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法. 先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.,例如：求兩個正整數(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)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù).若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù).,（1）輾轉(zhuǎn)相除法,（2）算法步驟 第一步,輸入兩個正整數(shù)m,n(mn). 第二步,計算m除以n所得的余數(shù)r. 第三步,m=n,n=r. 第四步,若r＝0,則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ù)約之. 第一步：任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù).若是，則用2約簡；若不是則執(zhí)行第二步. 第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或其與約簡的數(shù)的乘積就是所求的最大公約數(shù).,更相減損術(shù) （1）算理：所謂更相減損術(shù)，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟，直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù).,（2）算法步驟 第一步,輸入兩個正整數(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 a≠b 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)相減, 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98和63的最大公約數(shù)等于7.,,秦九韶算法的基本思想 對于求n次多項式的值，在我國古代數(shù)學(xué)中有一個優(yōu)秀算法，即秦九韶算法，我們將對這個算法作些了解和探究. 思考1:對于多項式f(x)=x5+x4+x3+x2+x+1，求f(5)的值. 若先計算各項的值，然后再相加，那么一共要做多少次乘法運算和多少次加法運算？ 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的值，這個多項式應(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)向外逐層計算一次多項式的值，其算法步驟如何？ 第一步,計算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 (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. 第五步:判斷i≥0是否成立.若是，則返回第三步；否則，輸出多項式的值v.,思考2:該算法的程序框圖如何表示？,,,開始,,,輸入n，an，x的值,,,v=an,,,v=vx+ai,,,輸入ai,,i≥0？,,i=n-1,,,,i=i-1,,,,結(jié)束,,,是,,,輸出v,否,思考3:該程序框圖對應(yīng)的程序如何表述？,,,開始,,,輸入n，an，x的值,,,v=an,,,v=vx+ai,,,輸入ai,,i≥0？,,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 已知一個5次多項式為f(x)=4x5+2x4+3.5x3-2.6x2+ 1.7x-0.8，用秦九韶算法求這個多項式當(dāng)x=5時的值. 解：根據(jù)秦九韶算法把多項式改寫成如下形式：f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8. 按照從內(nèi)到外的順序，依次計算一次多項式當(dāng)x=5時的值： 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.,閱讀下列程序，說明它解決的實際問題是什么？ 解：求多項式 f(x)=1+2x+3x2+4x3+5x4在x=a時的值.,INPUT “x=”；a n=0 y=0 WHILE n5 y=y+(n+1)*a∧n 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.用秦九韶算法求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng) x=5時的值. 解:首先將原多項式改寫成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7 然后由內(nèi)向外逐層計算一次多項式當(dāng)x=5時的值,即 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時,多項式的值是2 677.,1.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時，計算次數(shù)的區(qū)別較明顯. （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0而得到，而更相減損術(shù)則以減數(shù)與差相等而得到.,2.評價一個算法好壞的一個重要標(biāo)志是運算的次數(shù)，如果一個算法從理論上需要超出計算機(jī)允許范圍內(nèi)的運算次數(shù)，那么這樣的算法就只能是一個理論算法.在多項式求值的各種算法中，秦九韶算法是一個優(yōu)秀算法.,,,昨天的努力就是今天的收獲，今天的努力就是未來的希望.歲月不饒人，不妨現(xiàn)在就行動！,