【學(xué)案導(dǎo)學(xué)設(shè)計】學(xué)年高中數(shù)學(xué) 1.3 算法案例課堂教學(xué)課件2 新人教A必修3

第一章算法初步

1.3算法案例例：求下面兩個正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7思考：除了用這種方法外還有沒有其它方法？例：如何算出8251和6105的最大公約數(shù)？輾轉(zhuǎn)相除法與更相減損術(shù)一、輾轉(zhuǎn)相除法（歐幾里得算法）1、定義：所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。

2、步驟（以求8251和6105的最大公約數(shù)的過程為例）第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。為什么呢？第二步對6105和2146重復(fù)第一步的做法

6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。

完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例：用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)思考：從上面的兩個例子中可以看出計算的規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0

輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。m=n×q＋r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0思考：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？

程序框圖：開始輸入m,n

r=mMODn

m=nr=0?是否

n=r輸出m結(jié)束思考：你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎？程序：INPUT“m,n=”;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND1.定義：所謂更相減損術(shù)，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。二、更相減損術(shù)2、方法：例:用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝1414－7＝7所以，98和63的最大公約數(shù)等于7

INPUTm,nIFm<nTHENa=mm=nn=aENDIFK=0WHILEmMOD2=0ANDnMOD2=0m=m/2n=n/2k=k+1WENDd=m-nWHILEd<>n

IFd>nTHENm=d

ELSEm=nn=d

ENDIFd=m-nWENDd=2k*dPRINTdEND思考：你能根據(jù)更相減損術(shù)設(shè)計程序，求兩個正整數(shù)的最大公約數(shù)嗎？（1）設(shè)計求多項式當(dāng)x=5時的值的算法，并寫出程序。（2）有沒有更高效的算法？能否探求更好的算法，來解決任意多項式的求解問題？三、秦九韶算法引導(dǎo)學(xué)生把多項式變形為：思考：從內(nèi)到外，如果把每一個括號都看成一個常數(shù)，那么變形后的式子中有哪些“一次式”？x的系數(shù)依次是什么？（3）若若將將x的值值代代入入變變形形后后的的式式子子中中，，那那么么求將變變形形前前x的系系數(shù)數(shù)乘乘以以x的值值，，加加上上變變形形前前的的第第2個系系數(shù)數(shù)，，得得到到一一個個新新的的系系數(shù)數(shù)；；將將此此系系數(shù)數(shù)繼繼續(xù)續(xù)乘乘以以x的值值，，再再加加上上變變形形前前的的第第3個系系數(shù)數(shù)，，又又得得到到一一個個新新的的系系數(shù)數(shù)；；繼繼續(xù)續(xù)對對新新系系數(shù)數(shù)做做上上面面的的變變換換，，直直到到與與變變形形前前的的最最后后一一個個系系數(shù)數(shù)相相加加，，得得到到一一個個新新的的系系數(shù)數(shù)為為止止。。這這個個系系數(shù)數(shù)即即為為所所求求多多項項式式的的值值。。這這種種算算法法即即是是““秦秦九九韶韶算算法法””（4）用用秦秦九九韶韶算算法法求求多多項項式式的的值值，，與與多多項項式式組組成成有有直直接接關(guān)關(guān)系系嗎嗎？？用用秦秦九九韶韶算算法法計計算算上上述述多多項項式式的的值值，，需需要要多多少少次次乘乘法法運運算算和和多多少少次次加加法法運運算算？計算只與多項式的系數(shù)有關(guān)，

《數(shù)書書九九章章》————秦九九韶韶算算法法設(shè)是一個n次的多項式對該該多多項項式式按按下下面面的的方方式式進進行行改改寫寫：：思考考：：當(dāng)當(dāng)知知道道了了x的的值值后后該該如如何何求求多多項項式式的的值值？？這是是怎怎樣樣的的一一種種改改寫寫方方式式？？最最后后的的結(jié)結(jié)果果是是什什么么？？要求求多多項項式式的的值值，，應(yīng)應(yīng)該該先先算算最最內(nèi)內(nèi)層層的的一一次次多多項項式式的的值值，，即即然后后，，由由內(nèi)內(nèi)到到外外逐逐層層計計算算一一次次多多項項式式的的值值，，即即最后的一一項是什什么？這種將求求一個n次多項式式f(x)的值轉(zhuǎn)化化成求n個一次多多項式的的值的方方法，稱稱為秦九韶算算法。思考：在在求多項項式的值值上，這這是怎樣樣的一個個轉(zhuǎn)化？？程序框圖圖：這是一個個在秦九韶算算法中反反復(fù)執(zhí)行行的步驟驟，因此此可用循循環(huán)結(jié)構(gòu)構(gòu)來實現(xiàn)現(xiàn)。輸入ai開始輸入n,an,xi>=0?輸出v結(jié)束v=vx+aii=i-1YNi=n-1V=an秦九韶算算法的特特點：通過一次次式的反反復(fù)計算算，逐步步得出高高次多項項式的值值，對于于一個n次多項式式，只需需做n次乘法和和n次加法即即可。程序：INPUT““n=”；nINPUT““an=“;aINPUT““x=““;xv=ai=n-1WHILEi>=0PRINT““i=““;iINPUT““ai=“;av=v*x+ai=i-1WENDPRINTvEND四、進位位制1、什么是是進位制制？進位制是是人們?yōu)闉榱擞嫈?shù)數(shù)和運算算方便而而約定的的記數(shù)系系統(tǒng)。進位制是是一種記記數(shù)方式式，用有有限的數(shù)數(shù)字在不不同的位位置表示示不同的的數(shù)值。?？墒褂糜脭?shù)字符符號的個個數(shù)稱為為基數(shù)，，基數(shù)為為n，即可稱稱n進位制，，簡稱n進制。比如：滿二進一一，就是是二進制制；滿十進一一，就是是十進制制；滿十二進進一，就就是十二二進制；；滿六十進進一，就就是六十十進制基數(shù)：“滿幾進進一”就就是幾進進制，幾幾進制的的基數(shù)就就是幾.2、最常見見的進位位制是什什么？除除此之外外還有哪哪些常見見的進位位制？請請舉例說說明．最常見的的進位制制應(yīng)該是是我們數(shù)數(shù)學(xué)中的的十進制制,比如一般般的數(shù)值值計算，，但是并并不是生生活中的的每一種種數(shù)字都都是十進進制的.古人有半斤八兩兩之說，就就是十六六進制與與十進制制的轉(zhuǎn)換換.比如時間間和角度度的單位位用六十十進位制制,計算“一一打”數(shù)數(shù)值時是是12進制的。。電子計算算機用的的是二進進制。。式中1處在百位位，第一一個3所在十位位，第二二個3所在個位位，5和9分別處在在十分位位和百分分位。十十進制數(shù)數(shù)是逢十十進一的的。我們最常用最最熟悉的就是是十進制數(shù)，，它的數(shù)值部部分是十個不不同的數(shù)字符符號0，1，2，3，4，5，6，7，8，9來表示的。十進制：例如133.59，它可用一個個多項式來表表示：133.59=1*102+3*101+3*100+5*10-1+9*10-2實際上，十進進制數(shù)只是計計數(shù)法中的一一種，但它不不是唯一記數(shù)法。。除了十進制制數(shù)，生產(chǎn)生生活中還會遇遇到非十進制的記數(shù)制制。如時間：：60秒為1分，60分為1小時，它是六十進制的的。兩根筷子子一雙，兩只只手套為一副副，它們是二進制的。。其它進制：二進制、七進進制、八進制制、十二進制制、六十進制制……二進制只有0和1兩個數(shù)字，七七進制用0~6七個數(shù)字十六進制有0~9十個數(shù)字及ABCDEF六個字母.為了區(qū)分不同同的進位制，，常在數(shù)的右右下角標(biāo)明基基數(shù)，十進制制一般不標(biāo)注注基數(shù).例如十進制的的133.59，寫成133.59(10)七進制的13，寫成13(7)；二進制的10，寫成10(2)一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進制可以表示為一串?dāng)?shù)字連寫在一起的形式：十進制的構(gòu)成成十進制由兩個個部分構(gòu)成例如：3721其它進位制的的數(shù)又是如何何的呢？第一、它有0～9十個數(shù)字；第二、它有“數(shù)位”，即從右往左為個位、十位、百位、千位等等。(用10個數(shù)字來記數(shù)數(shù)，稱基數(shù)為為10)表示有：1個1，2個十，7個百即7個10的平方，3個千即3個10的立方十進制：“滿十進一”其它進制數(shù)化化成十進制數(shù)數(shù)公式二進制二進制是用0、1兩個數(shù)字來描描述的．如11001二進制的表示示方法區(qū)分的寫法：：11001（2）或者(11001)2八進制呢？如7342(8)k進制呢？anan-1an-2…a1(k)？二進制與十進進制的轉(zhuǎn)換1、二進制數(shù)轉(zhuǎn)轉(zhuǎn)化為十進制制數(shù)例1：將二進制數(shù)數(shù)110011(2)化成十進制數(shù)數(shù)。解：根據(jù)進位制的的定義可知所以，110011（2）=51．例2、設(shè)計一個算算法，將k進制數(shù)a(共有n位)轉(zhuǎn)換為十進制制數(shù)b。(1)算法步驟:第一步，輸入入a,k和n的值；第二步，將b的值初始化為為0,i的值初始化為為1；第三步，b=b+ai*ki-1,i=i+1第四步，判斷斷i>n是否成立.若是,則執(zhí)行第五步步,否則,返回第三步；；第五步，輸出出b的值.(2)程序框圖:開始輸入a,k,nb=0i=1把a的右數(shù)第i位數(shù)字賦給tb=b+t*ki-1i=i+1i>n?否是輸出b結(jié)束(3)程序：INPUT““a,k,n=”;a,k,nb=0i=1t=aMOD10DOb=b+t*k^(i-1)a=a\10t=aMOD10i=i+1LOOPUNTILi>nPRINTbEND**上面的程程序如采用get函數(shù),可簡化為：INPUTa,k,ni=1b=0WHILEi<=nt=GETa[i]b=t*k^(i-1)+bi=i+1WENDPRINTbEND備注:GET函數(shù)用于取出出a的右數(shù)第i位數(shù)方法：除2取余法，即用用2連續(xù)去除89或所得的商，，然后取余數(shù)數(shù)。例、把89化為二進制數(shù)數(shù)解：根據(jù)“逢二進進一”的原則則，有89＝2×44＋1＝2×(2×22＋0)+1＝2×(2××(2×11＋0)+0)+1＝2×(2××(2×(2×5＋1)+0)+0)+15＝2×2＋1＝2×（2×（2×（2×（22＋1）＋