【學案導學設計】學年高中數學 1.3 算法案例課堂教學課件1 新人教A必修3

第一章算法初步

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