高三數(shù)學(xué)教案：算法案例

1、普通高中 程 準 教科 數(shù)學(xué)人教版 高三新 數(shù)學(xué)第一輪復(fù)習(xí)教案（講座17）算法案例一課標要求：通 中國古代數(shù)學(xué)中的算法案例，體會中國古代數(shù)學(xué) 世界數(shù)學(xué) 展的 獻。二命題走向算法是高中數(shù)學(xué)新 程中的新增內(nèi)容，本 的重點是幾種重要的算法案例思想，復(fù) 重算法的思想 算法和程序的構(gòu)造。預(yù)測 2007 年高考 本 的考察是： 以 或填空 的形式出 ， 分 在 5 分左右，考察的 點是算法 例和 數(shù)學(xué)知 的 合 目。三要點精講1求最大公 數(shù)（ 1）短除法求兩個正整數(shù)的最大公 數(shù)的步 ：先用兩個數(shù)公有的 因數(shù) 去除，一直除到所得的商是兩個互 數(shù) 止，然后把所有的除數(shù) 乘起來。（ 2） 法（也叫枚 法） 法求

2、兩個正整數(shù)的最大公 數(shù)的解 步 ：從兩個數(shù)中 小數(shù)開始由大到小列 ，直到找到公 數(shù)立即中斷列 ，得到的公 數(shù)便是最大公 數(shù)。（ 3） 相除法 相除法求兩個數(shù)的最大公 數(shù)，其算法可以描述如下： 入兩個正整數(shù) m 和 n； 求余數(shù) r： 算 m 除以 n，將所得余數(shù)存放到 量r 中；更新被除數(shù)和余數(shù)：m=n ，n=r；判斷余數(shù)r 是否 0。若余數(shù) 0， 出 果；否 向第步 循 行。如此循 ，直到得到 果 止。（ 4）更相減 我國早期也有解決求最大公 數(shù) 的算法，就是更相減 。在九章算 中 了更相減 求最大公 數(shù)的步 ：可半者半之，不可半者，副置分母 ?子之數(shù)，以少減多，更相減 ，求其等也，以等數(shù)

3、之。步 ：任意 出兩個正數(shù)；判斷它 是否都是偶數(shù)。若是，用 2 ；若不是， 行第二步。以 大的數(shù)減去 小的數(shù)，接著把 小的數(shù)與所得的差比 ，并以大數(shù)減小數(shù)。 操作，直到所得的數(shù)相等 止， 個數(shù)（等數(shù)）就是所求的最大公 數(shù)。2秦九韶算法秦九韶算法的一般 ：秦九韶算法適用一般的多 式f(x)=a nnn-1 n-110的求 。用秦九韶算x +ax+ .+a x+a法求一般多 式f(x)= ann n-1xn-1100 的函數(shù) ，可把n 次多 式的求x +a+ .+a x+a當 x=x 化成求n 個一次多 式的 的 ，即求第 1頁共 10頁v0=anv1=anx+an 1v2=v 1x+an 2v3

4、=v 2x+an 3 .vn=v n 1x+a0 察秦九韶算法的數(shù)學(xué)模型， 算vk 要用到 vk 1 的 ，若令v0=an。我 可以得到下面的 推公式：v0=anvk=v k 1+ank (k=1,2, n) 是一個在秦九韶算法中反復(fù) 行的步 ，可以用循 構(gòu)來 。3. 排序排序的算法很多， 本主要介 里兩種排序方法：直接插入排序和冒泡排序（ 1）直接插入排序在日常生活中， 常碰到 一 排序 ：把新的數(shù)據(jù)插入到已 排好 序的數(shù)據(jù)列中。例如：一 從小到大排好 序的數(shù)據(jù)列 1 ， 3，5， 7，9， 11， 13 ，通常稱之 有序列，我 用序號 1，2，3，表示數(shù)據(jù)的位置， 欲把一個新的數(shù)據(jù) 8 插

5、入到上述序列中。完成 個工作要考 兩個 ：（ 1）確定數(shù)據(jù)“ 8”在原有序列中 占有的位置序號。數(shù)據(jù)“8”所 的位置 足小于或等于原有序列右 所有的數(shù)據(jù)，大于其左 位置上所有的數(shù)據(jù)。（ 2）將 個位置空出來，將數(shù)據(jù)“8”插 去。 于一列無序的數(shù)據(jù)列，例如：49 ， 38， 65， 97， 76， 13， 27， 49 ，如何使用 種方法 行排序呢？基本思想很 ，即反復(fù)使用上述方法排序，由序列的 度不斷增加，一直到完成整個無序列就有序了。首先， 49 是有序列，我 將38 插入到有序列 49 中，得到兩個數(shù)據(jù)的有序列：38 ，49 ，然后，將第三個數(shù)據(jù)65 插入到上述序列中，得到有序列：38 ，

6、 49， 65按照 種方法，直到將最后一個數(shù)據(jù)65 插入到上述有序列中，得到13 ， 27， 38， 49， 49， 65， 76， 97 ，就完成了整個數(shù)據(jù)列的排序工作。注意到無序列“插入排序算法”成 了解決 的平臺。（ 2）冒泡法排序所 冒泡法排序，形象地 ，就是將一 數(shù)據(jù)按照從小到大的 序排列 ，小的數(shù)據(jù) 量 的， 大的數(shù)據(jù) 量沉的。 一個小的數(shù)據(jù)就好比水中的氣泡， 往上移 ，一個 大的數(shù)據(jù)就好比石 ，往下移 。 然最 會沉到水底，最 的會浮到 ，反復(fù) 行，直到數(shù)據(jù)列排成 有序列。以上 程反映了 種排序方法的基本思路。第 2頁共 10頁我們先對一組數(shù)據(jù)進行分析。設(shè)待排序的數(shù)據(jù)為：49 ，

7、 38， 65， 97， 76， 13， 27， 49排序的具體操作步驟如下：1將第 1 個數(shù)與右邊相鄰的數(shù) 38 進行比較， 因為 3849 ，所以順序不變，得到新的數(shù)據(jù)列：38 ， 49， 65， 97， 76， 13， 27， 493將新數(shù)據(jù)列中的第3 個數(shù) 65 與右邊相鄰的數(shù)97 進行比較，因為9765 ，所以順序不變，得到新的數(shù)據(jù)列：38 ， 49， 65， 97， 76， 13， 27， 494將新數(shù)據(jù)列中的第4 個數(shù) 97 與右邊相鄰的數(shù)76 進行比較，因為7697，97 應(yīng)下沉，所以順序不變，得到新的數(shù)據(jù)列：38 ， 49， 65， 76， 97， 13， 27， 495將新

8、數(shù)據(jù)列中的第5 個數(shù) 97 與右邊相鄰的數(shù)13 進行比較，因為1397，97 應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列：38 ， 49， 65， 76， 13，97， 27， 496將新數(shù)據(jù)列中的第6 個數(shù) 97 與右邊相鄰的數(shù)27 進行比較，因為2797，97 應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列：38 ， 49， 65， 76， 13，97， 27， 497將新數(shù)據(jù)列中的第7 個數(shù) 97 與右邊相鄰的數(shù)49 進行比較，因為4997，97 應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列：38 ， 49，65， 76， 13， 97， 49， 27我們把上述過程稱為一趟排序。其基本特征是最大的數(shù)據(jù)沉到底，即

9、排在最左邊位置上的數(shù)據(jù)是數(shù)組中最大的數(shù)據(jù)。反復(fù)執(zhí)行上面的步驟，就能完成排序工作，排序過程不會超過 7 趟。這種排序的方法稱為冒泡排序。上面的分析具有一般性，如果數(shù)據(jù)列有 n 個數(shù)據(jù)組成，至多經(jīng)過 n 1 趟排序，就能完成整個排序過程。4進位制（ 1）概念進位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)， 基數(shù)為 n，即可稱 n 進位制，簡稱 n 進制。現(xiàn)在最常用的是十進制，通常使用 10 個阿拉伯數(shù)字 09 進行記數(shù)。對于任何一個數(shù)，我們可以用不同的進位制來表示。比如：十進數(shù)57，可以用二進制表示為111001，也可以用八進制表示為71、用十六進制表示

10、為39，它們所代表的數(shù)值都是一樣的。一般地，若k 是一個大于一的整數(shù)，那么以k 為基數(shù)的k 進制可以表示為：anan 1.a1a0( k )(0ank,0an 1 ,., a1 , a0k) ，而表示各種進位制數(shù)一般在數(shù)字右下腳加注來表示, 如 111001(2) 表示二進制數(shù),34 (5)表示 5 進制數(shù)。第 3頁共 10頁（ 2）進位制間的轉(zhuǎn)換關(guān)于進位制的轉(zhuǎn)換，教科書上以十進制和二進制之間的轉(zhuǎn)換為例講解，并推廣到十進制和其它進制之間的轉(zhuǎn)換。這樣做的原因是，計算機是以二進制的形式進行存儲和計算數(shù)據(jù)的，而一般我們傳輸給計算機的數(shù)據(jù)是十進制數(shù)據(jù)，因此計算機必須先將十進制數(shù)轉(zhuǎn)換為二進制數(shù)，再處理，

11、顯然運算后首次得到的結(jié)果為二進制數(shù)，同時計算機又把運算結(jié)果由二進制數(shù)轉(zhuǎn)換成十進制數(shù)輸出。非十進制數(shù)轉(zhuǎn)換為十進制數(shù)比較簡單，只要計算下面的式子值即可：anan 1 .a1a0 ( k)an k nan 1k n 1.a1 k a0第一步：從左到右依次取出k 進制數(shù).a1a0(k)各位上的數(shù)字，乘以相應(yīng)的k 的anan 1冪 ， k 的 冪 從 n開 始 取 值 ， 每 次 遞 減 1 ， 遞 減 到 0 ， 即an k n , an 1 k n 1 ,. , a1 k, a0 k 0 ；第二步：把所得到的乘積加起來，所得的結(jié)果就是相應(yīng)的十進制數(shù)。十進制數(shù)轉(zhuǎn)換成非十進制數(shù)把十進制數(shù)轉(zhuǎn)換為二進制數(shù)，

12、教科書上提供了“除2 取余法”，我們可以類比得到十進制數(shù)轉(zhuǎn)換成 k 進制數(shù)的算法“除k 取余法”。非十進制之間的轉(zhuǎn)換一個自然的想法是利用十進制作為橋梁。教科書上提供了一個二進制數(shù)據(jù)與16 進制數(shù)據(jù)之間的互化的方法，也就是先有二進制數(shù)轉(zhuǎn)化為十進制數(shù)，再由十進制數(shù)轉(zhuǎn)化成為16 進制數(shù)。四典例解析題型 1：求最大公約數(shù)例 1（ 1）用輾轉(zhuǎn)相除法求123 和 48 的最大公約數(shù)？（ 2）用更相減損來求80 和 36 的最大公約數(shù)？解析：（ 1）輾轉(zhuǎn)相除法求最大公約數(shù)的過程如下：（建立帶余除式）123248 2748127 2127121 62136 3623+0最后 6 能被 3 整除，得123 和

13、48 的最大公約數(shù)為3。（ 2）分析：我們將 80 作為大數(shù)， 36 作為小數(shù)，執(zhí)行更相減損術(shù)來求兩數(shù)的最大公約數(shù)。執(zhí)行結(jié)束的準則是減數(shù)和差相等。更相減損術(shù)：因為 80 和 36 都是偶數(shù)，要去公因數(shù)2。80 2=40， 362=18；40 和 18 都是偶數(shù)，要去公因數(shù)2。第 4頁共 10頁40 2=20， 182=9下面來求20 與 9 的最大公 數(shù)，20 9=1111 9=29 2=77 2=55 2=33 2=12 1=1可得 80 和 36 的最大公 數(shù) 22 1=4。點 ： 比兩種方法控制好算法的 束， 相除法是到達余數(shù) 0，更相減 是到達減數(shù)和差相等。例 2 一個算法，求出 84

14、0 與 1764 的最大公因數(shù)。解析：我 已 學(xué) 了 自然數(shù)的素因數(shù)分解的方法，下面的算法就是在此基 上 的。解 思路如下：首先 兩個數(shù) 行素因數(shù)分解：840=23 3 5 7， 1764=22 32 72，其次，確定兩個數(shù)的公共素因數(shù)：2， 3， 7。接著確定公共素因數(shù)的指數(shù)： 于公共素因數(shù)2， 840 中 23， 1764 中 22， 取 少的一個 22，同理可得下面的因數(shù) 3 和 7。算法步 ：第一步：將840 行素數(shù)分解23 35 7；第二步：將1764 行素數(shù)分解22 32 72 ；第三步：確定它 的公共素因數(shù)：2， 3， 7；第四步：確定公共素因數(shù) 2， 3，7 的指數(shù)分 是： 2

15、， 1， 1；第五步：最大公因數(shù) 2231 71=84 。點 ： 數(shù)是除以外只能被和本身整除的正整數(shù)，它 是無限多個，但是目前沒有一個 律來確定所有的 數(shù)。 型 2：秦九韶算法例 3（ 2005 北京， 14）已知 n 次多 式 pn (x)a0 xna1 xn 1 lan 1x an ，如果在一種算法中， 算 x0k （ k 2，3，4， n）的 需要 k 1 次乘法， 算 p3 ( x0 ) 的 共需要 9 次運算（ 6 次乘法，3 次加法），那么 算 p10(x0 ) 的 共需要次運算。下面 出一種減少運算次數(shù)的算法： p0 (x) a0, pk 1 ( x)xpk (x)ak 1（ k

16、 0， 1，第 5頁共 10頁2， n 1）利用 算法， 算p3 (x0 ) 的 共需要6 次運算， 算p10 ( x0 ) 的 共需要次運算。答案： 65； 20。點 ：秦九韶算法適用一般的多 式f(x)=a nxn+an-1xn-1 + .+a1x+a0 的求 。直接法乘法運算的次數(shù)最多可到達(n1)n ，加法最多 n 次。秦九韶算法通 化把乘法運2算的次數(shù)減少到最多n 次，加法最多n 次。例 4已知多 式函數(shù) f(x)=2x 5 5x 4 4x3 +3x2 6x+7 ，求當 x=5 的函數(shù)的 。解析：把多 式 形 ： f(x)= 2x 5 5x4 4x3+3x 2 6x+7=(2x 5)

17、x 4)x+3)x 6)x+7 算的 程可以列表表示 ：多 式 x 系數(shù)2 543 67運算運算所得的 10251055402670+ 形后 x 的 系數(shù) 25211085342677*5最后的系數(shù) 2677 即 所求的 。算法 程：v0=2v1=2 5 5=5v2=5 5 4=21v3=21 5+3=108v4=108 5 6=534v5=534 5+7=2677點 ：如果多 式函數(shù)中有缺 的 ，要以系數(shù) 0 的 后再 算。 型三：排序例 4 用兩種排序方法將以下 8 個數(shù)： 7,1,3,12,8,4,9,10。按照從大到小的 序 行排序。解析：可以按照直接插入排序和冒泡排序 兩種方法的要求

18、， 合 形， 分析寫出。直接插入法排序：7131284910713128491073112849101273184910第 6頁共 10頁1287314910128743191012987431101210987431冒泡排序7777777711333333331121212121212121218888888814444444419999999911010101010101010第一趟771212121231288910128791098491088491077791044441033333111111第 2 趟第 3 趟第 4 趟第 5 趟第 6 趟點評：直接插入法和冒泡法排序是常見的排序

19、方法，通過該例， 我們對比可以發(fā)現(xiàn)，直接插入排序比冒泡排序更有效一些，執(zhí)行的操作步驟更少一些。例 6給出以下四個數(shù)： 6， 3， 0，15，用直接插入法排序?qū)⑺鼈儼磸男〉酱蟮捻樞蚺帕?，用冒泡法將它們按從大到小的順序排列。分析：不論從大到小的順序還是按從大到小的順序，都可按兩種方法的步驟進行排序。解析：直接插入排序法：6 3015 36015 30615 30615用冒泡排序法排序：6666666151515 33000151566600 3151500000第 7頁共 10頁151515 3 3 33 3 3 3題型 4：進位值例 7把十進制數(shù)89 化為三進制數(shù)，并寫出程序語句.解析：具體的計

20、算方法如下：89=3 29+229=3 9+29=3 3+03=3 1+01=3 0+1所以 :89 （ 10） =1011001(3) 。點評：根據(jù)三進制數(shù)滿三進一的原則，可以用3 連續(xù)去除89 及其所的得的商，然后按倒序的先后順序取出余數(shù)組成數(shù)據(jù)即可。例 8將 8 進制數(shù) 314706（8 ）化為十進制數(shù)，并編寫出一個實現(xiàn)算法的程序。解析： 314706 （8）=3 85432+18 +4 8 +7 8 +0 81+6 80=104902。所以，化為十進制數(shù)是104902。點評：利用把 k 進制數(shù)轉(zhuǎn)化為十進制數(shù)的一般方法就可以把8 進制數(shù) 314706（ 8）化為十進制數(shù)，然后根據(jù)該算法，

21、利用get 函數(shù)，應(yīng)用循環(huán)結(jié)構(gòu)可以設(shè)計程序。五思維總結(jié)1求最大公約數(shù)開始（ 1）輾轉(zhuǎn)相除法程序框圖與程序語句程序：輸入： m,ninput “m ， n= ”;m,ndor=m mod nr=m mod nm=nn=rm=nloop until r=0printn=rendnr=0?y輸出：開始第 8頁共 10頁（ 2）更相減損術(shù)更相減損術(shù)程序：input “請輸入兩個不相等的正整數(shù)”；a， bi=0while a mod 2=0 and b mod 2=0a=a/2b=b/2i=i+1wenddoif ba thent=aa=bb=tend ifc=a ba=bb=cloop until a=bprint aiend對于兩個正整數(shù)如何選擇合適的方法求他們的最大公約數(shù)方法適用范圍及特點短除法適合兩個較小的正整數(shù)或兩個質(zhì)因數(shù)較少的正整數(shù)，簡便易操作。窮舉法適合計算機操作，但一一驗證過于繁瑣。輾轉(zhuǎn)相除法適用于兩個較大的正整數(shù)，以除法為主，輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小差別較大時計算次數(shù)較明顯。更相減損術(shù)適用于兩個較大的正整數(shù)，更相減損術(shù)以減法為主，計算次數(shù)上相對于輾轉(zhuǎn)相處法較多。2我們以這個5 次多項式函數(shù)為例加以說明，設(shè)：f （ x） =a5x5+a4x4 +a3x3+a2x2