第一章算法初步

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

它特點是:把求一個n次多項式值轉化為求n個一次多項式值,經過這種轉化,把運算次數由至多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） 這是一個在秦九韶算法中重復執行步驟,所以可用循環結構來實現.17/31第一步,輸入多項式次數n、最高次項系數an和x值第二步,將v值初始化為an，將i值初始化為n-1第三步,輸入i次項系數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結束是19/31

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

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

十六進制可使用數字或符號有0~9等10個數字以及A~F等6個字母(要求字母A~F對應10~15),十六進制基數是16. 注意:為了區分不一樣進位制,常在數字右下腳標明基數,.如111001(2)表示二進制數,34(5)表示5進制數.十進制數普通不標注基數.21/31[問題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.22/31 普通地,若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位數.23/31

[問題3]二進制只用0和1兩個數字,這恰好與電路通和斷兩種狀態相對應,所以計算機內部都使用二進制.計算機在進行數運算時,先把接收到數轉化成二進制數進行運算,再把運算結果轉化為十進制數輸出.

那么二進制數與十進制數之間是怎樣轉化呢?24/31例3:把二進制數110011(2)化為十進制數. 分析:先把二進制數寫成不一樣位上數字與2冪乘積之和形式,再按照十進制數運算規則計算出結果.解: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進制數轉化為十進制數方法 先把k進制數表示成不一樣位上數字與基數k冪乘積之和形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十進制數運算規則計算出結果.26/31例4:把89化為二進制數. 分析:把89化為二進制數,需想方法將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)×