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

第一章算法初步

1.3算法案例例：求下面兩個(gè)正整數(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)相除法，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(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=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。為什么呢？第二步對(duì)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ù)思考：從上面的兩個(gè)例子中可以看出計(jì)算的規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0

輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實(shí)際上是一個(gè)循環(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)相除法編成一個(gè)計(jì)算機(jī)程序嗎？程序：INPUT“m,n=”;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND1.定義：所謂更相減損術(shù)，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時(shí)相等的兩數(shù)便為原來兩個(gè)數(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è)計(jì)程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？（1）設(shè)計(jì)求多項(xiàng)式當(dāng)x=5時(shí)的值的算法，并寫出程序。（2）有沒有更高效的算法？能否探求更好的算法，來解決任意多項(xiàng)式的求解問題？三、秦九韶算法引導(dǎo)學(xué)生把多項(xiàng)式變形為：思考：從內(nèi)到外，如果把每一個(gè)括號(hào)都看成一個(gè)常數(shù)，那么變形后的式子中有哪些“一次式”？x的系數(shù)依次是什么？（3）若若將將x的值值代代入入變變形形后后的的式式子子中中，，那那么么求將變變形形前前x的系系數(shù)數(shù)乘乘以以x的值值，，加加上上變變形形前前的的第第2個(gè)系系數(shù)數(shù)，，得得到到一一個(gè)個(gè)新新的的系系數(shù)數(shù)；；將將此此系系數(shù)數(shù)繼繼續(xù)續(xù)乘乘以以x的值值，，再再加加上上變變形形前前的的第第3個(gè)系系數(shù)數(shù)，，又又得得到到一一個(gè)個(gè)新新的的系系數(shù)數(shù)；；繼繼續(xù)續(xù)對(duì)對(duì)新新系系數(shù)數(shù)做做上上面面的的變變換換，，直直到到與與變變形形前前的的最最后后一一個(gè)個(gè)系系數(shù)數(shù)相相加加，，得得到到一一個(gè)個(gè)新新的的系系數(shù)數(shù)為為止止。。這這個(gè)個(gè)系系數(shù)數(shù)即即為為所所求求多多項(xiàng)項(xiàng)式式的的值值。。這這種種算算法法即即是是““秦秦九九韶韶算算法法””（4）用用秦秦九九韶韶算算法法求求多多項(xiàng)項(xiàng)式式的的值值，，與與多多項(xiàng)項(xiàng)式式組組成成有有直直接接關(guān)關(guān)系系嗎嗎？？用用秦秦九九韶韶算算法法計(jì)計(jì)算算上上述述多多項(xiàng)項(xiàng)式式的的值值，，需需要要多多少少次次乘乘法法運(yùn)運(yùn)算算和和多多少少次次加加法法運(yùn)運(yùn)算算？計(jì)算只與多項(xiàng)式的系數(shù)有關(guān)，

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