新課標高三數學第一輪復習單元講座第17講 算法案例

1、第1頁共10頁普通高中課程標準實驗教科書—數學[人教版]高三新高三新數學數學第一輪復習教案（講座第一輪復習教案（講座17）—算法案例算法案例一課標要求：一課標要求：通過閱讀中國古代數學中的算法案例，體會中國古代數學對世界數學發(fā)展的貢獻。二命題走向二命題走向算法是高中數學新課程中的新增內容，本講的重點是幾種重要的算法案例思想，復習時重算法的思想輕算法和程序的構造。預測2007年高考隊本講的考察是：以選擇題或填空題的形式出現，分值在5分左右

2、，考察的熱點是算法實例和傳統數學知識的結合題目。三要點精講三要點精講1求最大公約數（1）短除法求兩個正整數的最大公約數的步驟：先用兩個數公有的質因數連續(xù)去除，一直除到所得的商是兩個互質數為止，然后把所有的除數連乘起來。（2）窮舉法（也叫枚舉法）窮舉法求兩個正整數的最大公約數的解題步驟：從兩個數中較小數開始由大到小列舉，直到找到公約數立即中斷列舉，得到的公約數便是最大公約數。（3）輾轉相除法輾轉相除法求兩個數的最大公約數，其算法可以描述如

3、下：①輸入兩個正整數m和n；②求余數r：計算m除以n，將所得余數存放到變量r中；③更新被除數和余數：m=n，n=r；④判斷余數r是否為0。若余數為0，則輸出結果；否則轉向第②步繼續(xù)循環(huán)執(zhí)行。如此循環(huán)，直到得到結果為止。（4）更相減損術我國早期也有解決求最大公約數問題的算法，就是更相減損術。在《九章算術》中記載了更相減損術求最大公約數的步驟：可半者半之，不可半者，副置分母?子之數，以少減多，更相減損，求其等也，以等數約之。步驟：Ⅰ任意給出

4、兩個正數；判斷它們是否都是偶數。若是，用2約簡；若不是，執(zhí)行第二步。Ⅱ以較大的數減去較小的數，接著把較小的數與所得的差比較，并以大數減小數。繼續(xù)這操作，直到所得的數相等為止，則這個數（等數）就是所求的最大公約數。2秦九韶算法秦九韶算法的一般規(guī)則：秦九韶算法適用一般的多項式f(x)=anxnan1xn1….a1xa0的求值問題。用秦九韶算法求一般多項式f(x)=anxnan1xn1….a1xa0當x=x0時的函數值，可把n次多項式的求值問

5、題轉化成求n個一次多項式的值的問題，即求第3頁共10頁進行，直到數據列排成為有序列。以上過程反映了這種排序方法的基本思路。我們先對一組數據進行分析。設待排序的數據為：49，38，65，97，76，13，27，49排序的具體操作步驟如下：1將第1個數與右邊相鄰的數38進行比較，因為3849，所以順序不變，得到新的數據列：38，49，65，97，76，13，27，493將新數據列中的第3個數65與右邊相鄰的數97進行比較，因為9765，所以

6、順序不變，得到新的數據列：38，49，65，97，76，13，27，494將新數據列中的第4個數97與右邊相鄰的數76進行比較，因為7697，97應下沉，所以順序不變，得到新的數據列：38，49，65，76，97，13，27，495將新數據列中的第5個數97與右邊相鄰的數13進行比較，因為1397，97應下沉，所以順序改變，得到新的數據列：38，49，65，76，13，97，27，496將新數據列中的第6個數97與右邊相鄰的數27進行比

7、較，因為2797，97應下沉，所以順序改變，得到新的數據列：38，49，65，76，13，97，27，497將新數據列中的第7個數97與右邊相鄰的數49進行比較，因為4997，97應下沉，所以順序改變，得到新的數據列：38，49，65，76，13，97，49，27我們把上述過程稱為一趟排序。其基本特征是最大的數據沉到底，即排在最左邊位置上的數據是數組中最大的數據。反復執(zhí)行上面的步驟，就能完成排序工作，排序過程不會超過7趟。這種排序的方法

8、稱為冒泡排序。上面的分析具有一般性，如果數據列有n個數據組成，至多經過n－1趟排序，就能完成整個排序過程。4進位制（1）概念進位制是一種記數方式，用有限的數字在不同的位置表示不同的數值。可使用數字符號的個數稱為基數，基數為n，即可稱n進位制，簡稱n進制?，F在最常用的是十進制，通常使用10個阿拉伯數字0—9進行記數。對于任何一個數，我們可以用不同的進位制來表示。比如：十進數57，可以用二進制表示為111001，也可以用八進制表示為71、用