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

1.3算法案例1/3435915[問題1]：在小學，我們已經學過求最大條約數(shù)知識，你能求出18與30最大條約數(shù)嗎？183023∴18和30最大條約數(shù)是2×3=6.先用兩個數(shù)公有質因數(shù)連續(xù)去除,一直除到所得商是互質數(shù)為止,然后把全部除數(shù)連乘起來.案例1輾轉相除法與更相減損術2/34[問題2]:我們都是利用找條約數(shù)方法來求最大條約數(shù)，假如兩個數(shù)比較大而且依據我們觀察又不能得到一些條約數(shù)，我們又應該怎樣求它們最大條約數(shù)？比如求8251與6105最大條約數(shù)?3/34〖研探新知〗1.輾轉相除法:例1求兩個正數(shù)8251和6105最大條約數(shù)。 分析：8251與6105兩數(shù)都比較大，而且沒有顯著條約數(shù)，如能把它們都變小一點，依據已經有知識即可求出最大條約數(shù).解：8251＝6105×1＋2146 顯然8251與6105最大條約數(shù)也必是2146約數(shù)，一樣6105與2146條約數(shù)也必是8251約數(shù)，所以8251與6105最大條約數(shù)也是6105與2146最大條約數(shù)。4/341.輾轉相除法:例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ù)方法就是輾轉相除法。也叫歐幾里德算法，它是由歐幾里德在公元前3左右首先提出。5/34第一步,給定兩個正數(shù)m,n第二步,計算m除以n所得到余數(shù)r第三步,m=n,n=r第四步,若r=0,則m,n最大條約數(shù)等于m;不然返回第二步輾轉相除法求最大條約數(shù)算法：思索：需不需要比較m，n大小不需要6/34否開始輸入兩個正數(shù)m,nr=mMODnr=0?輸出m結束m=nn=r是程序框圖7/34練習1：利用輾轉相除法求兩數(shù)4081與20723最大條約數(shù).(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.8/342.更相減損術: 我國早期也有處理求最大條約數(shù)問題算法，就是更相減損術. 更相減損術求最大條約數(shù)步驟以下：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之. 翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù).若是，用2約簡；若不是，執(zhí)行第二步. 第二步：以較大數(shù)減去較小數(shù)，接著把較小數(shù)與所得差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得數(shù)相等為止，則這個數(shù)（或這個數(shù)與約減數(shù)乘積）就是所求最大條約數(shù).9/34例2用更相減損術求98與63最大條約數(shù). 解：因為63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98與63最大條約數(shù)是7。練習2：用更相減損術求兩個正數(shù)84與72最大條約數(shù)。(12)10/34INPUTm,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思索：你能依據更相減損術設計程序，求兩個正整數(shù)最大條約數(shù)嗎？11/34輾轉相除法與更相減損術比較: （1）都是求最大條約數(shù)方法，計算上輾轉相除法以除法為主，更相減損術以減法為主;計算次數(shù)上輾轉相除法計算次數(shù)相對較少，尤其當兩個數(shù)字大小區(qū)分較大時計算次數(shù)區(qū)分較顯著。 （2）從結果表達形式來看，輾轉相除法表達結果是以相除余數(shù)為0則得到，而更相減損術則以減數(shù)與差相等而得到.12/34[問題1]設計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當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秦九韶算法13/34 這析計算上述多項式值,一共需要9次乘法運算,5次加法運算.[問題2]有沒有更高效算法? 分析:計算x冪時,能夠利用前面計算結果,以降低計算量, 即先計算x2,然后依次計算值. 第二種做法與第一個做法相比,乘法運算次數(shù)降低了,因而能提升運算效率.而且對于計算機來說,做一次乘法所需運算時間比做一次加法要長得多,所以第二種做法能更加快地得到結果.14/34 [問題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所以,當x=5時,多項式值是2677.這種求多項式值方法就叫秦九韶算法.變?yōu)榍髱讉€一次式值幾個乘法幾個加法？秦九韶《數(shù)書九章》.15/342-50-43-60x=5105252512512160560830403034所以,當x=5時,多項式值是15170.練習:用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當x=5時值.解:原多項式先化為:

f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0列表21517015170注意:n次多項式有n+1項,所以缺乏哪一項應將其系數(shù)補0.16/34f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.我們能夠改寫成以下形式:f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0. 求多項式值時,首先計算最內層括號內一次多項式值,即

v1=anx+an-1,然后由內向外逐層計算一次多項式值,即 普通地,對于一個n次多項式v2=v1x+an-2,v3=v2x+an-3,……,vn=vn-1x+a0. 這么,求n次多項式f(x)值就轉化為求n個一次多項式值.這種算法稱為秦九韶算法.17/34 點評:秦九韶算法是求一元多項式值一個方法. 它特點是:把求一個n次多項式值轉化為求n個一次多項式值,經過這種轉化,把運算次數(shù)由至多n(n+1)/2次乘法運算和n次加法運算,降低為n次乘法運算和n次加法運算,大大提升了運算效率.18/34v1=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） 這是一個在秦九韶算法中重復執(zhí)行步驟,所以可用循環(huán)結構來實現(xiàn).19/34第一步,輸入多項式次數(shù)n、最高次項系數(shù)an和x值第二步,將v值初始化為an，將i值初始化為n-1第三步,輸入i次項系數(shù)ai第四步,v=vx+ai,i=i-1第五步,若i>=0,則返回第三步，不然輸出v算法分析：20/34否程序框圖開始輸入n,an,x值輸入aii>=0?i=n-1v=anv=vx+aii=i-1輸出v結束是21/34 [問題1]我們常見數(shù)字都是十進制,不過并不是生活中每一個數(shù)字都是十進制.比如時間和角度單位用六十進位制,電子計算機用是二進制.那么什么是進位制?不一樣進位制之間又有什么聯(lián)絡呢? 進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定一個記數(shù)系統(tǒng)，約定滿二進一,就是二進制;滿十進一,就是十進制;滿十六進一,就是十六進制;等等.“滿幾進一”,就是幾進制,幾進制基數(shù)就是幾.可使用數(shù)字符號個數(shù)稱為基數(shù).基數(shù)都是大于1整數(shù).案例3進位制22/34 如二進制可使用數(shù)字有0和1,基數(shù)是2;十進制可使用數(shù)字有0,1,2,…,8,9等十個數(shù)字,基數(shù)是10;十六進制可使用數(shù)字或符號有0~9等10個數(shù)字以及A~F等6個字母(要求字母A~F對應10~15),十六進制基數(shù)是16. 注意:為了區(qū)分不一樣進位制,常在數(shù)字右下腳標明基數(shù),.如111001(2)表示二進制數(shù),34(5)表示5進制數(shù).十進制數(shù)普通不標注基數(shù).23/34[問題2]十進制數(shù)3721中3表示3個千,7表示7個百,2表示2個十,1表示1個一,從而它能夠寫成下面形式: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.24/34 普通地,若k是一個大于1整數(shù),那么以k為基數(shù)k進制數(shù)能夠表示為一串數(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ù).25/34 [問題3]二進制只用0和1兩個數(shù)字,這恰好與電路通和斷兩種狀態(tài)相對應,所以計算機內部都使用二進制.計算機在進行數(shù)運算時,先把接收到數(shù)轉化成二進制數(shù)進行運算,再把運算結果轉化為十進制數(shù)輸出. 那么二進制數(shù)與十進制數(shù)之間是怎樣轉化呢?26/34例3:把二進制數(shù)110011(2)化為十進制數(shù). 分析:先把二進制數(shù)寫成不一樣位上數(shù)字與2冪乘積之和形式,再按照十進制數(shù)運算規(guī)則計算出結果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.

27/34

k進制數(shù)轉化為十進制數(shù)方法 先把k進制數(shù)表示成不一樣位上數(shù)字與基數(shù)k冪乘積之和形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十進制數(shù)運算規(guī)則計算出結果.28/34例4:把89化為二進制數(shù). 分析:把89化為二進制數(shù),需想方法將89先寫成以下形式89=an×2n+an-1×2n-1+…+a1×21+a0×20.29/3489=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)×2+0)×2+1=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1011001(2).能夠用2連續(xù)去除89或所得商(一直到商為0為止),然后取余數(shù)---除2取余法.2=1×2+0,1=0×2+1,30/3444