高中數(shù)學(xué)必修三課件算法案例

1.3算法案例解：21824用公有質(zhì)因數(shù)2除，3912用公有質(zhì)因數(shù)3除，343和4互質(zhì)不除了。得：18和24最大公約數(shù)是：2×3＝6

想一想，如何求8251與6105的最大公約數(shù)？

例、求18與24的最大公約數(shù)：短除法案例1、8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用輾轉(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ù)思考1：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0解：輾轉(zhuǎn)相除法（歐幾里得算法）輾轉(zhuǎn)相除除法的程序框圖與程序開(kāi)始輸入m,n

r=mMODn m=nn=rr=0？輸出m結(jié)束否是

INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND《九章算術(shù)》——更相減損術(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ù)。例、用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。=7所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）98-63=35

63-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）程序：INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb>aTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND開(kāi)始輸入：a,b輸出：a×2i結(jié)束a=b?a=a/2,b=b/2是a=a-bt=a,a=b,b=tb>a?aMOD2=0且bMOD2=0?是否否否是i=0i=i+1秦九韶（約1202年－1261年）南宋官員、數(shù)學(xué)家，與李冶、楊輝、朱世杰并稱宋元數(shù)學(xué)四大家。主要成就:1247年完成了數(shù)學(xué)名著《數(shù)書九章》，其中的大衍求一術(shù)、三斜求積術(shù)和秦九韶算法是具有世界意義的重要貢獻(xiàn)。秦九韶算法就是中國(guó)古代數(shù)學(xué)的一枝奇葩。直到今天，這種算法仍是多項(xiàng)式求值比較先進(jìn)的算法。美國(guó)著名科學(xué)史家薩頓說(shuō)過(guò)，秦九韶是“他那個(gè)民族，他那個(gè)時(shí)代，并且確實(shí)也是所有時(shí)代最偉大的數(shù)學(xué)家之一”。

案例2、秦九韶算法知識(shí)探究(一):秦九韶算法的基本思想

思考1:對(duì)于多項(xiàng)式f(x)=x5+x4+x3+x2+x+1，怎么樣求f(5)的值呢？思考2:利用后一種算法求多項(xiàng)式f(x)=anxn+an-1xn-1+…+a1x+a0的值，這個(gè)多項(xiàng)式應(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

次乘法運(yùn)算，

次加法運(yùn)算.

nn例1已知一個(gè)5次多項(xiàng)式為用秦九韶算法求f(5)的值.f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=v2=v3=v4=v5=所以f(5)=14130.2.解：根據(jù)秦九韶算法，把多項(xiàng)式改寫成v0=4；4×5+2=22；22×5+3.5=113.5；113.5×5-2.6=564.9；2826.2；564.9×5+1.7=14130.2.2826.2×5-0.8=,求f(4)的值.f(x)=(((3x+2)x-9)x-11)x+1解：根據(jù)秦九韶算法，把多項(xiàng)式改寫成v1=v2=v3=v4=∴f(4)=709.v0=3；3×4+2=14；14×4-9=47；47×4-11=177；709；177×4+1=程序？INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi>=0INPUT“ai=”；a

v=v*x+ai=i-1

WENDPRINTvEND輸入n，an，x的值v=anv=vx+ai輸入aii≥0？i=n-1i=i-1是輸出v否結(jié)束開(kāi)始PRINT“i=”；i [問(wèn)題1]我們常見(jiàn)的數(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ù).案例3：進(jìn)位制

一般地,若k是一個(gè)大于1的整數(shù),那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式anan-1…a1a0(k) k進(jìn)制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1

+…+a1×k1+a0×k0.注意這是一個(gè)n+1位數(shù).例1:把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù).

分析:先把二進(jìn)制數(shù)寫成不同位上數(shù)字與2的冪的乘積之和的形式,再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.

k進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的方法

先把k進(jìn)制的數(shù)表示成不同位上數(shù)字與基數(shù)k的冪的乘積之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計(jì)算出結(jié)果.課堂練習(xí)：例：10231（4）=________

235（7）=________301124例2:把89化為二進(jìn)制的數(shù).

十進(jìn)制數(shù)轉(zhuǎn)化為k進(jìn)制數(shù)的方法441例2:把89化為二進(jìn)制的數(shù).我們可以用下面的除法算式表示除2取余法:289余數(shù)22202110251221210201把算式中各步所得的余數(shù)從下到上排列,得到89=1011001(2).這種方法也可以推廣為把十進(jìn)制數(shù)化為k進(jìn)制數(shù)的算法,稱為除k取余法.解：例3:把89化為五進(jìn)制的數(shù).解:以5作為除數(shù),相應(yīng)的除法算式為:174589余數(shù)532503∴89=32