新課標(biāo)高三數(shù)學(xué)第一輪復(fù)習(xí)單元講座第17講 算法案例

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

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

3、下：①輸入兩個(gè)正整數(shù)m和n；②求余數(shù)r：計(jì)算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ù)約之。步驟：Ⅰ任意給出

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

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

6、順序不變，得到新的數(shù)據(jù)列：38，49，65，97，76，13，27，494將新數(shù)據(jù)列中的第4個(gè)數(shù)97與右邊相鄰的數(shù)76進(jìn)行比較，因?yàn)?697，97應(yīng)下沉，所以順序不變，得到新的數(shù)據(jù)列：38，49，65，76，97，13，27，495將新數(shù)據(jù)列中的第5個(gè)數(shù)97與右邊相鄰的數(shù)13進(jìn)行比較，因?yàn)?397，97應(yīng)下沉，所以順序改變，得到新的數(shù)據(jù)列：38，49，65，76，13，97，27，496將新數(shù)據(jù)列中的第6個(gè)數(shù)97與右邊相鄰的數(shù)27進(jìn)行比

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

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