【正文】 第 1 頁 共 23 頁 普通高中課程標(biāo)準(zhǔn)實驗教科書 — 數(shù)學(xué) [人教版 ] 高三新 數(shù)學(xué) 第一輪復(fù)習(xí)教案（講座 17） — 算法案例 一．課標(biāo)要求： 通過閱讀中國古代數(shù)學(xué)中的算法案例，體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的貢獻(xiàn)。 二．命題走向 算法是高中數(shù)學(xué)新課程中的新增內(nèi)容，本講的重點是幾種重要的算法案例思想，復(fù)習(xí)時重算法的思想輕算法和程序的構(gòu)造。 預(yù)測 20xx 年高考隊本講的考察是：以選擇題或填空題的形式出現(xiàn)，分值在 5 分左右，考察的熱點是算法實例和傳統(tǒng)數(shù)學(xué)知識的結(jié)合題目。 三．要點精講 1．求最大公約數(shù) （ 1） 短除法 求兩個正整數(shù)的最大公約數(shù)的步 驟：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來。 （ 2） 窮舉法（也叫枚舉法） 窮舉法 求兩個正整數(shù)的最大公約數(shù)的解題 步驟： 從兩個數(shù)中較小數(shù) 開始 由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù) 。 （ 3） 輾轉(zhuǎn)相除法 輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下： ① 輸入兩個正整數(shù) m 和 n； ② 求余數(shù) r：計算 m 除以 n，將所得余數(shù)存放到變量 r 中； ③更新被除數(shù)和余數(shù)： m=n， n=r； ④判斷余數(shù) r 是否為 0。若余數(shù)為 0，則輸出結(jié)果；否則轉(zhuǎn)向 第②步繼續(xù)循環(huán)執(zhí)行。 如此循環(huán)，直到得到結(jié)果為止。 （ 4） 更相減損術(shù) 我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。在《九章算術(shù)》中記載了更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母?子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。 步驟： Ⅰ ． 任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用 2 約簡；若不是，執(zhí)行第二步。 Ⅱ ． 以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。 2．秦九韶算 法 秦九韶算法的一般規(guī)則： 秦九韶算法適用一般的多項式 f(x)=anxn+an1xn1+….+ a1x+a0 的求值問題。用秦九韶算法求一般多項式 f(x)= anxn+an1xn1+….+ a1x+a0 當(dāng) x=x0 時的函數(shù)值，可把 n 次多項式的求值問題轉(zhuǎn)化成求 n 個一次多項式的值的問題，即求 第 2 頁 共 23 頁 v0=an v1=anx+an－ 1 v2=v1x+an－ 2 v3=v2x+an－ 3 …… .. vn=vn－ 1x+a0 觀察秦九韶算法的數(shù)學(xué)模型，計算 vk 時要用到 vk－ 1 的值，若令 v0=an。 我們可以得到下面的遞推公式： v0=an vk=vk－ 1+an－ k(k=1,2,… n) 這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用循環(huán)結(jié)構(gòu)來實現(xiàn)。 排序的算法很多，課本主要介紹里兩種排序方法： 直接插入排序和 冒泡排序 （ 1） 直接插入排序 在日常生活中，經(jīng)常碰到這樣一類排序問題：把新的數(shù)據(jù)插入到已經(jīng)排好順序的數(shù)據(jù)列中。 例如：一組從小到大排好順序的數(shù)據(jù)列 {1， 3， 5， 7， 9， 11， 13}，通常稱之為有序列，我們用序號 1， 2， 3，??表示數(shù)據(jù)的位置，欲把一個新的數(shù)據(jù) 8 插入到上述序列中。 完成這個工作要考慮兩個問題： （ 1）確定數(shù)據(jù) “ 8”在原有序列中應(yīng)該占有的位置序號。數(shù)據(jù)“ 8”所處的位置應(yīng)滿足小于或等于原有序列右邊所有的數(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， 49， 65} ???? 按照這種方法，直到將最后一個數(shù)據(jù) 65 插入到上述有序列中，得到 {13， 27， 38， 49， 49， 65， 76， 97} 這樣，就完成了整個數(shù)據(jù)列的排序工作。注意到無序列“插入排序算法”成為了解決這類問題的平臺。 （ 2） 冒泡法排序 所謂冒泡法排序，形象地說，就是將一組數(shù)據(jù)按照從小到大的順序排列時，小的數(shù)據(jù)視為質(zhì)量輕的，大的數(shù)據(jù)視為質(zhì)量沉的。一個小的數(shù)據(jù)就好比水中的氣泡，往上移動，一個較大的數(shù)據(jù)就好比石頭，往下移動。顯然最終會沉到水底，最輕的會浮到頂，反復(fù)進行，直到數(shù) 據(jù)列排成為有序列。以上過程反映了這種排序方法的基本思路。 第 3 頁 共 23 頁 我們先對一組數(shù)據(jù)進行分析。 設(shè)待排序的數(shù)據(jù)為： {49， 38， 65， 97， 76， 13， 27， 49} 排序的具體操作步驟如下： 1．將第 1 個數(shù)與右邊相鄰的數(shù) 38 進行比較，因為 3849， 49 應(yīng)下沉，即向右移動，所以交換他們的位置，得到新的數(shù)據(jù)列： {38， 49， 65， 97， 76， 13， 27， 49} 2．將新數(shù)據(jù)列中的第 2 個數(shù) 49 與右邊相鄰的數(shù) 65 進行比較，因為 6549，所以順序不變，得到新的數(shù)據(jù)列： {38， 49， 65， 97， 76， 13， 27， 49} 3．將新數(shù)據(jù)列中的第 3 個數(shù) 65 與右邊相鄰的數(shù) 97 進行比較，因為 9765，所以順序不變，得到新的數(shù)據(jù)列： {38， 49， 65， 97， 76， 13， 27， 49} 4．將新數(shù)據(jù)列中的第 4 個數(shù) 97 與右邊相鄰的數(shù) 76 進行比較，因為 7697， 97 應(yīng)下沉，所以順序不變，得到新的數(shù)據(jù)列： {38， 49， 65， 76， 97， 13， 27， 49} 5．將新數(shù)據(jù)列中的第 5 個數(shù) 97 與右邊相鄰的數(shù) 13 進行比較，因為 1397， 97 應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列： {38， 49， 65， 76， 13， 97， 27， 49} 6．將新 數(shù)據(jù)列中的第 6 個數(shù) 97 與右邊相鄰的數(shù) 27 進行比較，因為 2797， 97 應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列： {38， 49， 65， 76， 13， 97， 27， 49} 7．將新數(shù)據(jù)列中的第 7 個數(shù) 97 與右邊相鄰的數(shù) 49 進行比較，因為 4997， 97 應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列： {38， 49， 65， 76， 13， 97， 49， 27} 我們把上述過程稱為一趟排序。其基本特征是最大的數(shù)據(jù)沉到底，即排在最左邊位置上的數(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 進制?，F(xiàn)在最常用的是十進制，通常使用 10 個阿拉伯?dāng)?shù)字 0— 9 進行記數(shù)。 對于任何一個數(shù)，我們可以用不同的進位制來表示。比如：十進數(shù) 57，可以用二進制表示為 111001，也可以用八進制表示為 7用十六進制表示為 39，它們所代表的數(shù)值都是一樣的。 一般 地，若 k 是一個大于一的整數(shù)，那么以 k 為基數(shù)的 k 進制可以表示為： 1 1 0 ( ) 1 1 0.. . ( 0 , 0 , .. ., , )n n k n na a a a a k a a a k??? ? ? ?， 而表示各種進位制數(shù)一般在數(shù)字右下腳加注來表示 ,如 111001(2)表示二進制數(shù) ,34(5)表示 5 進制數(shù)。 第 4 頁 共 23 頁 （ 2） 進位制間的轉(zhuǎn)換 關(guān)于進位制的轉(zhuǎn)換，教科書上以十進制和二進制之間的轉(zhuǎn)換為例講解，并推廣到十進制和其它進制之間的轉(zhuǎn)換。這樣做的原因是，計算機是以二進制的形式進行存儲和計算數(shù)據(jù)的，而一般我們傳輸給計算機的數(shù)據(jù)是十進制數(shù)據(jù)，因此計算機必須先將十進制數(shù)轉(zhuǎn)換為二進制數(shù)，再處理，顯然運算后首 次得到的結(jié)果為二進制數(shù)，同時計算機又把運算結(jié)果由二進制數(shù)轉(zhuǎn)換成十進制數(shù)輸出。 非十進制數(shù)轉(zhuǎn)換為十進制數(shù)比較簡單，只要計算下面的式子值即可： 0111011 . .. .. .. ..)(. .. .. akakakakaaaa nnnnnn ???????? ??? 第一步：從左到右依次取出 k 進制數(shù) )(..... 011 kaaaa nn ? 各位上的數(shù)字，乘以