算法案例ppt課件

《算法案例ppt課件》由會員分享，可在線閱讀，更多相關(guān)《算法案例ppt課件（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,算法案例,1.3,算法案例1.3,主要內(nèi)容,1.3.1,輾轉(zhuǎn)相除法與更相減損術(shù),1.3.2,秦九韶算法,1.3.3,進位制,主要內(nèi)容1.3.1輾轉(zhuǎn)相除法與更相減損術(shù)1.3.2秦九韶算法,輾轉(zhuǎn)相除法更相減損術(shù),1.1.1,輾轉(zhuǎn)相除法更相減損術(shù)1.1.1,1,、求兩個正整數(shù)的最大公約數(shù),（,1,）求,25,和,35,的最大公約數(shù),（,2,）求,225,和,135,的最大公約數(shù),2,、求,8251,和,6105,的最大公約數(shù),25,（,1,）,5,5,35,7,所以，,25,和,35,的最大公約數(shù)為,5,所以

2、，,225,和,135,的最大公約數(shù)為,533=45,課前復習,225,（,2,）,5,45,135,27,3,15,9,知識回顧：,先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來,3,3,5,1、求兩個正整數(shù)的最大公約數(shù)（1）求25和35的最大公約數(shù)2,輾轉(zhuǎn)相除法（歐幾里得算法）,觀察用輾轉(zhuǎn)相除法求,8251,和,6105,的最大公約數(shù)的過程,第一步,用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得,商,和,余數(shù),8251=61051+2146,結(jié)論：,8251,和,6105,的公約數(shù)就是,6105,和,2146,的公約數(shù)，求,8251,和,6105,的最大公約數(shù)，

3、只要求出,6105,和,2146,的公約數(shù)就可以了。,第二步,對,6105,和,2146,重復第一步的做法,6105=21462+1813,同理,6105,和,2146,的最大公約數(shù)也是,2146,和,1813,的最大公約數(shù)。,思考：從上述的過程你體會到了什么？,輾轉(zhuǎn)相除法（歐幾里得算法）觀察用輾轉(zhuǎn)相除法求8251和610,完整的過程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例,2,用輾轉(zhuǎn)相除法求,225,和,135,的最大公約數(shù),225=1351+90,135=901

4、+45,90=452,顯然,37,是,148,和,37,的最大公約數(shù)，也就是,8251,和,6105,的最大公約數(shù),顯然,45,是,90,和,45,的最大公約數(shù)，也就是,225,和,135,的最大公約數(shù),思考,1,：從上面的兩個例子可以看出計算的規(guī)律是什么？,S1,：用大數(shù)除以小數(shù),S2,：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),S3,：重復,S1,，直到余數(shù)為,0,完整的過程8251=61051+2146 6105=214,輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于,0,停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。,m=n q,r,用程序框圖表示出右邊的過程,否,思考,2,：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？,

5、r=m MOD n,m=n,n=r,r=0?,是,輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于0停止的步驟，這,輾轉(zhuǎn)相除法的程序框圖,開始,輸入,m,n,r=m MOD n,m=n,n=r,r=0?,輸出,m,結(jié)束,是,否,INPUT m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,輾轉(zhuǎn)相除法的程序框圖開始輸入m,nr=m MOD nm=nn,1,、用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：,（,1,）（,123,，,48,）,（,2,）（,72,，,168,）,（,3,）（,153,，,119,）,（,4,）（,4081,20723,）,3,53,2

6、4,17,課堂練習：,1、用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：3532417課堂練,2,、下面是求,115,與,276,的最大公約數(shù)的程序，把程序補充完整。,a=115,b=276,DO,r=_,a=b,b=r,LOOP UNTIL r=_,PRINT a,END,2、下面是求115與276的最大公約數(shù)的程序，把程序補充完,更相減損術(shù),算理,：,可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,第一步：,任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用,2,約簡；若不是，則執(zhí)行第二步。,第二步：,以,較大的數(shù)減較小的數(shù),，接著把所得的差與較小的數(shù)比較，并以

7、,大數(shù)減小數(shù),。繼續(xù)這個操作，直到所得的,減數(shù)和差相等為止,，則這個等數(shù)或這個等數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。,更相減損術(shù)算理：可半者半之，不可半者，副置分母、子之數(shù)，以少,例,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,。,練習：用更相減損術(shù)求兩個正數(shù),84,與,72,的最大公約數(shù)。,(12),例1、用更相減損術(shù)求98與63的最大公約數(shù).解

8、：由于63不,二者算理相似，有異曲同工之妙,1,、都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。,2,、從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為,0,則得到，而更相減損術(shù)則以減數(shù)與差相等而得到（差為,0,）,輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別,二者算理相似，有異曲同工之妙輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別,2,、求,324,、,243,、,135,這三個數(shù)的最大公約數(shù),1,、用輾轉(zhuǎn)相除法求,294,與,84,的最大公約數(shù)，再用更相減損術(shù)驗證。,課堂練習：,2、求324、243、1

9、35這三個數(shù)的最大公約數(shù)1、用輾轉(zhuǎn)相,秦九韶算法,1.3.2,秦九韶算法1.3.2,問題,1,怎樣求多項式,f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,當,x=5,時的值？,方法一：把,5,代人多項式,f(x),，計算各項的值，然后把它們加起來，這時我們一共做了,5+4+3+2+1=15,次乘法運算,5,次加法運算,.,方法二：先計算,x,2,然后依次計算,的值，這樣每次都可以利用上一次計算的結(jié)果，這時我們一共需要,9,次乘法運算,5,次加法運算,.,問題1怎樣求多項式f(x)=2x5-5x4-4x3+3x,問題,2,能否探索更好的算法,來解決任意多項式的求值問題,?,

10、f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,=(,2x,4,-5x,3,-4x,2,+3x-6)x+7,=(2x,3,-5x,2,-4x+3)x-6)x+7,=(2x,2,-5x-4)x+3)x-6)x+7,=(2x-5)x-4)x+3)x-6)x+7,v,0,=2,v,1,=v,0,x-5=25-5=5,v,2,=v,1,x-4=55-4=21,v,3,=v,2,x+3,=215+3=108,v,4,=v,3,x-6,=1085-6=534,v,5,=v,4,x+7=5345+7=2677,這種求多項式值的方法就叫,秦九韶算法,.,問題2能否探索更好的算法,來解決任意

11、多項式的求值問題?f,設,是一個,n,次的多項式,對該多項式按下面的方式進行改寫：,思考：當知道了,x,的值后該如何求多項式的值？,這是怎樣的一種改寫方式？最后的結(jié)果是什么？,設是一個n次的多項式對該多項式按下面的方式進行改寫：思考：當,要求多項式的值，應該先算最內(nèi)層的一次多項式的值，即,然后，由內(nèi)到外逐層計算一次多項式的值，即,最后的一項是什么？,這種將求一個,n,次多項式,f,（,x,）的值轉(zhuǎn)化成求,n,個一次多項式的值的方法，稱為,秦九韶算法,。,思考：在求多項式的值上，這是怎樣的一個轉(zhuǎn)化？,要求多項式的值，應該先算最內(nèi)層的一次多項式的值，即然后，由內(nèi),點評,:,秦九韶算法是求一元多項式

12、的值的一種方法,.,它的特點是,:,把求一個,n,次多項式的值轉(zhuǎn)化為求,n,個一次多項式的值,通過這種轉(zhuǎn)化,把運算的次數(shù)由至多,n(n+1)/2,次乘法運算和,n,次加法運算,減少為,n,次乘法運算和,n,次加法運算,大大提高了運算效率,.,點評:秦九韶算法是求一元多項式的值的一種方法.,v,1,=a,n,x+a,n-,1,v,2,=v,1,x+a,n-,2,v,3,=v,2,x+a,n-,3,v,n,=v,n-,1,x+a,0,.,觀察上述秦九韶算法中的,n,個一次式,可見,v,k,的計算要用到,v,k-1,的值,.,若令,v,0,=a,n,得,v,0,=a,n,v,k,=v,k-,1,x+

13、a,n-k,(k=1,2,n),這是一個在秦九韶算法中反復執(zhí)行的步驟,因此可用循環(huán)結(jié)構(gòu)來實現(xiàn),.,v1=anx+an-1,v2=v1x+an-2,v3=v2x,程序框圖,v=vx+a,i,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,否,開始,輸入,n,a,n,x,的值,i,0?,i=n-,1,v=a,n,i=i-1,輸出,v,結(jié)束,是,輸入,a,i,程序框圖v=vx+aiINPUT

14、“n=”；n否開始輸入n,1,、用秦九韶算法求多項式,當,x=3,時的值,.,課堂練習,f(3)=21324,1、用秦九韶算法求多項式當x=3時的值.課堂練習f(3)=2,當,x=5,時,多項式的值是,15170.,2,、用秦九韶算法求多項式,f(x)=2x,6,-5x,5,-4x,3,+3x,2,-6x,當,x=5,時的值,.,解,:,原多項式先化為,:,f(x)=2x,6,-5x,5,+,0,x,4,-4x,3,+3x,2,-6x+,0,注意,:n,次多項式有,n+1,項,因此缺少哪一項應將其系數(shù)補,0.,當x=5時,多項式的值是15170.2、用秦九韶算法求多項,進位制,1.3.3,進位

15、制1.3.3,問題,1,我們常見的數(shù)字都是十進制的,但是并不是生活中的每一種數(shù)字都是十進制的,.,比如時間和角度的單位用六十進位制,電子計算機用的是二進制,.,那么什么是進位制,?,不同的進位制之間又有什么聯(lián)系呢,?,進位制是人們?yōu)榱擞嫈?shù)和運算的方便而約定的一種記數(shù)系統(tǒng)，約定滿二進一,就是二進制,;,滿十進一,就是十進制,;,滿十六進一,就是十六進制,;,等等,.,“滿幾進一”,就是幾進制,幾進制的,基數(shù),就是幾,.,可使用數(shù)字符號的個數(shù)稱為基數(shù),.,基數(shù)都是大于,1,的整數(shù),.,問題1我們常見的數(shù)字都是十進制的,但是并不是生活中的每一,例如：二進制可使用的數(shù)字有,0,和,1,基數(shù)是,2;,十

16、進制可使用的數(shù)字有,0,1,2,8,9,等十個數(shù)字,基數(shù)是,10;,十六進制可使用的數(shù)字或符號有,09,等,10,個數(shù)字以及,AF,等,6,個字母,(,規(guī)定字母,AF,對應,1015),十六進制的基數(shù)是,16.,注意,:,為了區(qū)分不同的進位制,常在數(shù)字的右下腳標明基數(shù),.,如,111001,(2),表示二進制數(shù),34,(5),表示,5,進制數(shù),.,十進制數(shù)一般不標注基數(shù),.,例如：二進制可使用的數(shù)字有0和1,基數(shù)是2;注意:為了區(qū)分,問題,2,十進制數(shù),3721,中的,3,表示,3,個千,7,表示,7,個百,2,表示,2,個十,1,表示,1,個一,從而它可以寫成下面的形式,:,3721=310,3,+710,2,+210,1,+110,0,.,想一想二進制數(shù),1011,(2),可以類似的寫成什么形式,?,1011,(2),=12,3,+02,2,+12,1,+12,0,.,同理,:,3421,(5),=35,3,+45,2,+25,1,+15,0,.,C7A16,(16),=1216,4,+716,3,+1016,2,+116,1,+616,0,.,問題2十進制數(shù)3721中的3表示3個