2010屆高考數(shù)學(xué)復(fù)習(xí)必備試題算法案例

《2010屆高考數(shù)學(xué)復(fù)習(xí)必備試題算法案例》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法案例一．【課標(biāo)要求】通過閱讀中國古代數(shù)學(xué)中的算法案例，體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的貢獻(xiàn)。二．【命題走向】算法是高中數(shù)學(xué)新課程中的新增內(nèi)容，本講的重點(diǎn)是幾種重要的算法案例思想，復(fù)習(xí)時重算法的思想輕算法和程序的構(gòu)造。預(yù)測2010年高考隊(duì)本講的考察是：以選擇題或填空題的形式出現(xiàn)，分值在5分左右，考察的熱點(diǎn)是算法實(shí)例和傳統(tǒng)數(shù)學(xué)知識的結(jié)合題目三．【要點(diǎn)精講】1．求最大公約數(shù)（1）短除法求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來（2）窮舉法（也叫枚舉法）窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：

2、從兩個數(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ù)約之步驟

3、：Ⅰ．任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。Ⅱ．以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。2．秦九韶算法秦九韶算法的一般規(guī)則：秦九韶算法適用一般的多項(xiàng)式f(x)=anxn+an-1xn-1+….+a1x+a0的求值問題。用秦九韶算法求一般多項(xiàng)式f(x)=anxn+an-1xn-1+….+a1x+a0當(dāng)x=x0時的函數(shù)值，可把n次多項(xiàng)式的求值問題轉(zhuǎn)化成求n個一次多項(xiàng)式的值的問題，即求v0=anv1=anx+an－1v2=v1x+an－2

4、v3=v2x+an－3……..vn=vn－1x+a0觀察秦九韶算法的數(shù)學(xué)模型，計算vk時要用到vk－1的值，若令v0=an。我們可以得到下面的遞推公式：v0=anvk=vk－1+an－k(k=1,2,…n)這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)3.排序排序的算法很多，課本主要介紹里兩種排序方法：直接插入排序和冒泡排序（1）直接插入排序在日常生活中，經(jīng)常碰到這樣一類排序問題：把新的數(shù)據(jù)插入到已經(jīng)排好順序的數(shù)據(jù)列中。例如：一組從小到大排好順序的數(shù)據(jù)列{1，3，5，7，9，11，13}，通常稱之為有序列，我們用序號1，2，3，……表示數(shù)據(jù)的位置，欲把一個新

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

6、有序列：{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ù)進(jìn)行，直到數(shù)據(jù)列排成為有序列。以上過程反映了這種排序方法的基本思路。我們先對一組數(shù)據(jù)進(jìn)行分析。設(shè)待排

7、序的數(shù)據(jù)為：{49，38，65，97，76，13，27，49}排序的具體操作步驟如下：1．將第1個數(shù)與右邊相鄰的數(shù)38進(jìn)行比較，因?yàn)?8<49，49應(yīng)下沉，即向右移動，所以交換他們的位置，得到新的數(shù)據(jù)列：{38，49，65，97，76，13，27，49}2．將新數(shù)據(jù)列中的第2個數(shù)49與右邊相鄰的數(shù)65進(jìn)行比較，因?yàn)?5>49，所以順序不變，得到新的數(shù)據(jù)列：{38，49，65，97，76，13，27，49}3．將新數(shù)據(jù)列中的第3個數(shù)65與右邊相鄰的數(shù)97進(jìn)行比較，因?yàn)?7>65，所以順序不變，得到新的數(shù)據(jù)列：{38，49，65，97，76，