13算法案例.ppt

1、,1.3算法案例,1. 回顧算法的三種表示方法：,（1）、自然語言,（2）、程序框圖,（3）、程序語言,（三種邏輯結(jié)構(gòu)）,（五種基本語句）,復(fù)習(xí)引入,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,例：如何算出8251和6105的最大公約數(shù)？,新課講解：,一、輾轉(zhuǎn)相除法（歐幾里得算法）,1、定義： 所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)數(shù)，

2、用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)較小的數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)。,2、步驟:（以求8251和6105的最大公約數(shù)的過程為例）,第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù):8251=61051+2146,結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的最大公約數(shù)就可以了。,第二步 對(duì)6105和2146重復(fù)第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。,為什么呢

3、？,完整的過程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),思考：從上述的過程你體會(huì)到了什么？,例： 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù),225=1351+90,135=901+45,90=452,顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),思考1：從上面的兩個(gè)例子中可以看出計(jì)算的規(guī)律是什么？,S1：用大數(shù)除以小數(shù),S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),S3：重復(fù)S1，直到

4、余數(shù)為0,輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。,m = n q r,用程序框圖表示出右邊的過程,r=m MOD n,m = n,n = r,r=0?,是,否,思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？,思考：你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？,(1)、算法步驟：,第一步：輸入兩個(gè)正整數(shù)m,n(mn). 第二步：計(jì)算m除以n所得的余數(shù)r. 第三步：m=n,n=r. 第四步：若r0,則m,n的最大公約數(shù)等于m； 否則，返回第二步. 第五步：輸出最大公約數(shù)m.,(2)、程序框圖：,(3)、程序：,INPUT m,n DO r=m MOD n m=n n

5、=r LOOP UNTIL r=0 PRINT m END,二、更相減損術(shù),可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)和差相等為止，則這個(gè)等數(shù)或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。,（1）、九章算術(shù)中的更相減損術(shù)：,1、背景介紹：,（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：,2、定義：,所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的

6、數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(shù)的最大公約數(shù)。,例: 用更相減損術(shù)求98與63的最大公約數(shù).,解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減,9863356335283528728721 21714 1477,所以，98和63的最大公約數(shù)等于7,3、方法：,1、用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù),練習(xí)：,思路分析：先約簡(jiǎn)，再求21與18的最大公約數(shù),然后乘以兩次約簡(jiǎn)的質(zhì)因數(shù)4。,2、求324、243、135這三個(gè)數(shù)的最大公約數(shù)。,思路分析：求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè)數(shù)的最大公約數(shù)，第三個(gè)

7、數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)即為所求。,2、求324、243、135這三個(gè)數(shù)的最大公約數(shù),2、求324、243、135這三個(gè)數(shù)的最大公約數(shù),比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （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)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到。,小結(jié),1、求兩個(gè)數(shù)的最大公約數(shù)的兩種方法分別是 （ ）和（ ）。 2、兩個(gè)數(shù)21672，8127的最大公約數(shù)是 （ ） A、2709 B、26

8、06 C、2703 D、2706,輾轉(zhuǎn)相除法,更相減損術(shù),案例2 秦九韶算法,問題,怎樣求多項(xiàng)式f(x)=x5+x4+x3+x2+x+1 當(dāng)x=5時(shí)的值呢？,計(jì)算多項(xiàng)式() =當(dāng)x = 5的值,算法1：,因?yàn)?) =,所以(5)=55555,=3125625125255,= 3906,算法2：,(5)=55555,=5(5555 ) ,=5(5(555 ) ) ,=5(5(5(5+5 +) + ) + ) +,=5(5(5(5 (5 +) + )+)+) +,分析：兩種算法中各用了幾次乘法運(yùn)算？和幾次加法運(yùn)算？,算法1：,算法2：,共做了1+2+3+4=10次乘法運(yùn)算，5次加法運(yùn)算。,共做了4

9、次乘法運(yùn)算，5次加法運(yùn)算。,有沒有更有效的方法？,數(shù)書九章秦九韶算法,對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫：,思考：當(dāng)知道了x的值后該如何求多項(xiàng)式的值？,這是怎樣的一種改寫方式？最后的結(jié)果是什么？,要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即,然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即,最后的一項(xiàng)是什么？,這種將求一個(gè)n次多項(xiàng)式f(x)的值轉(zhuǎn)化成求n個(gè)一次多項(xiàng)式的值的方法，稱為秦九韶算法。,思考：在求多項(xiàng)式的值上，這是怎樣的一個(gè)轉(zhuǎn)化？,例1:用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值.,解法一:首先將原多項(xiàng)式改寫成如下形式 : f(x)=(2x-5)x

10、-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 v5=v4x+7=5345+7=2677,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2677.,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,算法步驟：,第一步：輸入多項(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，若是，則返回第三步；否則，輸出多項(xiàng)式的值v。,程序框圖：,這是一個(gè)

11、在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。,程序,特點(diǎn)：通過一次式的反復(fù)計(jì)算，逐步得出高次多項(xiàng)式的值，對(duì)于一個(gè)n次多項(xiàng)式，只需做n次乘法和n次加法即可。,例1:用秦九韶算法求多項(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,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 v5=v4x+7=5345+7=2677,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2677.,然

12、后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,2 -5 -4 3 -6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2677.,原多項(xiàng)式的系數(shù),多項(xiàng)式的值.,例1:用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值.,解法二:列表,2,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.,練一練:用秦九韶算法求多項(xiàng)式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時(shí)的值.,解:原多項(xiàng)

13、式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0 列表,2,15170,15170,注意:n次多項(xiàng)式有n+1項(xiàng),因此缺少哪一項(xiàng)應(yīng)將其系數(shù)補(bǔ)0.,例2 已知一個(gè)五次多項(xiàng)式為,用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值。,解：,將多項(xiàng)式變形：,按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)x = 5時(shí)的值：,所以，當(dāng)x = 5時(shí)，多項(xiàng)式的值等于14130.2,你從中看到了怎樣的規(guī)律？怎么用程序框圖來描述呢？,程序框圖：,這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。,練習(xí)、已知多項(xiàng)式f(x)=x5+5x4+10 x3+10 x2+5x+1 用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)

14、x=-2時(shí)的值。,課堂小結(jié)： 1、秦九韶算法的方法和步驟 2、秦九韶算法的程序框圖,案例三進(jìn)位制,問題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ù).,如二進(jìn)制可使用的數(shù)字有0和1,基數(shù)是2; 十進(jìn)制可使用的數(shù)字有0,1,2,8,

15、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+121+120.,同理:,3421(5)=353+452+251+

16、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)制只用0和1兩個(gè)數(shù)字,這正好與電路的通和斷兩種狀態(tài)相對(duì)應(yīng),因此計(jì)算機(jī)內(nèi)部

17、都使用二進(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)化的呢?,例1:把二進(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.,問題4你會(huì)把三進(jìn)制數(shù)10221(3)化為十進(jìn)制數(shù)嗎?,解:10221(3)=134+033+232+231+130 =81+18+6+1=106.,k進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的方法,先把k進(jìn)制

18、的數(shù)表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(k) =ankn+an-1kn-1+a1k1+a0k0 .,再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果.,例2.設(shè)計(jì)一個(gè)算法，把k進(jìn)制數(shù)a（共有n位）化為十進(jìn)制數(shù)b.,開始,輸入a,k,n,b=0,i=1,把a(bǔ)的右數(shù)第i位數(shù)字賦給t,b=b+t*ki-1,i=i+1,in?,否,是,輸出b,結(jié)束,程序框圖：,INPUT a,k,n,i=1,b=0,DO,b=b+t*k(i-1),i=i+1,LOOP UNTIL in,PRINT b,END,t=a MOD 10,a=a10,t=a MOD 10,程序：,例3:把89化為二進(jìn)

19、制的數(shù).,分析:把89化為二進(jìn)制的數(shù),需想辦法將89先寫成如下形式,89=an2n+an-12n-1+a121+a020 .,89=64+16+8+1=126+025+124 +123+022+021+120 =1011001(2).,但如果數(shù)太大,我們是無法這樣湊出來的,怎么辦?,89=442+1,44=222+0,22=112+0,11=52+1,5=22+1,2=12+0,1=02+1,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=101100