(2013級課堂用)算法案例.pptVIP

1.3 算法案例,案例1 輾轉(zhuǎn)相除法與更相減損術(shù),問題提出,1.研究一個實際問題的算法，主要從算法步驟、程序框圖和編寫程序三方面展開.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序設(shè)計中基本的算法語句有哪幾種？,2.“求兩個正整數(shù)的最大公約數(shù)”是數(shù)學中的一個基礎(chǔ)性問題，它有各種解決辦法，我們以此為案例，對該問題的算法作一些探究.,3 5,9 15,【思考1】：在小學，我們已經(jīng)學過求最大公約數(shù)的知識，你能求出18與30的最大公約數(shù)嗎？,18 30,18和30的最大公約數(shù)是23=6.,先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除, 一直除到所得的商是互質(zhì)數(shù)為止,然 后把所有的除數(shù)連乘起來.,知識探究（一）:輾轉(zhuǎn)相除法,【思考2】對于8251與6105這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難. 注意到 8251=61051+2146， 問：8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？,【思考3】又6105=21462+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.重復(fù)上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。,m = n q r,用程序框圖表示出右邊的過程,思考4：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？,【思考5】上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？,第一步，給定兩個正整數(shù)m，n(mn).,第二步，計算m除以n所得的余數(shù)r.,第三步，m=n，n=r.,第四步，若r=0，則m，n的最大公約數(shù)等 于m；否則，返回第二步.,【思考5】該算法的程序框圖如何表示？,直到型循環(huán)結(jié)構(gòu),【思考6】該程序框圖對應(yīng)的程序如何表述？,INPUT m，n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,【思考7】如果用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)的程序框圖和程序分別如何表示？,INPUT m，n,WHILE n0,r=m MOD n,m=n,n=r,WEND,PRINT m,END,練習1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).,(53),20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0.,知識探究（二）:更相減損術(shù),思考1:設(shè)兩個正整數(shù)mn，若m-n=k，則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等.反復(fù)利用這個原理，可求得98與63的最大公約數(shù)為多少？,98-63=35，,14-7=7.,21-7=14，,28-7=21，,35-28=7，,63-35=28，,思考2:上述求兩個正整數(shù)的最大公約數(shù)的方法稱為更相減損術(shù).一般地，用更相減損術(shù)求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？,第一步，給定兩個正整數(shù)m，n(mn).,第二步，計算m-n所得的差k.,第三步，比較n與k的大小，其中大者用m表 示，小者用n表示.,第四步，若m=n，則m，n的最大公約數(shù)等于 m；否則，返回第二步.,思考3:該算法的程序框圖如何表示？,思考4:該程序框圖對應(yīng)的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,“更相減損術(shù)”在中國古代數(shù)學專著九章算術(shù)中記述為： 可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之.,是,否,n=d,是,輸出2k *d,是,否,否,INPUT “m,n=“;m,n IF mn THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n,While dn IF dn then m=d ELSE m=n n=d End if d=m-n Wend d=2k*d PRINT d End,理論遷移,例1 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).,輾轉(zhuǎn)相除法：168=931+75， 93=751+18， 75=184+3， 18=36.,更相減損術(shù):168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.,例2 求325，130，270三個數(shù)的最大公約數(shù).,因為325=1302+65，130=652，所以325與130的最大公約數(shù)是65.,因為270=654+10，65=106+5，10=52，所以65與270最大公約數(shù)是5.,故325，130，270三個數(shù)的最大公約數(shù)是5.,1.輾轉(zhuǎn)相除法，就是對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù).,小結(jié)作業(yè),2. 更相減損術(shù)，就是對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時相等的兩數(shù)即為原來兩個數(shù)的最大公約數(shù).,比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （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ù)與差相等而得到,1.3 算法案例,案例2 秦九韶算法,問題提出,對于求n次多項式的值，在我國古代數(shù)學中有一個優(yōu)秀算法，即秦九韶算法，我們將對這個算法作些了解和探究.,問題1設(shè)計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值的算法,并寫出程序.,x=5 f=2x5-5x4-4x3+3x2-6x+7 PRINT f END,程序,點評:上述算法一共做了15次乘法運算,5次加法運算.優(yōu)點是簡單,易懂;缺點是不通用,不能解決任意多項多求值問題,而且計算效率不高.,知識探究(一):秦九韶算法的基本思想,思考2:在上述問題中，若先計算x2的值，然后依次計算x2x，(x2x)x，(x2x)x)x的值，這樣每次都可以利用上一次計算的結(jié)果，那么一共做了多少次乘法運算和多少次加法運算？,9次乘法運算，5次加法運算.,第二種做法與第一種做法相比,乘法的運算次數(shù)減少了,因而能提高運算效率.而且對于計算機來說,做一次乘法所需的運算時間比做一次加法要長得多,因此第二種做法能更快地得到結(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)x-4)x+3)x-6)x+7,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=2677,所以,當x=5時,多項式的值是2677.,這種求多項式值的方法就叫秦九韶算法.,5次乘法運算，5次加法運算.,思考4:利用最后一種算法求多項式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.,思考5:對于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.,思考6:上述求多項式 f(x)=anxn+an-1xn-1+a1x+a0的值的方法稱為秦九韶算法，利用該算法求f(x0)的值，一共需要多少次乘法運算，多少次加法運算？,思考7:在秦九韶算法中，記v0=an，那么第k步的算式是什么？,vk=vk-1x+an-k (k=1，2，n),n次乘法運算， 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.,第五步，判斷i0是否成立.若是，則返回第 二步；否則，輸出多項式的值v.,思考2:該算法的程序框圖如何表示？,思考3:該程序框圖對應(yīng)的程序如何表述？,INPUT “n=”；n,INPUT “an=”；a,INPUT “x=”；x,v=an,i=n-1,WHILE i=0,INPUT “ai=”；b,v=v*x+b,i=i-1,WEND,PRINT y,END,理論遷移,例1 已知一個5次多項式為 用秦九韶算法求f(5)的值.,f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.,v1=55+2=27；,v2=275+3.5=138.5；,v3=138.55-2.6=689.9；,v4=689.95+1.7=3451.2；,v5=3451.25-0.8=17255.2.,所以f(5)=17255.2.,【變式】例2 已知一個5次多項式為 用秦九韶算法求當x=5時，V1,V3的值及求f(5)的值,解：f(x)=(5x+0)x+3.5)x+0)x+1.7)x-0.8.,v1=55+0=25；,v2=255+3.5=128.5；,v3=128.55+0=642.5；,v4=642.55+1.7=3214.2；,v5=3214.25-0.8=16070.8.,所以v1=25， v3=642.5 ，f(5)=16070.8.,例3 閱讀下列程序，說明它解決的實際問題是什么？,INPUT “x=”；a n=0 y=0 WHLE n5 y=y+(n+1)*an n=n+1 WEND PRINT y END,求多項式 在x=a時的值.,小結(jié),評價一個算法好壞的一個重要標志是運算的次數(shù)，如果一個算法從理論上需要超出計算機允許范圍內(nèi)的運算次數(shù)，那么這樣的算法就只能是一個理論算法.在多項式求值的各種算法中，秦九韶算法是一個優(yōu)秀算法.,案例3 進位制,1.3 算法案例,【問題1】我們常見的數(shù)字都是十進制的,但是并不是生活中的每一種數(shù)字都是十進制的.比如時間和角度的單位用六十進位制, 計算機用的是二進制. 那么什么是進位制?不同的進位制之間又有什么聯(lián)系呢?,進位制是人們?yōu)榱擞嫈?shù)和運算的方便而約定的一種記數(shù)系統(tǒng)。 約定滿二進一,就是二進制;滿十進一,就是十進制;滿十六進一,就是十六進制;等等.,“滿幾進一”,就是幾進制, 幾進制的基數(shù)就是幾.,可使用數(shù)字符號的個數(shù)稱為基數(shù). 基數(shù)都是大于1的整數(shù).,如二進制可使用的數(shù)字有0和1,基數(shù)是2; 十進制可使用的數(shù)字有0,1,2,8,9等十個數(shù)字,基數(shù)是10; 十六進制可使用的數(shù)字或符號有09等10個數(shù)字以及AF等6個字母(規(guī)定字母AF對應(yīng)1015),十六進制的基數(shù)是16.,【注意】為了區(qū)分不同的進位制,常在數(shù)字的右下腳標明基數(shù).,如 111001(2)表示二進制數(shù), 34(5)表示5進制數(shù).,十進制數(shù)一般不標注基數(shù).,【問題2】十進制數(shù)3721中的3表示3個千,7表示7個百,2表示2個十,1表示1個一,從而它可以寫成下面的形式:,3721=3103+7102+2101+1100.,【想一想】 二進制數(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ù),那么以k為基數(shù)的k進制數(shù)可以表示為一串數(shù)字連寫在一起的形式,anan-1a1a0(k) (0ank,0an-1,a1,a0k),意思是:(1)第一個數(shù)字an不能等于0; (2)每一個數(shù)字an,an-1,a1,a0都須小于k.,k進制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0 .,注意這是一個n+1位數(shù).,【問題3】二進制只用0和1兩個數(shù)字,這正好與電路的通和斷兩種狀態(tài)相對應(yīng),因此計算機內(nèi)部都使用二進制.計算機在進行數(shù)的運算時,先把接受到的數(shù)轉(zhuǎn)化成二進制數(shù)進行運算,再把運算結(jié)果轉(zhuǎn)化為十進制數(shù)輸出. 那么二進制數(shù)與十進制數(shù)之間是如何轉(zhuǎn)化的呢?,例1:把二進制數(shù)110011(2)化為十進制數(shù).,分析:先把二進制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式,再按照十進制數(shù)的運算規(guī)則計算出結(jié)果.,解:110011(2) =125+124+023+022+121+120 =132+116+12+1=51.,【問題4】 你會把三進制數(shù)10221(3)化為十進制數(shù)嗎?,解:10221(3)=134+033+232+231+130 =81+18+6+1=106.,例1 將下列各進制數(shù)化為十進制數(shù). （1）10303（4） ； （2）1234（5）.,理論遷移,10303（4）=144+342+340=307.,1234（5）=153+252+351+450=194.,p.48 3題（1）（3）,例2 已知10b1（2）=a02（3）, 求數(shù)字a，b的值.,所以2b+9=9a+2，即9a-2b=7.,10b1（2）=123+b2+1=2b+9.,a02（3）=a32+2=9a+2.,故a=1，b=1.,k進制數(shù)轉(zhuǎn)化為十進制數(shù)的方法,先把k進制的數(shù)表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即,anan-1a1a0(k) =ankn+an-1kn-1+a1k1+a0k0 .,再按照十進制數(shù)的運算規(guī)則計算出結(jié)果.,十進制數(shù)轉(zhuǎn)化為k進制數(shù)的方法？,【例1】把89化為二進制的數(shù).,分析:把89化為二進制的數(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=1011001(2).,可以用2連續(xù)去除89或所得商(一直到商為0為止),然后取余數(shù) -除2取余法.,2=12+0,1=02+1,44 1,【例1】把89化為二進制的數(shù).,我們可以用下面的除法算式表示除2取余法:,22 0,11 0,5 1,2 1,1 0,0 1,把算式中各步所得的余數(shù)從下到上排列,得到,89=1011001(2),這種方法也可以推廣為把十進制數(shù)化為k進制數(shù)的算法,稱為除k取余法.,可以用2連續(xù)去除89或所得商(一直到商為0為止),然后取余數(shù)-除2取余法.,【例2】把89化為五進制的數(shù).,解:以5作為除數(shù),相應(yīng)的除法算式為:,17 4,3 2,0 3,