高中數(shù)學(xué)第一章算法初步1.3算法案例

第一章算法初步

1.3算法案例1/3135915[問題1]：在小學(xué)，我們已經(jīng)學(xué)過求最大條約數(shù)知識，你能求出18與30最大條約數(shù)嗎？〖創(chuàng)設(shè)情景，揭示課題〗183023∴18和30最大條約數(shù)是2×3=6.先用兩個數(shù)公有質(zhì)因數(shù)連續(xù)去除,一直除到所得商是互質(zhì)數(shù)為止,然后把全部除數(shù)連乘起來.案例1輾轉(zhuǎn)相除法與更相減損術(shù)2/31〖創(chuàng)設(shè)情景，揭示課題〗[問題2]:我們都是利用找條約數(shù)方法來求最大條約數(shù)，假如兩個數(shù)比較大而且依據(jù)我們觀察又不能得到一些條約數(shù)，我們又應(yīng)該怎樣求它們最大條約數(shù)？比如求8251與6105最大條約數(shù)?3/31〖研探新知〗1.輾轉(zhuǎn)相除法:例1求兩個正數(shù)8251和6105最大條約數(shù)。 分析：8251與6105兩數(shù)都比較大，而且沒有顯著條約數(shù)，如能把它們都變小一點，依據(jù)已經(jīng)有知識即可求出最大條約數(shù).解：8251＝6105×1＋2146 顯然8251與6105最大條約數(shù)也必是2146約數(shù)，一樣6105與2146條約數(shù)也必是8251約數(shù)，所以8251與6105最大條約數(shù)也是6105與2146最大條約數(shù)。4/311.輾轉(zhuǎn)相除法:例1求兩個正數(shù)8251和6105最大條約數(shù)。解：8251＝6105×1＋2146;6105＝2146×2＋1813;2146＝1813×1＋333;1813＝333×5＋148;333＝148×2＋37;148＝37×4＋0.則37為8251與6105最大條約數(shù)。 以上我們求最大條約數(shù)方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出。5/31第一步,給定兩個正數(shù)m,n第二步,計算m除以n所得到余數(shù)r第三步,m=n,n=r第四步,若r=0,則m,n最大條約數(shù)等于m;不然返回第二步輾轉(zhuǎn)相除法求最大條約數(shù)算法：思索：需不需要比較m，n大小不需要6/31否開始輸入兩個正數(shù)m,nr=mMODnr=0?輸出m結(jié)束m=nn=r是程序框圖7/312.更相減損術(shù): 我國早期也有處理求最大條約數(shù)問題算法，就是更相減損術(shù)。 更相減損術(shù)求最大條約數(shù)步驟以下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。 翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。 第二步：以較大數(shù)減去較小數(shù)，接著把較小數(shù)與所得差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求最大條約數(shù)。8/31例2用更相減損術(shù)求98與63最大條約數(shù). 解：因為63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98與63最大條約數(shù)是7。練習(xí)2：用更相減損術(shù)求兩個正數(shù)84與72最大條約數(shù)。(12)9/31輾轉(zhuǎn)相除法與更相減損術(shù)比較: （1）都是求最大條約數(shù)方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主;計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，尤其當(dāng)兩個數(shù)字大小區(qū)分較大時計算次數(shù)區(qū)分較顯著。 （2）從結(jié)果表達形式來看，輾轉(zhuǎn)相除法表達結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到.10/31〖教學(xué)設(shè)計〗[問題1]設(shè)計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時值算法,并寫出程序.x=5f=2＊x^5-5＊x^4-4＊x^3+3＊x^2-6＊x+7PRINTfEND程序點評:上述算法一共做了15次乘法運算,5次加法運算.優(yōu)點是簡單,易懂;缺點是不通用,不能處理任意多項式求值問題,而且計算效率不高.n次多項式至多n(n+1)/2次乘法運算和n次加法運算案例2秦九韶算法11/31 這析計算上述多項式值,一共需要9次乘法運算,5次加法運算.[問題2]有沒有更高效算法? 分析:計算x冪時,能夠利用前面計算結(jié)果,以降低計算量, 即先計算x2,然后依次計算值. 第二種做法與第一個做法相比,乘法運算次數(shù)降低了,因而能提升運算效率.而且對于計算機來說,做一次乘法所需運算時間比做一次加法要長得多,所以第二種做法能更加快地得到結(jié)果.12/31

[問題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+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,當(dāng)x=5時,多項式值是2677.這種求多項式值方法就叫秦九韶算法.變?yōu)榍髱讉€一次式值幾個乘法幾個加法？秦九韶《數(shù)書九章》.13/312-50-43-60x=5105252512512160560830403034所以,當(dāng)x=5時,多項式值是15170.練習(xí):用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時值.解:原多項式先化為:f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0列表21517015170注意:n次多項式有n+1項,所以缺乏哪一項應(yīng)將其系數(shù)補0.14/31f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.我們能夠改寫成以下形式:f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0. 求多項式值時,首先計算最內(nèi)層括號內(nèi)一次多項式值,即

v1=anx+an-1,然后由內(nèi)向外逐層計算一次多項式值,即 普通地,對于一個n次多項式v2=v1x+an-2,v3=v2x+an-3,……,vn=vn-1x+a0. 這么,求n次多項式f(x)值就轉(zhuǎn)化為求n個一次多項式值.這種算法稱為秦九韶算法.15/31 點評:秦九韶算法是求一元多項式值一個方法.

它特點是:把求一個n次多項式值轉(zhuǎn)化為求n個一次多項式值,經(jīng)過這種轉(zhuǎn)化,把運算次數(shù)由至多n(n+1)/2次乘法運算和n次加法運算,降低為n次乘法運算和n次加法運算,大大提升了運算效率.16/31v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3,……,vn=vn-1x+a0. 觀察上述秦九韶算法中n個一次式,可見vk計算要用到vk-1值.若令v0=an,得v0=an,vK=vK-1x+an-k(k=1,2,……,n） 這是一個在秦九韶算法中重復(fù)執(zhí)行步驟,所以可用循環(huán)結(jié)構(gòu)來實現(xiàn).17/31第一步,輸入多項式次數(shù)n、最高次項系數(shù)an和x值第二步,將v值初始化為an，將i值初始化為n-1第三步,輸入i次項系數(shù)ai第四步,v=vx+ai,i=i-1第五步,若i>=0,則返回第三步，不然輸出v算法分析：18/31否程序框圖開始輸入n,an,x值輸入aii>=0?i=n-1v=anv=vx+aii=i-1輸出v結(jié)束是19/31

[問題1]我們常見數(shù)字都是十進制,不過并不是生活中每一個數(shù)字都是十進制.比如時間和角度單位用六十進位制,電子計算機用是二進制.那么什么是進位制?不一樣進位制之間又有什么聯(lián)絡(luò)呢? 進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定一個記數(shù)系統(tǒng)，約定滿二進一,就是二進制;滿十進一,就是十進制;滿十六進一,就是十六進制;等等.“滿幾進一”,就是幾進制,幾進制基數(shù)就是幾. 可使用數(shù)字符號個數(shù)稱為基數(shù).基數(shù)都是大于1整數(shù).案例3進位制20/31 如二進制可使用數(shù)字有0和1,基數(shù)是2;

十進制可使用數(shù)字有0,1,2,…,8,9等十個數(shù)字,基數(shù)是10;

十六進制可使用數(shù)字或符號有0~9等10個數(shù)字以及A~F等6個字母(要求字母A~F對應(yīng)10~15),十六進制基數(shù)是16. 注意:為了區(qū)分不一樣進位制,常在數(shù)字右下腳標(biāo)明基數(shù),.如111001(2)表示二進制數(shù),34(5)表示5進制數(shù).十進制數(shù)普通不標(biāo)注基數(shù).21/31[問題2]十進制數(shù)3721中3表示3個千,7表示7個百,2表示2個十,1表示1個一,從而它能夠?qū)懗上旅嫘问?3721=3×103+7×102+2×101+1×100. 想一想二進制數(shù)1011(2)能夠類似寫成什么形式?1011(2)=1×23+0×22+1×21+1×20.同理:3421(5)=3×53+4×52+2×51+1×50.C7A16(16)=12×164+7×163+10×162

+1×161+6×160.22/31 普通地,若k是一個大于1整數(shù),那么以k為基數(shù)k進制數(shù)能夠表示為一串?dāng)?shù)字連寫在一起形式anan-1…a1a0(k)(0<an<k,0≤an-1,…,a1,a0<k)意思是:(1)第一個數(shù)字an不能等于0;(2)每一個數(shù)字an,an-1,…,a1,a0都須小于k.

k進制數(shù)也能夠表示成不一樣位上數(shù)字與基數(shù)k冪乘積之和形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1

+…+a1×k1+a0×k0.注意這是一個n+1位數(shù).23/31

[問題3]二進制只用0和1兩個數(shù)字,這恰好與電路通和斷兩種狀態(tài)相對應(yīng),所以計算機內(nèi)部都使用二進制.計算機在進行數(shù)運算時,先把接收到數(shù)轉(zhuǎn)化成二進制數(shù)進行運算,再把運算結(jié)果轉(zhuǎn)化為十進制數(shù)輸出.

那么二進制數(shù)與十進制數(shù)之間是怎樣轉(zhuǎn)化呢?24/31例3:把二進制數(shù)110011(2)化為十進制數(shù). 分析:先把二進制數(shù)寫成不一樣位上數(shù)字與2冪乘積之和形式,再按照十進制數(shù)運算規(guī)則計算出結(jié)果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.

25/31

k進制數(shù)轉(zhuǎn)化為十進制數(shù)方法 先把k進制數(shù)表示成不一樣位上數(shù)字與基數(shù)k冪乘積之和形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十進制數(shù)運算規(guī)則計算出結(jié)果.26/31例4:把89化為二進制數(shù). 分析:把89化為二進制數(shù),需想方法將89先寫成以下形式89=an×2n+an-1×2n-1+…+a1×21+a0×20.27/3189=44×2+1,44=22×2+0,22=11×2+0,11=5×2+1,5=2×2+1,89=44×2+1,=(22×2+0)×2+1=((11×2+0)×2+0)×2+1=(((5×2+1)×2+0)×2+0)×2+1=((((2×2+1)×2+1)×2+0)×2+0)×2+1=(((((1×2)+0)×2+1)×2+1)×2+0)×