1.3 算法案例

1、1.3 算法案例,3 5,9 15,問題1：在小學(xué)，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，你能求出18與30的最大公約數(shù)嗎？,18 30,2,3,18和30的最大公約數(shù)是23=6.,先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除,一直除到所得的商是互質(zhì)數(shù)為止,然后把所有的除數(shù)連乘起來(lái).,案例1 輾轉(zhuǎn)相除法與更相減損術(shù),問題2:我們都是利用找公約數(shù)的方法來(lái)求 最大公約數(shù)，如果兩個(gè)數(shù)比較大而且根據(jù)我 們的觀察又不能得到一些公約數(shù)，我們又應(yīng) 該怎樣求它們的最大公約數(shù)？比如求8251與 6105的最大公約數(shù)?,研探新知,1.輾轉(zhuǎn)相除法:,例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。,分析：8251與6105兩數(shù)都比較大

2、，而且沒有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(shù).,解：8251610512146,顯然8251與6105的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù)。,1.輾轉(zhuǎn)相除法:,例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。,解：8251610512146;,6105214621813; 214618131333; 333148237; 1483740.,則37為8251與6105的最大公約數(shù)。,以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除

3、法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。,第一步,給定兩個(gè)正數(shù)m,n 第二步,計(jì)算m除以n所得到余數(shù)r 第三步,m=n,n=r 第四步,若r=0,則m,n的最大公約數(shù)等于m;否則返回第二步,輾轉(zhuǎn)相除法求最大公約數(shù)算法：,思考 ：需不需要比較m，n的大小,不需要,否,開始,輸入兩個(gè)正數(shù)m,n,r=m MOD n,r=0?,輸出m,結(jié)束,m=n,n=r,是,程序框圖,練習(xí)1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).,(53),20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0.,2.更相減損術(shù):,

4、我國(guó)早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù).,更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之.,翻譯出來(lái)為：第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù).若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步. 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（或這個(gè)數(shù)與約減數(shù)的乘積）就是所求的最大公約數(shù).,例2 用更相減損術(shù)求98與63的最大公約數(shù).,解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，,即：986335; 633528; 35287

5、; 28721; 21714; 1477.,所以，98與63的最大公約數(shù)是7。,練習(xí)2：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。,(12),INPUT m, n IF mn IF dn THEN m=d,ELSE m=n n=d END IF d=m-n WEND d=2 k*d PRINT d END,思考：你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？,輾轉(zhuǎn)相除法與更相減損術(shù)的比較:,（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主;計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。 （2）從結(jié)果體現(xiàn)形式來(lái)

6、看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到.,問題1設(shè)計(jì)求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值的算法,并寫出程序.,點(diǎn)評(píng):上述算法一共做了15次乘法運(yùn)算,5次加法運(yùn)算.優(yōu)點(diǎn)是簡(jiǎn)單,易懂;缺點(diǎn)是不通用,不能解決任意多項(xiàng)式求值問題,而且計(jì)算效率不高.,n次多項(xiàng)式至多n(n+1)/2次乘法運(yùn)算和n次加法運(yùn)算,案例2 秦九韶算法,這析計(jì)算上述多項(xiàng)式的值,一共需要9次乘法運(yùn)算,5次加法運(yùn)算.,問題2有沒有更高效的算法?,分析:計(jì)算x的冪時(shí),可以利用前面的計(jì)算結(jié)果,以減少計(jì)算量,即先計(jì)算x2,然后依次計(jì)算,的值.,第二種做法與第一種做

7、法相比,乘法的運(yùn)算次數(shù)減少了,因而能提高運(yùn)算效率.而且對(duì)于計(jì)算機(jī)來(lái)說(shuō),做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多,因此第二種做法能更快地得到結(jié)果.,問題3能否探索更好的算法,來(lái)解決任意多項(xiàng)式的求值問題?,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)x-4)x+3)x-6)x+7,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 v

8、5=v4x+7=5345+7=2677,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2677.,這種求多項(xiàng)式值的方法就叫秦九韶算法.,變?yōu)榍髱讉€(gè)一次式的值,幾個(gè)乘法 幾個(gè)加法？,秦九韶?cái)?shù)書九章.,2 -5 0 -4 3 -6 0,x=5,10,5,25,25,125,121,605,608,3040,3034,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是15170.,練習(xí):用秦九韶算法求多項(xiàng)式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時(shí)的值.,解:原多項(xiàng)式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0 列表,2,15170,15170,注意:n次多項(xiàng)式有n+1項(xiàng),因此缺少哪一項(xiàng)應(yīng)將

9、其系數(shù)補(bǔ)0.,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.,我們可以改寫成如下形式:,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值,即,v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,一般地,對(duì)于一個(gè)n次多項(xiàng)式,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,這樣,求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值.這種算法稱為秦九韶算法.,點(diǎn)評(píng):秦九韶算法是求一元多項(xiàng)式的值的一種方法. 它的特點(diǎn)是:把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,

10、通過(guò)這種轉(zhuǎn)化,把運(yùn)算的次數(shù)由至多n(n+1)/2次乘法運(yùn)算和n次加法運(yùn)算,減少為n次乘法運(yùn)算和n次加法運(yùn)算,大大提高了運(yùn)算效率.,v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,觀察上述秦九韶算法中的n個(gè)一次式,可見vk的計(jì)算要用到vk-1的值.,若令v0=an,得,這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟,因此可用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn).,第一步,輸入多項(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 第五步,若i=0,則返回第三步，否則輸出

11、v,算法分析：,否,程序框圖,開始,輸入n,an,x的值,輸入ai,i=0?,i=n-1,v=an,v=vx+ai,i=i-1,輸出v,結(jié)束,是,問題1我們常見的數(shù)字都是十進(jìn)制的,但是并不是生活中的每一種數(shù)字都是十進(jìn)制的.比如時(shí)間和角度的單位用六十進(jìn)位制,電子計(jì)算機(jī)用的是二進(jìn)制.那么什么是進(jìn)位制?不同的進(jìn)位制之間又有什么聯(lián)系呢?,進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進(jìn)一,就是二進(jìn)制;滿十進(jìn)一,就是十進(jìn)制;滿十六進(jìn)一,就是十六進(jìn)制;等等.,“滿幾進(jìn)一”,就是幾進(jìn)制,幾進(jìn)制的基數(shù)就是幾.,可使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù).基數(shù)都是大于1的整數(shù).,案例3 進(jìn)位制,如二進(jìn)制可使用

12、的數(shù)字有0和1,基數(shù)是2; 十進(jìn)制可使用的數(shù)字有0,1,2,8,9等十個(gè)數(shù)字,基數(shù)是10; 十六進(jìn)制可使用的數(shù)字或符號(hào)有09等10個(gè)數(shù)字以及AF等6個(gè)字母(規(guī)定字母AF對(duì)應(yīng)1015),十六進(jìn)制的基數(shù)是16.,注意:為了區(qū)分不同的進(jìn)位制,常在數(shù)字的右下腳標(biāo)明基數(shù),.,如111001(2)表示二進(jìn)制數(shù),34(5)表示5進(jìn)制數(shù).,十進(jìn)制數(shù)一般不標(biāo)注基數(shù).,問題2十進(jìn)制數(shù)3721中的3表示3個(gè)千,7表示7個(gè)百,2表示2個(gè)十,1表示1個(gè)一,從而它可以寫成下面的形式:,3721=3103+7102+2101+1100.,想一想二進(jìn)制數(shù)1011(2)可以類似的寫成什么形式?,1011(2)=123+022+

13、121+120.,同理:,3421(5)=353+452+251+150.,C7A16(16)=12164+7163+10162 +1161+6160.,一般地,若k是一個(gè)大于1的整數(shù),那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式,anan-1a1a0(k) (0ank,0an-1,a1,a0k),意思是:(1)第一個(gè)數(shù)字an不能等于0; (2)每一個(gè)數(shù)字an,an-1,a1,a0都須小于k.,k進(jìn)制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0 .,注意這是一個(gè)n+1位數(shù).,問題3二進(jìn)制

14、只用0和1兩個(gè)數(shù)字,這正好與電路的通和斷兩種狀態(tài)相對(duì)應(yīng),因此計(jì)算機(jī)內(nèi)部都使用二進(jìn)制.計(jì)算機(jī)在進(jìn)行數(shù)的運(yùn)算時(shí),先把接受到的數(shù)轉(zhuǎn)化成二進(jìn)制數(shù)進(jìn)行運(yùn)算,再把運(yùn)算結(jié)果轉(zhuǎn)化為十進(jìn)制數(shù)輸出. 那么二進(jìn)制數(shù)與十進(jìn)制數(shù)之間是如何轉(zhuǎn)化的呢?,例3:把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù).,分析:先把二進(jìn)制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式,再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果.,解:110011(2) =125+124+023+022+121+120 =132+116+12+1=51.,k進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的方法,先把k進(jìn)制的數(shù)表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(

15、k) =ankn+an-1kn-1+a1k1+a0k0 .,再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果.,例4:把89化為二進(jìn)制的數(shù).,分析:把89化為二進(jìn)制的數(shù),需想辦法將89先寫成如下形式,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ù)去除89或所得商(一直到商為0為止),然后取余數(shù) -除2取余法.,2=12+0,1=02+1,44 1,例4:把89化為二進(jìn)制的數(shù).,我們可以用下面的除法算式表示除2取余法:,22 0,11 0,5 1,2 1,1 0,0 1,把算式中各步所得的余數(shù)從下到上排列,得到,89=1011001(2).,這種方法也可以推廣為把十進(jìn)制數(shù)化為k進(jìn)制數(shù)的算法,稱為除k取余法.,例5:把89化為五進(jìn)制的數(shù).,解:以5作為除數(shù),相應(yīng)的除法算式