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

第一章算法初步

1.3算法案例編輯ppt例：求下面兩個(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ù)編輯ppt一、輾轉(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ù)。

編輯ppt完整的過程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編輯ppt

輾轉(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)？

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

r=mMODn

m=nr=0?是否

n=r輸出m結(jié)束思考：你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？編輯ppt程序：INPUT“m,n=”;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND編輯ppt1.定義：所謂更相減損術(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

編輯pptINPUTm,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ù)嗎？編輯ppt（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ù)依次是什么？編輯ppt（3）若將x的值代入變形后的式子中，那么求值的計(jì)算過程是怎樣的？

將變形前x的系數(shù)乘以x的值，加上變形前的第2個(gè)系數(shù)，得到一個(gè)新的系數(shù)；將此系數(shù)繼續(xù)乘以x的值，再加上變形前的第3個(gè)系數(shù)，又得到一個(gè)新的系數(shù)；繼續(xù)對(duì)新系數(shù)做上面的變換，直到與變形前的最后一個(gè)系數(shù)相加，得到一個(gè)新的系數(shù)為止。這個(gè)系數(shù)即為所求多項(xiàng)式的值。這種算法即是“秦九韶算法”（4）用秦九韶算法求多項(xiàng)式的值，與多項(xiàng)式組成有直接關(guān)系嗎？用秦九韶算法計(jì)算上述多項(xiàng)式的值，需要多少次乘法運(yùn)算和多少次加法運(yùn)算？

計(jì)算只與多項(xiàng)式的系數(shù)有關(guān)，

編輯ppt《數(shù)書九章》——秦九韶算法

設(shè)是一個(gè)n次的多項(xiàng)式對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫：思考：當(dāng)知道了x的值后該如何求多項(xiàng)式的值？這是怎樣的一種改寫方式？最后的結(jié)果是什么？編輯ppt要求多項(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)化？編輯ppt程序框圖：這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。輸入ai開始輸入n,an,xi>=0?輸出v結(jié)束v=vx+aii=i-1YNi=n-1V=an秦九韶算法的特點(diǎn)：

通過一次式的反復(fù)計(jì)算，逐步得出高次多項(xiàng)式的值，對(duì)于一個(gè)n次多項(xiàng)式，只需做n次乘法和n次加法即可。編輯ppt程序：INPUT“n=”；nINPUT“an=“;aINPUT“x=“;xv=ai=n-1WHILEi>=0PRINT“i=“;iINPUT“ai=“;av=v*x+ai=i-1WENDPRINTvEND編輯ppt四、進(jìn)位制1、什么是進(jìn)位制？進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)。進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡稱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)制的基數(shù)就是幾.編輯ppt2、最常見的進(jìn)位制是什么？除此之外還有哪些常見的進(jìn)位制？請(qǐng)舉例說明．最常見的進(jìn)位制應(yīng)該是我們數(shù)學(xué)中的十進(jìn)制,比如一般的數(shù)值計(jì)算，但是并不是生活中的每一種數(shù)字都是十進(jìn)制的.古人有半斤八兩之說，就是十六進(jìn)制與十進(jìn)制的轉(zhuǎn)換.比如時(shí)間和角度的單位用六十進(jìn)位制,計(jì)算“一打”數(shù)值時(shí)是12進(jìn)制的。電子計(jì)算機(jī)用的是二進(jìn)制。編輯ppt式中1處在百位，第一個(gè)3所在十位，第二個(gè)3所在個(gè)位，5和9分別處在十分位和百分位。十進(jìn)制數(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è)多項(xiàng)式來表示：133.59=1*102+3*101+3*100+5*10-1+9*10-2編輯ppt實(shí)際上，十進(jìn)制數(shù)只是計(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)制只有0和1兩個(gè)數(shù)字，七進(jìn)制用0~6七個(gè)數(shù)字十六進(jìn)制有0~9十個(gè)數(shù)字及ABCDEF六個(gè)字母.編輯ppt

為了區(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ù)字連寫在一起的形式：編輯ppt十進(jìn)制的構(gòu)成十進(jìn)制由兩個(gè)部分構(gòu)成例如：3721其它進(jìn)位制的數(shù)又是如何的呢？第一、它有0～9十個(gè)數(shù)字；第二、它有“數(shù)位”，即從右往左為個(gè)位、十位、百位、千位等等。(用10個(gè)數(shù)字來記數(shù)，稱基數(shù)為10)表示有：1個(gè)1，2個(gè)十，7個(gè)百即7個(gè)10的平方，3個(gè)千即3個(gè)10的立方十進(jìn)制：“滿十進(jìn)一”編輯ppt其它進(jìn)制數(shù)化成十進(jìn)制數(shù)公式編輯ppt二進(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)？編輯ppt二進(jìn)制與十進(jìn)制的轉(zhuǎn)換1、二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)例1：將二進(jìn)制數(shù)110011(2)化成十進(jìn)制數(shù)。解：根據(jù)進(jìn)位制的定義可知所以，110011（2）=51．編輯ppt例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的值.編輯ppt(2)程序框圖:開始輸入a,k,nb=0i=1把a(bǔ)的右數(shù)第i位數(shù)字賦給tb=b+t*ki-1i=i+1i>n?否是輸出b結(jié)束編輯ppt(3)程序：INPUT“a,k,n=”;a,k,nb=0i=1t=aMOD10DOb=b+t*k^(i-1)a=a\10t=aMOD10i=i+1LOOPUNTILi>nPRINTbEND編輯ppt**上面的程序如采用get函數(shù),可簡化為：INPUTa,k,ni=1b=0WHILEi<=nt=GETa[i]b=t*k^(i-1)+bi=i+1WENDPRINTbEND備注:GET函數(shù)用于取出a的右數(shù)第i位數(shù)編輯ppt方法：除2取余法，即用2連續(xù)去除89或所得的商，然后取余數(shù)。例、把89化為二進(jìn)制數(shù)解：根據(jù)“逢二進(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）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝2×（2×（2×（23＋2＋1）＋0）＋