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

第一章算法初步

1.3算法案例35915[問(wèn)題1]：在小學(xué)，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，你能求出18與30的最大公約數(shù)嗎？〖創(chuàng)設(shè)情景，揭示課題〗183023∴18和30的最大公約數(shù)是2×3=6.先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除,一直除到所得的商是互質(zhì)數(shù)為止,然后把所有的除數(shù)連乘起來(lái).案例1輾轉(zhuǎn)相除法與更相減損術(shù)〖創(chuàng)設(shè)情景，揭示課題〗[問(wèn)題2]:我們都是利用找公約數(shù)的方法來(lái)求最大公約數(shù)，如果兩個(gè)數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)?〖研探新知〗1.輾轉(zhuǎn)相除法:例1求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。 分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(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求兩個(gè)正數(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年左右首先提出的。第一步,給定兩個(gè)正數(shù)m,n第二步,計(jì)算m除以n所得到余數(shù)r第三步,m=n,n=r第四步,若r=0,則m,n的最大公約數(shù)等于m;否則返回第二步輾轉(zhuǎn)相除法求最大公約數(shù)算法：思考：需不需要比較m，n的大小不需要否開始輸入兩個(gè)正數(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ù): 我國(guó)早期也有解決求最大公約數(shù)問(wèn)題的算法，就是更相減損術(shù)。 更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。 翻譯出來(lái)為：第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(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＝21;21－7＝14;14－7＝7.所以，98與63的最大公約數(shù)是7。練習(xí)2：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)。(12)輾轉(zhuǎn)相除法法與更相減減損術(shù)的比比較:（1）都是求最最大公約數(shù)數(shù)的方法，，計(jì)算上輾輾轉(zhuǎn)相除法法以除法為為主，更相相減損術(shù)以以減法為主主;計(jì)算次數(shù)上上輾轉(zhuǎn)相除除法計(jì)算次次數(shù)相對(duì)較較少，特別別當(dāng)兩個(gè)數(shù)數(shù)字大小區(qū)區(qū)別較大時(shí)時(shí)計(jì)算次數(shù)數(shù)的區(qū)別較較明顯。（2）從結(jié)果體體現(xiàn)形式來(lái)來(lái)看，輾轉(zhuǎn)轉(zhuǎn)相除法體體現(xiàn)結(jié)果是是以相除余余數(shù)為0則得到，而而更相減損損術(shù)則以減減數(shù)與差相相等而得到到.〖教學(xué)設(shè)計(jì)〗[問(wèn)題1]設(shè)計(jì)求多項(xiàng)項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值的算算法,并寫出程序序.x=5f=2＊x^5-5＊x^4-4＊x^3+3＊x^2-6＊x+7PRINTfEND程序點(diǎn)評(píng):上述算法一一共做了15次乘法運(yùn)算算,5次加法運(yùn)算算.優(yōu)點(diǎn)是簡(jiǎn)單單,易懂;缺點(diǎn)是不通通用,不能解決任任意多項(xiàng)式式求值問(wèn)題題,而且計(jì)算效效率不高.n次多項(xiàng)式至至多n(n+1)/2次乘法運(yùn)算算和n次加法運(yùn)算算案例2秦九韶算法法這析計(jì)算上上述多項(xiàng)式式的值,一共需要9次乘法運(yùn)算算,5次加法運(yùn)算算.[問(wèn)題2]有沒有更高高效的算法法?分析:計(jì)算x的冪時(shí),可以利用前前面的計(jì)算算結(jié)果,以減少計(jì)算算量,即先計(jì)算x2,然后依次計(jì)計(jì)算的值.第二種做法與與第一種做法法相比,乘法的運(yùn)算次次數(shù)減少了,因而能提高運(yùn)運(yùn)算效率.而且對(duì)于計(jì)算算機(jī)來(lái)說(shuō),做一次乘法所所需的運(yùn)算時(shí)時(shí)間比做一次次加法要長(zhǎng)得得多,因此第二種做做法能更快地地得到結(jié)果.[問(wèn)題3]能否探索更好好的算法,來(lái)解決任意多多項(xiàng)式的求值值問(wèn)題?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時(shí),多項(xiàng)式的值是是2677.這種求多項(xiàng)式式值的方法就就叫秦九韶算法.變?yōu)榍髱讉€(gè)一一次式的值幾個(gè)乘法幾個(gè)加法？秦九韶《數(shù)書九章》.2-50-43-60x=5105252512512160560830403034所以,當(dāng)x=5時(shí),多項(xiàng)式的值是是15170.練習(xí):用秦九韶算法法求多項(xiàng)式f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時(shí)的值.解:原多項(xiàng)式先化化為:f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0列表21517015170注意:n次多項(xiàng)式有n+1項(xiàng),因此缺少哪一一項(xiàng)應(yīng)將其系系數(shù)補(bǔ)0.f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.我們可以改寫寫成如下形式式:f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.求多項(xiàng)式的值值時(shí),首先計(jì)算最內(nèi)內(nèi)層括號(hào)內(nèi)一一次多項(xiàng)式的的值,即v1=anx+an-1,然后由內(nèi)向外外逐層計(jì)算一一次多項(xiàng)式的的值,即一般地,對(duì)于一個(gè)n次多項(xiàng)式v2=v1x+an-2,v3=v2x+an-3,……,vn=vn-1x+a0.這樣,求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為為求n個(gè)一次多項(xiàng)式式的值.這種算法稱為為秦九韶算法.點(diǎn)評(píng):秦九韶算法是是求一元多項(xiàng)項(xiàng)式的值的一一種方法.它的特點(diǎn)是:把求一個(gè)n次多項(xiàng)式的值值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式式的值,通過(guò)這種轉(zhuǎn)化化,把運(yùn)算的次數(shù)數(shù)由至多n(n+1)/2次乘法運(yùn)算和和n次加法運(yùn)算,減少為n次乘法運(yùn)算和和n次加法法運(yùn)算算,大大提提高了了運(yùn)算算效率率.v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3,…………,vn=vn-1x+a0.觀察上上述秦秦九韶韶算法法中的的n個(gè)一次次式,可見vk的計(jì)算算要用用到vk-1的值.若令v0=an,得v0=an,vK=vK-1x+an-k(k=1,2,……,n）這是一一個(gè)在在秦九九韶算算法中中反復(fù)復(fù)執(zhí)行行的步步驟,因此可可用循循環(huán)結(jié)結(jié)構(gòu)來(lái)來(lái)實(shí)現(xiàn)現(xiàn).第一步步,輸入多多項(xiàng)式式次數(shù)數(shù)n、最高高次項(xiàng)項(xiàng)的系系數(shù)an和x的值第二步步,將v的值初初始化化為an，將i的值初初始化化為n-1第三步步,輸入i次項(xiàng)的的系數(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é)束是[問(wèn)題1]我們常常見的的數(shù)字字都是是十進(jìn)進(jìn)制的的,但是并并不是是生活活中的的每一一種數(shù)數(shù)字都都是十十進(jìn)制制的.比如時(shí)時(shí)間和和角度度的單單位用用六十十進(jìn)位位制,電子計(jì)計(jì)算機(jī)機(jī)用的的是二二進(jìn)制制.那么什什么是是進(jìn)位位制?不同的的進(jìn)位位制之之間又又有什什么聯(lián)聯(lián)系呢呢?進(jìn)位位制制是是人人們們?yōu)闉榱肆擞?jì)計(jì)數(shù)數(shù)和和運(yùn)運(yùn)算算的的方方便便而而約約定定的的一一種種記記數(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ù)字字符符號(hào)號(hào)的的個(gè)個(gè)數(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等十十個(gè)個(gè)數(shù)數(shù)字字,基數(shù)數(shù)是是10;十六六進(jìn)進(jìn)制制可可使使用用的的數(shù)數(shù)字字或或符符號(hào)號(hào)有有0~9等10個(gè)數(shù)數(shù)字字以以及及A~F等6個(gè)字字母母(規(guī)定定字字母母A~F對(duì)應(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ù).[問(wèn)題2]十進(jìn)制數(shù)數(shù)3721中的3表示3個(gè)千,7表示7個(gè)百,2表示2個(gè)十,1表示1個(gè)一,從而它可可以寫成成下面的的形式: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是一個(gè)大大于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)第一個(gè)數(shù)數(shù)字an不能等于于0;(2)每一個(gè)數(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.注意這是是一個(gè)n+1位數(shù).[問(wèn)題3]二進(jìn)制只用0和1兩個(gè)數(shù)字,這正好與電路路的通和斷兩兩種狀態(tài)相對(duì)對(duì)應(yīng),因此計(jì)算機(jī)內(nèi)部都都使用二進(jìn)制制.計(jì)算機(jī)在進(jìn)行行數(shù)的運(yùn)算時(shí)時(shí),先把接受到的的數(shù)轉(zhuǎn)化成二二進(jìn)制數(shù)進(jìn)行行運(yùn)算,再把運(yù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ù)的運(yùn)算規(guī)規(guī)則計(jì)算出結(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ù)的運(yùn)算規(guī)規(guī)則計(jì)算出結(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