§1.3算法案例

1、1. 3 算法案例 一、教學(xué)目標(biāo) 1知識與技能 （1）理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析； （ 2）了解秦九韶算法的計算過程，并理解利用秦九韶算法可以減少計算次數(shù)提高計算效 率的實質(zhì)； （ 3）了解各種進(jìn)位制與十進(jìn)制之間轉(zhuǎn)換的規(guī)律，會利用各種進(jìn)位制與十進(jìn)制之間的聯(lián)系 進(jìn)行各種進(jìn)位制之間的轉(zhuǎn)換； （4）基本能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序框圖并寫出算法程序 2過程與方法 在輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的學(xué)習(xí)過程中對比我們常見的約分求公因 式的方法，比較它們在算法上的區(qū)別，并從程序的學(xué)習(xí)中體會數(shù)學(xué)的嚴(yán)謹(jǐn)，領(lǐng)會數(shù)學(xué)算法 計算機處理的結(jié)合方式，初

2、步掌握把數(shù)學(xué)算法轉(zhuǎn)化成計算機語言的一般步驟 3情感態(tài)度與價值觀 通過閱讀中國古代數(shù)學(xué)中的算法案例，了解中國古代數(shù)學(xué)家對數(shù)學(xué)的貢獻(xiàn)，充分認(rèn)識 到我國文化歷史的悠久； 領(lǐng)悟十進(jìn)制， 二進(jìn)制的特點， 進(jìn)一步認(rèn)識到計算機與數(shù)學(xué)的聯(lián)系 二、教學(xué)重點與難點 1教學(xué)重點：以3 個典型的算法案例為載體，使學(xué)生通過模仿、操作、探索經(jīng)歷算法設(shè) 計的全過程，幫助學(xué)生進(jìn)一步體會算法的基本思想，感受算法在解決實際問題中的重要作 用 2教學(xué)難點：提煉出算法中的循環(huán)結(jié)構(gòu)，并用程序框圖和算法語句表示出來 三、教學(xué)過程 新課講解 案例 1 輾轉(zhuǎn)相除法與更相減損術(shù) 引入：在小學(xué)，我們學(xué)過求兩個正整數(shù)的最大公約數(shù)的方法，你能求出

3、18 與 30 的最大公 約數(shù)嗎？ 分析：已學(xué)方法是先利用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除， 一直除到所得的商是互質(zhì)數(shù)為止， 然后把所有的除數(shù)連乘起來； 如果公有的質(zhì)因數(shù)比較大， 如求 8251與 6105的最大公約數(shù)？ 上述方法就比較困難， 我們又應(yīng)該怎樣求它們的最大公約數(shù)？這就是我們這一堂課所要探 討的內(nèi)容 1輾轉(zhuǎn)相除法 引例：求兩個正數(shù) 8251 和 6105 的最大公約數(shù) 分析： 8251 與 6105 兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，根 據(jù)已有的知識即可求出最大公約數(shù)） 解：8251 = 6105X 1 + 2146 顯然8251與6105的公約數(shù)也必是 6105

4、X 1 + 2146的約數(shù)，故也就是 2146的約數(shù)， 同樣 8251、6105 與 2146 的公約數(shù)一樣， 所以 8251 與 6105的最大公約數(shù)也是 6105 與 2146 的最大公約數(shù)（數(shù)字變小） 6105= 2146 X 2+ 1813 2146= 1813 X 1 + 333 1813=333X5148 333= 148X 2+ 37 148= 37X 4+ 0 則 37 為 8251 與 6105 的最大公約數(shù) 以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法，也叫歐幾里德算法，它是由歐幾里德 在公元前 300 年左右首先提出的，它可以求任意兩個正整數(shù)的最大公約數(shù) 思考：能否把輾轉(zhuǎn)相除

5、法編成一個計算機程序？ 算法分析： 用較大的數(shù) m 除以較小的數(shù) n ，得到除式 錯誤！未找到引用源。錯誤！未找到 引用源。 ，直到 錯誤！未找到引用源。 最后的除數(shù) n 就是所需的最大公約數(shù) 程序設(shè)計： 直到型循環(huán)程序： INPUT m， n DO r=m MOD n INPUT m r=m MOD n 當(dāng)型循環(huán)程序： ，n 4 m=n WHILE r0 r=m MOD n m與n的最大公約數(shù)：”；n n=r m=n LOOP UNTIL r=0 n=r PRINT “ m與n的最大公約數(shù)：”；m END WEND PRINT END 2更相減損術(shù) 我國古代著名的數(shù)學(xué)專著九章算術(shù)方田章中的更

6、相減損術(shù)也可以用來解決求最大 公約數(shù)問題 更相減損術(shù)：可半者半之，不可半者，副置分母子之?dāng)?shù)，以少減多，更相減損，求 其等也，以等數(shù)約之 翻譯出來為： 第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)若是，用2 約簡；若不是，執(zhí) 行第二步 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小 數(shù)繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù) 例 1用更相減損術(shù)求 98 與 63 的最大公約數(shù) 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98 - 63 = 35 63- 35= 28 , 35- 28 = 7, 28- 7= 21,

7、 21- 7= 14 , 14-7 = 7 所以， 98 與 63 的最大公約數(shù)是 7 算法分析： 比較兩個數(shù)的大小, 較大的數(shù)減去較小的數(shù), 接著把所得的差與較小的數(shù)比較, 并以大數(shù)減小數(shù)繼續(xù)這個操作,直到所得的數(shù)相等為止,則這個數(shù)（等數(shù)）就是所求的 最大公約數(shù) 當(dāng)型循環(huán)程序： INPUT m,n r=m-n WHILE nr IF nr THEN t=n n=r r=t END IF m=n n=r r=m-n WEND PRINT “ m與n的最大公約數(shù)：”；n END 比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 (1) 都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，

8、計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū) 別較明顯； (2) 從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損 術(shù)則以減數(shù)與差相等而得到. 配套練習(xí)：書 P45練習(xí)1 (讓三個學(xué)生上來各用兩種方法完成) 案例2秦九韶算法 引入：怎樣計算多項式f (x) = x5 x4 x3 x2 x 1當(dāng)x = 5時的值，并統(tǒng)計所做的 計算的種類及計算次數(shù). 分析：常規(guī)解法直接代入計算，共需要10次乘法運算，5次加法運算.有沒有更為簡單的 方法？ 我們把多項式變形為：f (x) =x2(1 x(1 x(1 x) x 1再統(tǒng)計一下計算當(dāng) x = 5

9、時的值時需要的計算次數(shù)，可以得出僅需4次乘法和5次加法運算即可得出結(jié)果。顯然少 了 6次乘法運算. 類似的： f (x) anxn an4xnJ anxn玄 = (anXn，an4xn anQXn； |l( ajx a。 = (anXn，anxn”a2)x ajx a。=HIIH (anX an)x anQ)xaj a。 求多項式的值，首先計算最內(nèi)層括號內(nèi)一次多項式的值，即v anx an/，然后由 內(nèi)向外逐層計算， 即v2 =wx an/, ,vvnJx a0，這樣，求n次多項式f (x)的 值就轉(zhuǎn)化為求n個一次多項式的值.一一秦九韶算法 算法分析、程序框圖、程序：(見書P38) 思考：在利

10、用秦九韶算法計算 n次多項式當(dāng)x=x0時需要多少次乘法計算和多少次加法計 算？至多n次乘法和n次加法 練習(xí)：書P45練習(xí)2 (統(tǒng)計需要多少次乘法計算和多少次加法計算？) 案例3進(jìn)位制 引入：我們常見的數(shù)字都是十進(jìn)制的，但是并不是生活中的每一種數(shù)字都是十進(jìn)制的.比 如時間和角度用六十進(jìn)位制，計算機用的是二進(jìn)制，那么什么是進(jìn)位制？不同的進(jìn)位制之 間又又什么聯(lián)系呢？ 進(jìn)位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的記數(shù)系統(tǒng)，約定滿二進(jìn)一就是二進(jìn)制；滿 十進(jìn)一就是十進(jìn)制；滿十二進(jìn)一就是十二進(jìn)制；滿六十進(jìn)一就是六十進(jìn)制；也就是滿幾進(jìn) 一就是幾進(jìn)制，幾就是基數(shù). 女口：十進(jìn)制中 3721 =3 1037 1022

11、1011 10 類似的，其他進(jìn)位制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)的幕的乘積之和的形式， 如: 110011(2)-1251 24 023022121120 7342)=7 83 3 82 4 81 2 80 例3 把二進(jìn)制110011(2)化為十進(jìn)制. 分析：先把二進(jìn)制數(shù)寫成不同位上數(shù)字與基數(shù)的幕的乘積之和的形式，再按照十進(jìn)制數(shù)的 運算規(guī)則計算出結(jié)果. 解：110011(2)=1251240 230 221 211 20 =1321161 21 1 = 51 說明：其他進(jìn)制數(shù)都可用這種方法轉(zhuǎn)化為十進(jìn)制數(shù). 例4 設(shè)計一個算法，把 k進(jìn)制數(shù)a轉(zhuǎn)化為十進(jìn)制數(shù)b 算法分析、程序框圖、算法：(見書

12、P41-42) “t=a MOD 10 ” 89或所得商，然后去余數(shù). 2|89_ 分析：如何實現(xiàn)取出 k進(jìn)制數(shù)各位上的數(shù)字？“ a=a10” 例5 .把89化為二進(jìn)制數(shù). 解：根據(jù)二進(jìn)制數(shù)滿二進(jìn)一的原則，、，可以用2連續(xù)去除 具體的計算方法如下： / 89=2*44+1 2441 44=2*22+0 22=2*11+0 11=2*5+1 5=2*2+1 .89=2*(2*(2*(2*(2*2+1)+1)+0)+0)+1 =1*2 6+0*25+1*2 4+1*2 3+0*2 2+0*21+1*20=1011001 這種算法叫做除2取余法，還可以用右邊的除法算式表示 把上式中的各步所得的余數(shù)從下到上排列即可得到89=1011001 (2) 上述方法也可以推廣為把十進(jìn)制化為k進(jìn)制數(shù)的算法，稱為 除k取余法. 例6 設(shè)計一個程序，實現(xiàn)“除k取余法”. 算法分析、程序框圖、程序：(見書P43) 拓展：非十進(jìn)