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

第一章算法初步

1.3算法案例35915[問題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ù)〖創(chuàng)設(shè)情景，揭示課題〗[問題2]:我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果兩個數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)?〖研探新知〗1.輾轉(zhuǎn)相除法:例1求兩個正數(shù)8251和6105的最大公約數(shù)。 分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，根據(jù)已有的知識即可求出最大公約數(shù).解：8251＝6105×1＋2146 顯然8251與6105的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù)。1.輾轉(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年左右首先提出的。第一步,給定兩個正數(shù)m,n第二步,計算m除以n所得到余數(shù)r第三步,m=n,n=r第四步,若r=0,則m,n的最大公約數(shù)等于m;否則返回第二步輾轉(zhuǎn)相除法求最大公約數(shù)算法：思考：需不需要比較m，n的大小不需要否開始輸入兩個正數(shù)m,nr=mMODnr=0?輸出m結(jié)束m=nn=r是程序框圖練習(xí)1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.2.更相減損術(shù): 我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。 更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。 翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(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＝21;21－7＝14;14－7＝7.所以，98與63的最大公約數(shù)是7。練習(xí)2：用更相減損術(shù)求兩個正數(shù)84與72的最大公約數(shù)。(12)輾轉(zhuǎn)相除法法與更相減減損術(shù)的比比較:（1）都是求最最大公約數(shù)數(shù)的方法，，計算上輾輾轉(zhuǎn)相除法法以除法為為主，更相相減損術(shù)以以減法為主主;計算次數(shù)上上輾轉(zhuǎn)相除除法計算次次數(shù)相對較較少，特別別當(dāng)兩個數(shù)數(shù)字大小區(qū)區(qū)別較大時時計算次數(shù)數(shù)的區(qū)別較較明顯。（2）從結(jié)果體體現(xiàn)形式來來看，輾轉(zhuǎn)轉(zhuǎn)相除法體體現(xiàn)結(jié)果是是以相除余余數(shù)為0則得到，而而更相減損損術(shù)則以減減數(shù)與差相相等而得到到.〖教學(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秦九韶算法法這析計算上上述多項式式的值,一共需要9次乘法運算算,5次加法運算算.[問題2]有沒有更高高效的算法法?分析:計算x的冪時,可以利用前前面的計算算結(jié)果,以減少計算算量,即先計算x2,然后依次計計算的值.第二種做法與與第一種做法法相比,乘法的運算次次數(shù)減少了,因而能提高運運算效率.而且對于計算算機(jī)來說,做一次乘法所所需的運算時時間比做一次次加法要長得得多,因此第二種做做法能更快地地得到結(jié)果.[問題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ù)書九章》.2-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.f(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)層括號內(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個一次多項式式的值.這種算法稱為為秦九韶算法.點評:秦九韶算法是是求一元多項項式的值的一一種方法.它的特點是:把求一個n次多項式的值值轉(zhuǎn)化為求n個一次多項式式的值,通過這種轉(zhuǎn)化化,把運算的次數(shù)數(shù)由至多n(n+1)/2次乘法運算和和n次加法運算,減少為n次乘法運算和和n次加法法運算算,大大提提高了了運算算效率率.v1=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ù)復(fù)執(zhí)行行的步步驟,因此可可用循循環(huán)結(jié)結(jié)構(gòu)來來實現(xiàn)現(xiàn).第一步步,輸入多多項式式次數(shù)數(shù)n、最高高次項項的系系數(shù)an和x的值第二步步,將v的值初初始化化為an，將i的值初初始化化為n-1第三步步,輸入i次項的的系數(shù)數(shù)ai第四步步,v=vx+ai,i=i-1第五步步,若i>=0,則返回回第三三步，，否則則輸出出v算法分分析：：否程序框框圖開始輸入n,an,x的值輸入aii>=0?i=n-1v=anv=vx+aii=i-1輸出v結(jié)束是[問題1]我們常常見的的數(shù)字字都是是十進(jìn)進(jìn)制的的,但是并并不是是生活活中的的每一一種數(shù)數(shù)字都都是十十進(jìn)制制的.比如時時間和和角度度的單單位用用六十十進(jìn)位位制,電子計計算機(jī)機(jī)用的的是二二進(jìn)制制.那么什什么是是進(jìn)位位制?不同的的進(jìn)位位制之之間又又有什什么聯(lián)聯(lián)系呢呢?進(jìn)位位制制是是人人們們?yōu)闉榱肆擞嬘嫈?shù)數(shù)和和運運算算的的方方便便而而約約定定的的一一種種記記數(shù)數(shù)系系統(tǒng)統(tǒng)，，約約定定滿滿二二進(jìn)進(jìn)一一,就是是二二進(jìn)進(jìn)制制;滿十十進(jìn)進(jìn)一一,就是是十十進(jìn)進(jìn)制制;滿十十六六進(jìn)進(jìn)一一,就是是十十六六進(jìn)進(jìn)制制;等等等.“滿滿幾幾進(jìn)進(jìn)一一””,就是是幾幾進(jìn)進(jìn)制制,幾進(jìn)進(jìn)制制的的基數(shù)數(shù)就是是幾幾.可使使用用數(shù)數(shù)字字符符號號的的個個數(shù)數(shù)稱稱為為基基數(shù)數(shù).基數(shù)數(shù)都都是是大大于于1的整整數(shù)數(shù).案例例3進(jìn)位位制制如二二進(jìn)進(jìn)制制可可使使用用的的數(shù)數(shù)字字有有0和1,基數(shù)數(shù)是是2;十進(jìn)進(jìn)制制可可使使用用的的數(shù)數(shù)字字有有0,1,2,……,8,9等十十個個數(shù)數(shù)字字,基數(shù)數(shù)是是10;十六六進(jìn)進(jìn)制制可可使使用用的的數(shù)數(shù)字字或或符符號號有有0~9等10個數(shù)數(shù)字字以以及及A~F等6個字字母母(規(guī)定定字字母母A~F對應(yīng)10~15),十六進(jìn)制制的基數(shù)數(shù)是16.注意:為了區(qū)分分不同的的進(jìn)位制制,常在數(shù)字字的右下下腳標(biāo)明明基數(shù),.如111001(2)表示二進(jìn)進(jìn)制數(shù),34(5)表示5進(jìn)制數(shù).十進(jìn)制數(shù)數(shù)一般不不標(biāo)注基基數(shù).[問題2]十進(jìn)制數(shù)數(shù)3721中的3表示3個千,7表示7個百,2表示2個十,1表示1個一,從而它可可以寫成成下面的的形式:3721=3××103+7×102+2×101+1×100.想一想二二進(jìn)制數(shù)數(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.一般地,若k是一個大大于1的整數(shù),那么以k為基數(shù)的的k進(jìn)制數(shù)可可以表示示為一串串?dāng)?shù)字連連寫在一一起的形形式anan-1…a1a0(k)(0<an<k,0≤an-1,…,a1,a0<k)意思是:(1)第一個數(shù)數(shù)字an不能等于于0;(2)每一個數(shù)數(shù)字an,an-1,…,a1,a0都須小于于k.k進(jìn)制的數(shù)數(shù)也可以以表示成成不同位位上數(shù)字字與基數(shù)數(shù)k的冪的乘乘積之和和的形式式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.注意這是是一個n+1位數(shù).[問題3]二進(jìn)制只用0和1兩個數(shù)字,這正好與電路路的通和斷兩兩種狀態(tài)相對對應(yīng),因此計算機(jī)內(nèi)部都都使用二進(jìn)制制.計算機(jī)在進(jìn)行行數(shù)的運算時時,先把接受到的的數(shù)轉(zhuǎn)化成二二進(jìn)制數(shù)進(jìn)行行運算,再把運算結(jié)果果轉(zhuǎn)化為十進(jìn)進(jìn)制數(shù)輸出.那么二進(jìn)制數(shù)數(shù)與十進(jìn)制數(shù)數(shù)之間是如何何轉(zhuǎn)化的呢?例3:把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù)數(shù).分析:先把二進(jìn)制數(shù)數(shù)寫成不同位位上數(shù)字與2的冪的乘積之之和的形式,再按照十進(jìn)制制數(shù)的運算規(guī)規(guī)則計算出結(jié)結(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ù)數(shù)k的冪的乘積之之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十進(jìn)制制數(shù)的運算規(guī)規(guī)則計算出結(jié)結(jié)果.例4:把89化為二進(jìn)制的的數(shù).分析:把89化為二進(jìn)制的的數(shù),需想辦法將89先寫成如下形形式89=an×2n+an-1×2n-1+…+a1×21+a0×20.89=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