小課題 算法案例

1、小課題： 算法案例海南僑中田林未 (一)輾轉(zhuǎn)相除法與更相減損術(shù)1.短除法 求兩個正整數(shù)的最大公約數(shù)的步驟:先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除,一直除到所有的商是兩個互質(zhì)的數(shù)為止,然后把所有的處暑連乘起來.2.窮舉法(也叫枚舉法) 窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟:從兩個較小的數(shù)開始由大到小列舉,直到找到公約數(shù)立即中斷列舉,得到的公約數(shù)便是最大公約數(shù).3.輾轉(zhuǎn)相除法 (1)輾轉(zhuǎn)相除法:該算法又稱歐幾里得算法,就是對于給定的兩個正整數(shù),用較大的數(shù)除以較小的數(shù),若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成一對新數(shù),繼續(xù)上面的除法,直到余數(shù)為零,此時處暑就是所求兩正整數(shù)的最大公約數(shù). (2)算法步驟:以求

2、正整數(shù)的最大公約數(shù)為例. 第一步,輸入兩個正整數(shù). 第二步,判斷的大小,讓表示較大的數(shù),表示較小的數(shù). 第三步,計算除以的余數(shù). 第四步,讓. 第五步,如果,則的最大公約數(shù)等于;否則返回第三步. (3)程序框圖為:略 (4)程序1為: INPUT “m,n=”;m,n IF m<n THEN t=m m=n n=t END IF DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 程序2為:INPUT “m,n=”;m,n IF m<n THEN t=m m=n n=t END IF r=1 WHILE r<>0 r=m MO

3、D n m=n n=r WEND PRINT m END4.更項減損術(shù) (1)更項減損術(shù):我國早期也有解決求最大公約數(shù)問題的算法,就是更相減損術(shù).九章算術(shù)是中國古代的數(shù)學(xué)專著,其中的“更相減損術(shù)”也可以來用來求兩個數(shù)的最大公約數(shù),即“可半者半之,不可半者,副置分母、子子之?dāng)?shù),以少減多,更相減損,求其等也.以等數(shù)約之.” (2)算法步驟: 第一步,任意給定兩個正整數(shù),判斷它們是否都是偶數(shù),若是,用約簡之;若不是,執(zhí)行第二步. 第二步,以較大的數(shù)減去較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減去小數(shù),繼續(xù)這個操作,直到所得的數(shù)相等為止.則這個數(shù)(等數(shù))或這個數(shù)與約簡數(shù)的乘積就是所求的最大公約

4、數(shù). (3)程序框圖為:略 (4)程序為: INPUT “m,n=”;m,n IF m<n THEN t=m m=n n=t END IF k=0 WHILE (m MOD 2=0) AND (n MOD 2=0) m=m/2 n=n/2 k=k+1 WEND d=m-n WHILE d<>n IF d>n THEN m=d ELSE m=n n=d END IF d=m-n WEND d=2k*d PRINT d END (二)秦九韶算法1.怎么求多項式當(dāng)時的值? 一個自然的做法是把代入多項式,急速各項的值,然后把它們加起來,這時,我們一共做了次乘法運算,次加法運算.

5、 另一種算法是先計算的值,然后計算的值,這樣每次都可以利用上一次計算的結(jié)構(gòu),這時,我們一共做了次乘法運算,次加法運算. 第二種做法與第一種做法相比,乘法的運算此時減少了,因而能夠提高運算效率,對于計算機來說,做一次乘法運算所用的時間比做一次加法運算要長得多,所以采用第二種算法,計算機能更快地得到結(jié)果.2.求多項式的值時,常用秦九韶算法,這種算法的運算次數(shù)較少,是多項式求值比較先進的算法,其實質(zhì)是轉(zhuǎn)化為求個一次多項式的值,共進行次乘法運算和次加法運算.3.秦九韶算法 (1)改寫多項式: 設(shè),.(2)算法步驟: 第一步,輸入多項式次數(shù),最高次項的系數(shù)和的值. 第二步,. 第三步,輸入次項的系數(shù).

6、第四步,. 第五步,判斷是否大于等于,若是,則返回第三步;否則,輸出多項式的值.(3)程序框圖為:略(4)程序為: INPUT “n=”;n INPUT “an=”;a INPUT “x=”;x v=a i=n-1 WHILE i>=0 PRINT “i=”;i INPUT “ai=”;a v=v*x+a i=i-1 WEND PRINT v END(三)進位制算法1.定義:人們?yōu)榱擞嫈?shù)和運算方面而約定的計數(shù)系統(tǒng),“滿進一”就是進制,是基數(shù)(其中是大于的整數(shù)).進制的數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式.2.在日常生活中,我們最熟悉、最常用的是十進制.除此之外還有二進制,七進制,八進制,

7、十二進制,十六進制,六十進制等.3.非十進制的進制數(shù)(共有位)化為十進制數(shù)的計算公式為: (1)算法步驟: 第一步,輸入的值. 第二步,. 第三步,. 第四步,判斷是否成立,若是,則執(zhí)行第五步;否則,返回第三步. 第五步,輸出的值. (2)程序框圖為:略 (3)程序為: INPUT “a,k,n=”;a,k,n b=0 i=1 t=a MOD 10 DO b=b+t*k(i-1) a=a10 t= a MOD 10i=i+1 LOOP UNTIL i>n PRINT b END4.十進制數(shù)轉(zhuǎn)化為非十進制的進制數(shù)的方法 (1)算法步驟: 第一步,輸入的值. 第二步,求出除以所得的商,余數(shù).

8、 第三步,若,則,返回第二步;否則執(zhí)行第四步. 第四步,將依次得到的余數(shù)從右到左排列,得到進制數(shù). (2)程序框圖為:略 (3)程序為: INPUT “a,k=”;a,n b=0 i=0 DO q=ak r=a MOD k b=b+r*10ii=i+1 LOOP UNTIL q=0 PRINT b END(四)實數(shù)排序算法1.直接插入排序法 從第一個數(shù)開始,依次把每個數(shù)插入到前面已排好序的序列的適當(dāng)位置,具體操作時,把要插入的數(shù)與有序序列的最后一個數(shù)比較,如果該數(shù)大于序列中的最后一個數(shù),則直接將該數(shù)作為前面序列的最后一個數(shù),否則繼續(xù)與前面的數(shù)相比較,直到找到合適的位置為止. 程序為: INPU

9、T “n=”;n DIM a(n) INPUT a a(1)=a i=2 WHILE i<=n Input a flag=0 j=1 DO IF a(j)<a THEN flag= 1 k=j END IF j=j+1 LOOP UNTIL flag=1 OR j>=i IF flag=0 THEN a(i)=a ELSE t=i DO a(t)=a(t-1) t=t-1 LOOP UNTIL t=k a(k)=a END IF i=i+1 WEND i=1 WHILE i<=n PRINT a(i) i=i+1 WEND END2.冒泡排序法 這種方法的基本思路是:將

10、待排序的數(shù)看作是豎著排列的“氣泡”,較小的數(shù)比較輕,要往上浮.在這種方法中,我們要對這個“氣泡”序列進行若干趟處理,每一趟處理都要自上而下兩兩進行比較,按較大數(shù)在下,較小數(shù)在上的原則,如果順序不對,就交換兩個數(shù)的位置.排序完成的已經(jīng)是在某一趟中無交換,即交換次數(shù)為.在排序過程中,小的數(shù)就如氣泡一樣逐層上浮,大的數(shù)逐個下沉,因此被形象地比喻為“冒泡”,古城這種排序算法為冒泡法. 程序1為: INPUT “n=”;n DIM a(n) i=1 WHILE i<=n INPUT a a(i)=a i=i+1 WEND i=1 WHILE i<=n-1 j=1 WHILE j<=n-

11、i IF a(j)<a(j+1) THEN t=a(j) a(j)=a(j+1) a(j+1)=t END IF j=j+1 WEND i=i+1 WEND i=1 WHILE i<=n PRINT a(i) i=i+1 WEND END程序2為: INPUT “n=”;n DIM a(n) i=1 WHILE i<=n INPUT a a(i)=a i=i+1 WEND i=1 DO flag=1j=1 WHILE j<=n-i IF a(j)<a(j+1) THEN t=a(j) a(j)=a(j+1) a(j+1)=t flag=0 END IF j=j+1

12、 WEND i=i+1 LOOP UNTIL flag=1 i=1 WHILE i<=n PRINT a(i) i=i+1 WEND END3.選擇排序法 這種方法是在所有的數(shù)據(jù)中找出最小的元素,并與序列中的第一個數(shù)據(jù)互換,然后在余下的數(shù)據(jù)中再找出最小的數(shù)與第二個數(shù)據(jù)相互換,如此直到最后排序完為止. 該法與冒泡法相比,需要交換的次數(shù)較少,因而效率要比冒泡法高.程序1為: INPUT “n=”;n DIM a(n) i=1 WHILE i<=n INPUT a a(i)=a i=i+1 WEND i=1 WHILE i<=n-1 j=i+1 WHILE j<=n IF a

13、(i)<a(j) THEN t=a(i) a(i)=a(j) a(j)=t END IF j=j+1 WEND i=i+1 WEND i=1 WHILE i<=n PRINT a(i) i=i+1 WEND END程序2為: INPUT “n=”;n DIM a(n) i=1 WHILE i<=n INPUT a a(i)=a i=i+1 WEND i=1 WHILE i<=n-1 k=ij=i+1 WHILE j<=n IF a(k)<a(j) THEN j=j END IF j=j+1 WEND IF i<>k THEN t=a(i) a(i

14、)=a(k) a(k)=t END IF i=i+1 WEND i=1 WHILE i<=n PRINT a(i) i=i+1 WEND END4.快速排序法 在序列中任取一個數(shù)作為基準(zhǔn)(設(shè)為),一次基準(zhǔn)將序列劃分為左右兩個較小的序列區(qū),且坐標(biāo)序列區(qū)中的數(shù)均小于基準(zhǔn),右邊序列區(qū)中的數(shù)均大于基準(zhǔn),然后對兩個序列區(qū)分別再選擇基準(zhǔn)排序,直到所有序列區(qū)中的數(shù)據(jù)元素均已排好序.三、典例剖析(一)輾轉(zhuǎn)相除法與更項減損術(shù)例1 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求與的最大公約數(shù).解: (1)輾轉(zhuǎn)相除法 第一步, 第二步, 第三步, 因此,是與的最大公約數(shù). (2)更相減損術(shù) 第一步, 第二步, 第三步, 因此

15、,是與的最大公約數(shù).點評: 更相減損術(shù)與輾轉(zhuǎn)相除法的比較:盡管兩種算法分別來源于東西方古代數(shù)學(xué)專著,但是二者的算理卻是相似的,右異曲同工之妙.主要區(qū)別在于輾轉(zhuǎn)相除法進行的是出發(fā)運算,即輾轉(zhuǎn)相除;而更相減損術(shù)進行的是減法運算,即輾轉(zhuǎn)相減,但是實質(zhì)都是一個不斷的遞歸過程.例2 請用輾轉(zhuǎn)相除法和更相減損術(shù)求和的最大公約數(shù).解：(1)輾轉(zhuǎn)相除法 第一步, 第二步, 因此,是和的最大公約數(shù). (2)更相減損術(shù) 第一步,因為兩個數(shù)皆為偶數(shù),首先除以得到,在求這兩個數(shù)的最大公約數(shù) 第二步, 第三步, 第四步, 第五步, 第六步, 因此,是和的最大公約數(shù). 例3 用輾轉(zhuǎn)相除法和更相減損術(shù)求三個數(shù)的最大公約數(shù).

16、解：(1)輾轉(zhuǎn)相除法 , 則與的最大公約數(shù)為 又, 則與的最大公約數(shù)為 因此,三個數(shù)的最大公約數(shù)為.(2)更相減損術(shù) , 則與的最大公約數(shù)為 又, 則與的最大公約數(shù)為 因此,三個數(shù)的最大公約數(shù)為.練習(xí): 1.用輾轉(zhuǎn)相除法求和的最大公約數(shù).(答案:) 2.用更相減損術(shù)求和的最大公約數(shù).(答案:) 3.求的最大公約數(shù).(答案:)(二)秦九韶算法例1 已知次多項式,如果在一種算法中,計算的值需要次乘法,計算的值共需要次運算(次乘法次加法),那么計算的值需要_次運算.下面給出一種減少運算次數(shù)的算法:,.利用該算法,計算的值共需要次運算,計算的值共需要_次運算.答案: 點評: 秦九韶算法使用一般的多項式

17、的求值問題.直接法乘法運算的次數(shù)最多可到達,加法最多次.秦九韶算法通過轉(zhuǎn)化把乘法運算的次數(shù)減少到最多次,加法最多次.例2 已知一個次多項式為,用秦九韶算法求這個多項式當(dāng)時的值.解: 根據(jù)秦九韶算法,把多項式改寫成如下形式: 按照從內(nèi)到外的順序,一次計算一次多項式當(dāng)時的值: ,所以,當(dāng)時,多項式的值為點評: 如果多項式函數(shù)中又缺項的畫,要以系數(shù)為的項補齊后再計算.練習(xí): 1.已知多項式函數(shù),求. 2.當(dāng)時,用秦九韶算法求多項式的值. 3.用秦九韶算法求多項式當(dāng)時的值.答案: 1.; 2.; 3.例3 某城市2001年末汽車保有量為萬輛,預(yù)計此后每年報廢上一年末汽車保有量的,并且每年新增汽車萬輛.

18、設(shè)計算法,計算經(jīng)過多少年可使汽車保有量達到萬輛.將此算法用程序語言給出.解：設(shè),經(jīng)過幾年的汽車保有量為,則 上述各式充分說明了秦九韶算法的優(yōu)點:可以通過遞推關(guān)系進行迭代處理.程序為:C=0.94A=30n=0WHILE A<40 A=A*C+3 n=n+1WENDPRINT nEND(三)排序算法例1 (1)冒泡排序法將按從小到大的順序排成一列,需要進行的操作次數(shù)是( ) A. 次 B. 次 C. 次 D. 次 (2)直接排序法將按從小到大的順序排成一列,需要進行操作次數(shù)是( ) A. 次 B. 次 C. 次 D. 次解：(1)B(2)B例2 用直接排序法將按從小到大的順序排列起來: S1: S2: S3: S4: 例3 用直接排序法、冒泡排序法和選擇排序法對數(shù)據(jù)進行排序.解: (1)直接排序法 第一步,將第1,2兩個數(shù)比較,排列成 第二步,將第3個數(shù)插到合適的位置,排列成第三步,將第4個數(shù)插到合適的位置,排列成第四步,將第5個數(shù)插到合適的位置,排列成第五步,將第6個數(shù)插到合適的位置,排列成 (2)冒泡排序法第一步,比較1,2兩個數(shù),前者小于后者,則位置不變: 第二步,比較與,小于,則與互換:第三步,比較與,前者小于后者,則位置不變:第四步,比較與,