四川省開江縣高中數(shù)學(xué) 第一章 算法初步 1.3 算法與案例課件 新人教A版必修3

《四川省開江縣高中數(shù)學(xué) 第一章 算法初步 1.3 算法與案例課件 新人教A版必修3》由會員分享，可在線閱讀，更多相關(guān)《四川省開江縣高中數(shù)學(xué) 第一章 算法初步 1.3 算法與案例課件 新人教A版必修3（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1.3 1.3 算法案例算法案例3 59 15 問題問題11：在小學(xué)，我們已經(jīng)學(xué)過求最大公約數(shù)：在小學(xué)，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出的知識，你能求出1818與與3030的最大公約數(shù)嗎？的最大公約數(shù)嗎？18 30231818和和3030的最大公約數(shù)是的最大公約數(shù)是2 23=6.3=6.先用兩個數(shù)公有的先用兩個數(shù)公有的質(zhì)因數(shù)質(zhì)因數(shù)連續(xù)去除連續(xù)去除,一直除到一直除到所得的商是互質(zhì)數(shù)為止所得的商是互質(zhì)數(shù)為止,然后把所有的除數(shù)連然后把所有的除數(shù)連乘起來乘起來.案例案例1 1 輾轉(zhuǎn)相除法與更相減損術(shù)輾轉(zhuǎn)相除法與更相減損術(shù) 問題問題2:2:我們都是利用找公約數(shù)的方法來求我們都是利用找公約數(shù)的方法

2、來求最大公約數(shù)，如果兩個數(shù)比較大而且根據(jù)我最大公約數(shù)，如果兩個數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求該怎樣求它們的最大公約數(shù)？比如求82518251與與61056105的最大公約數(shù)的最大公約數(shù)? ? 研探新知研探新知1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: :例例1 1 求兩個正數(shù)求兩個正數(shù)82518251和和61056105的最大公約數(shù)。的最大公約數(shù)。分析：分析：82518251與與61056105兩數(shù)都比較大，而且沒兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，根有明顯的公約數(shù)，如能把它們都變小一點，

3、根據(jù)已有的知識即可求出最大公約數(shù)據(jù)已有的知識即可求出最大公約數(shù). .解：解：82518251610561051 121462146顯然顯然82518251與與61056105的最大公約數(shù)也必是的最大公約數(shù)也必是21462146的約數(shù)，同樣的約數(shù)，同樣61056105與與21462146的公約數(shù)也必是的公約數(shù)也必是82518251的約數(shù)，所以的約數(shù)，所以82518251與與61056105的最大公約數(shù)也是的最大公約數(shù)也是61056105與與21462146的最大公約數(shù)。的最大公約數(shù)。1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: :例例1 1 求兩個正數(shù)求兩個正數(shù)82518251和和61056105的最大公約數(shù)

4、。的最大公約數(shù)。解：解：82518251610561051 12146;2146;6105214621813;214618131333;18133335148;333148237;1483740.則則3737為為82518251與與61056105的最大公約數(shù)。的最大公約數(shù)。以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在除法。也叫歐幾里德算法，它是由歐幾里德在公元前公元前300300年左右首先提出的。年左右首先提出的。 第一步第一步, ,給定兩個正數(shù)給定兩個正數(shù)m,nm,n 第二步第二步, ,計算計算m m除以除以n n所得到余

5、數(shù)所得到余數(shù)r r 第三步第三步,m=n,n=r,m=n,n=r 第四步第四步, ,若若r=0,r=0,則則m,nm,n的最大公約數(shù)等于的最大公約數(shù)等于m;m;否則返回第二步否則返回第二步輾轉(zhuǎn)相除法求最大公約數(shù)算法：輾轉(zhuǎn)相除法求最大公約數(shù)算法：思考思考 ：需不需要比較：需不需要比較m，n的大小的大小不需要不需要否否開始開始 輸入兩個正數(shù)輸入兩個正數(shù)m,nr=m MOD nr=0?輸出輸出m結(jié)束結(jié)束m=nn=r是是程序框圖練習(xí)練習(xí)1 1：利用輾轉(zhuǎn)相除法求兩數(shù)：利用輾轉(zhuǎn)相除法求兩數(shù)40814081與與2072320723的最大公約數(shù)的最大公約數(shù). . (53)(53)20723=40815+318

6、;4081=31812+265;318=2651+53;265=535+0.2.2.更相減損術(shù)更相減損術(shù): :我國早期也有解決求最大公約數(shù)問題的算我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)法，就是更相減損術(shù).更相減損術(shù)求最大公約數(shù)的步驟如下：可更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之少減多，更相減損，求其等也，以等數(shù)約之.翻譯出來為：第一步：任意給出兩個正數(shù)；翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)判斷它們是否都是偶數(shù). .若是，用若是，用2 2約簡；

7、若不是，約簡；若不是，執(zhí)行第二步執(zhí)行第二步. .第二步：以較大的數(shù)減去較小的數(shù)，接著把第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（或這個數(shù)與約減數(shù)的乘積）就是所求的最大公（或這個數(shù)與約減數(shù)的乘積）就是所求的最大公約數(shù)約數(shù). .例例2 2 用更相減損術(shù)求用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). .解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，減小數(shù)，并輾轉(zhuǎn)相減，

8、 即：即：986335; 633528; 35287; 28721; 21714; 1477.所以，所以，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。練習(xí)練習(xí)2 2：用更相減損術(shù)求兩個正數(shù)：用更相減損術(shù)求兩個正數(shù)8484與與7272的最大的最大公約數(shù)。公約數(shù)。 (12)(12)INPUT m, nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WENDd=m-nWHILE dn IF dn THEN m=d ELSE m=n n=d END IF d=m-nWENDd=2 k

9、*dPRINT dEND思考：你能根據(jù)更相減損術(shù)設(shè)計程序，求兩個正整數(shù)的最大公約數(shù)嗎？輾轉(zhuǎn)相除法與更相減損術(shù)的比較輾轉(zhuǎn)相除法與更相減損術(shù)的比較: : （1 1）都是求最大公約數(shù)的方法，計算上）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主主; ;計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。別較明顯。（2 2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為體現(xiàn)結(jié)果是以相除余

10、數(shù)為0 0則得到，而更相減損則得到，而更相減損術(shù)則以減數(shù)與差相等而得到術(shù)則以減數(shù)與差相等而得到. . 問題問題11設(shè)計求多項式設(shè)計求多項式f(x)=2xf(x)=2x5 5-5x-5x4 4-4x-4x3 3+3x+3x2 2- -6x+76x+7當(dāng)當(dāng)x=5x=5時的值的算法時的值的算法, ,并寫出程序并寫出程序. .x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序程序點評點評: :上述算法一共做了上述算法一共做了1515次乘法運算次乘法運算,5,5次加法次加法運算運算. .優(yōu)點是簡單優(yōu)點是簡單, ,易懂易懂; ;缺點是不通用缺點是不通用, ,不能解不能解決任意多項式

11、求值問題決任意多項式求值問題, ,而且計算效率不高而且計算效率不高. .n n次多項式至多次多項式至多n(n+1)/2n(n+1)/2次乘法運算和次乘法運算和n n次加法運算次加法運算案例案例2 2 秦九韶算法秦九韶算法 這析計算上述多項式的值這析計算上述多項式的值,一共需要一共需要9次乘次乘法運算法運算,5次加法運算次加法運算.問題問題2有沒有更高效的算法有沒有更高效的算法?分析分析:計算計算x的冪時的冪時,可以利用前面的計算結(jié)可以利用前面的計算結(jié)果果,以減少計算量以減少計算量,即先計算即先計算x2,然后依次計算然后依次計算222,(),()xx xxxxxxx的值的值.第二種做法與第一種做

12、法相比第二種做法與第一種做法相比,乘法的運乘法的運算次數(shù)減少了算次數(shù)減少了,因而能提高運算效率因而能提高運算效率.而且對于而且對于計算機來說計算機來說,做一次乘法所需的運算時間比做一做一次乘法所需的運算時間比做一次加法要長得多次加法要長得多,因此第二種做法能更快地得到因此第二種做法能更快地得到結(jié)果結(jié)果.問題問題3能否探索更好的算法能否探索更好的算法,來解決任意多來解決任意多項式的求值問題項式的求值問題?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5

13、)x-4)x+3)x-6)x+7v0=2v1=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=2677所以所以,當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是2677.這種求多項式值的方法就叫這種求多項式值的方法就叫秦九韶算法秦九韶算法.變?yōu)榍髱讉€一次式的值變?yōu)榍髱讉€一次式的值幾個乘法幾個乘法幾個加法？幾個加法？秦九韶數(shù)書九章秦九韶數(shù)書九章.2 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以所以,當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是1

14、5170.練習(xí)練習(xí):用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)當(dāng)x=5時的值時的值.解解:原多項式先化為原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 注意注意:n次多項式有次多項式有n+1項項,因此缺少哪一項因此缺少哪一項應(yīng)將其系數(shù)補應(yīng)將其系數(shù)補0.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下形式我們可以改寫成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多項式的值時求多項式的值時,首先計算最內(nèi)層括號內(nèi)一首先

15、計算最內(nèi)層括號內(nèi)一次多項式的值次多項式的值,即即 v1=anx+an-1,然后由內(nèi)向外逐層計算一次多項式的值然后由內(nèi)向外逐層計算一次多項式的值,即即一般地一般地,對于一個對于一個n次多項式次多項式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.這樣這樣,求求n次多項式次多項式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個個一次多項式的值一次多項式的值.這種算法稱為這種算法稱為秦九韶算法秦九韶算法.點評點評:秦九韶算法是求一元多項式的值的秦九韶算法是求一元多項式的值的一種方法一種方法.它的特點是它的特點是:把求一個把求一個n次多項式的值轉(zhuǎn)化次多項式的值轉(zhuǎn)化為求為求n個一次

16、多項式的值個一次多項式的值,通過這種轉(zhuǎn)化通過這種轉(zhuǎn)化,把運算把運算的次數(shù)由至多的次數(shù)由至多n(n+1)/2次乘法運算和次乘法運算和n次加法次加法運算運算,減少為減少為n次乘法運算和次乘法運算和n次加法運算次加法運算,大大大大提高了運算效率提高了運算效率.v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶算法中的觀察上述秦九韶算法中的n個一次式個一次式,可見可見vk的計算要用到的計算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n）這是一個在秦九韶算法中反復(fù)執(zhí)行的步這是一個在秦

17、九韶算法中反復(fù)執(zhí)行的步驟驟,因此可用循環(huán)結(jié)構(gòu)來實現(xiàn)因此可用循環(huán)結(jié)構(gòu)來實現(xiàn). 第一步第一步, ,輸入多項式次數(shù)輸入多項式次數(shù)n n、最高次項的系數(shù)、最高次項的系數(shù)anan和和x x的值的值 第二步第二步, ,將將v v的值初始化為的值初始化為anan，將，將i i的值初始化為的值初始化為n-1n-1 第三步第三步, ,輸入輸入i i次項的系數(shù)次項的系數(shù)aiai 第四步第四步,v=vx+ai,i=i-1,v=vx+ai,i=i-1 第五步第五步, ,若若i=0,i=0,則返回第三步，否則輸出則返回第三步，否則輸出v v算法分析：算法分析：否否程序框圖程序框圖開始開始輸入輸入n,an,x的值的值輸入

18、輸入aii=0?i=n-1v=anv=vx+aii=i-1輸出輸出v結(jié)束結(jié)束是是 問題問題11我們常見的數(shù)字都是十進制的我們常見的數(shù)字都是十進制的, ,但是并不是生活中的每一種數(shù)字都是十進制的但是并不是生活中的每一種數(shù)字都是十進制的. .比如時間和角度的單位用六十進位制比如時間和角度的單位用六十進位制, ,電子計電子計算機用的是二進制算機用的是二進制. .那么什么是進位制那么什么是進位制? ?不同的不同的進位制之間又有什么聯(lián)系呢進位制之間又有什么聯(lián)系呢? ?進位制是人們?yōu)榱擞嫈?shù)和運算的方便而進位制是人們?yōu)榱擞嫈?shù)和運算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進一約定的一種記數(shù)系統(tǒng)，約定滿二進一, ,

19、就是二就是二進制進制; ;滿十進一滿十進一, ,就是十進制就是十進制; ;滿十六進一滿十六進一, ,就就是十六進制是十六進制; ;等等等等. . “滿幾進一滿幾進一”, ,就是幾進制就是幾進制, ,幾進制的幾進制的基數(shù)基數(shù)就是就是幾幾. .可使用數(shù)字符號的個數(shù)稱為基數(shù)可使用數(shù)字符號的個數(shù)稱為基數(shù). .基數(shù)都是基數(shù)都是大于大于1 1的整數(shù)的整數(shù). . 案例案例3 3 進位制進位制如二進制可使用的數(shù)字有如二進制可使用的數(shù)字有0和和1,基數(shù)是基數(shù)是2; 十進制可使用的數(shù)字有十進制可使用的數(shù)字有0,1,2,8,9等十個等十個數(shù)字數(shù)字,基數(shù)是基數(shù)是10; 十六進制可使用的數(shù)字或符號有十六進制可使用的數(shù)字

20、或符號有09等等10個數(shù)字以及個數(shù)字以及AF等等6個字母個字母(規(guī)定字母規(guī)定字母AF對應(yīng)對應(yīng)1015),十六進制的基數(shù)是十六進制的基數(shù)是16.注意注意: :為了區(qū)分不同的進位制為了區(qū)分不同的進位制, ,常在數(shù)字常在數(shù)字的右下腳標明基數(shù)的右下腳標明基數(shù),. ,. 如如111001111001(2)(2)表示二進制數(shù)表示二進制數(shù),34,34(5)(5)表示表示5 5進制數(shù)進制數(shù). .十進制數(shù)一般不標注基數(shù)十進制數(shù)一般不標注基數(shù).問題問題2十進制數(shù)十進制數(shù)3721中的中的3表示表示3個千個千,7表示表示7個百個百,2表示表示2個十個十,1表示表示1個一個一,從而它可以寫成從而它可以寫成下面的形式下面

21、的形式:3721=3103+7102+2101+1100.想一想二進制數(shù)想一想二進制數(shù)1011(2)可以類似的寫成什可以類似的寫成什么形式么形式?1011(2)=123+022+121+120.同理同理:3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162 +1161+6160.一般地一般地,若若k是一個大于是一個大于1的整數(shù)的整數(shù),那么以那么以k為為基數(shù)的基數(shù)的k進制數(shù)可以表示為一串?dāng)?shù)字連寫在一進制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式起的形式anan-1a1a0(k) (0ank,0an-1,a1,a0k)意思是意思是:(1):(1)第一個數(shù)字

22、第一個數(shù)字a an n不能等于不能等于0;0;(2)(2)每一個數(shù)字每一個數(shù)字a an n,a,an-1n-1, ,a,a1 1,a,a0 0都須小于都須小于k.k.k進制的數(shù)也可以表示成不同位上數(shù)字與進制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)基數(shù)k的冪的乘積之和的形式的冪的乘積之和的形式,即即anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0 .注意這是一注意這是一個個n+1位數(shù)位數(shù).問題問題3二進制只用二進制只用0和和1兩個數(shù)字兩個數(shù)字,這正這正好與電路的通和斷兩種狀態(tài)相對應(yīng)好與電路的通和斷兩種狀態(tài)相對應(yīng),因此因此計算計算機內(nèi)部都使用二進制機內(nèi)部都使用二進制.計算機在

23、進行數(shù)的運算計算機在進行數(shù)的運算時時,先把接受到的數(shù)轉(zhuǎn)化成二進制數(shù)進行運算先把接受到的數(shù)轉(zhuǎn)化成二進制數(shù)進行運算,再把運算結(jié)果轉(zhuǎn)化為十進制數(shù)輸出再把運算結(jié)果轉(zhuǎn)化為十進制數(shù)輸出.那么二進制數(shù)與十進制數(shù)之間是如何轉(zhuǎn)那么二進制數(shù)與十進制數(shù)之間是如何轉(zhuǎn)化的呢化的呢?例例3:把二進制數(shù)把二進制數(shù)110011(2)化為十進制數(shù)化為十進制數(shù).分析分析:先把二進制數(shù)寫成不同位上數(shù)字與先把二進制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式的冪的乘積之和的形式,再按照十進制數(shù)的運算再按照十進制數(shù)的運算規(guī)則計算出結(jié)果規(guī)則計算出結(jié)果.解解:110011(2) =125+124+023+022+121+120 =132+1

24、16+12+1=51. k k進制數(shù)轉(zhuǎn)化為十進制數(shù)的方法進制數(shù)轉(zhuǎn)化為十進制數(shù)的方法先把先把k k進制的數(shù)表示成不同位上數(shù)字與基進制的數(shù)表示成不同位上數(shù)字與基數(shù)數(shù)k k的冪的乘積之和的形式的冪的乘積之和的形式, ,即即a an na an-1n-1a a1 1a a0(k)0(k)=a=an nk kn n+a+an-1n-1k kn-1n-1+ +a+a1 1k k1 1+a+a0 0k k0 0 . .再按照十進制數(shù)的運算規(guī)則計算出結(jié)果再按照十進制數(shù)的運算規(guī)則計算出結(jié)果. .例例4:把把89化為二進制的數(shù)化為二進制的數(shù).分析分析:把把89化為二進制的數(shù)化為二進制的數(shù),需想辦法將需想辦法將89

25、先寫成如下形式先寫成如下形式89=an2n+an-12n-1+a121+a020 .89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1 =(12)+0)2+1)2+1)2+0) 2+0)2+1=126+025+124 +123+022+021+120=1011001(2).可以用可以用2連續(xù)去除連續(xù)去除89或所得商或所得商(一直到商為一直到商為0為止為止),然后取余數(shù)然后取余數(shù)-除除2取余法取

26、余法.2=12+0, 1=02+1, 44 1例例4:把把89化為二進制的數(shù)化為二進制的數(shù).我們可以用下面的除法算式表示除我們可以用下面的除法算式表示除2取余法取余法:289 余數(shù)余數(shù)222 0211 025 122 121 020 1把算式中各步所得的余數(shù)把算式中各步所得的余數(shù)從下到上排列從下到上排列,得到得到89=1011001(2).這種方法也可以推廣為把這種方法也可以推廣為把十進制數(shù)化為十進制數(shù)化為k進制數(shù)的進制數(shù)的算法算法,稱為稱為除除k取余法取余法.例例5:5:把把8989化為五進制的數(shù)化為五進制的數(shù). .解解: :以以5 5作為除數(shù)作為除數(shù), ,相應(yīng)的除法算式為相應(yīng)的除法算式為:

27、 :17 4589 余數(shù)余數(shù)53 250 3 89=324(5).問題問題5你會把三進制數(shù)你會把三進制數(shù)10221(3)化為二進制數(shù)嗎化為二進制數(shù)嗎?解解:第一步第一步:先把三進制數(shù)化為十進制數(shù)先把三進制數(shù)化為十進制數(shù):10221(3)=134+033+232+231+130 =81+18+6+1=106. 第二步第二步:再把十進制數(shù)化為二進制數(shù)再把十進制數(shù)化為二進制數(shù): 106=1101010(2).10221(3)=106= 1101010(2).小結(jié)小結(jié)進位制的概念及表示方法進位制的概念及表示方法; ;各種進位制之間的相互轉(zhuǎn)化各種進位制之間的相互轉(zhuǎn)化. .anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0 .