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

算法事例一．【課標(biāo)要求】經(jīng)過(guò)閱讀中國(guó)古代數(shù)學(xué)中的算法事例，領(lǐng)會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn)。二．【命題走向】算法是高中數(shù)學(xué)新課程中的新增內(nèi)容，本講的重點(diǎn)是幾種重要的算法事例思想，復(fù)習(xí)時(shí)重算法的思想輕算法和程序的結(jié)構(gòu)。展望2010年高考隊(duì)本講的觀察是：以選擇題或填空題的形式出現(xiàn)，分值在5分左右，觀察的熱門(mén)是算法實(shí)例和傳統(tǒng)數(shù)學(xué)知識(shí)的聯(lián)合題目三．【重點(diǎn)精講】1．求最大條約數(shù)（1）短除法求兩個(gè)正整數(shù)的最大條約數(shù)的步驟：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，向來(lái)除到所得的商是兩個(gè)互質(zhì)數(shù)為止，而后把全部的除數(shù)連乘起來(lái)2）窮舉法（也叫列舉法）窮舉法求兩個(gè)正整數(shù)的最大條約數(shù)的解題步驟：從兩個(gè)數(shù)中較小數(shù)開(kāi)始由大到小列舉，直到找到條約數(shù)立刻中止列舉，獲得的條約數(shù)即是最大條約數(shù)3）展轉(zhuǎn)相除法展轉(zhuǎn)相除法求兩個(gè)數(shù)的最大條約數(shù)，其算法能夠描繪以下：①輸入兩個(gè)正整數(shù)m和②求余數(shù)r：計(jì)算m除以n，將所得余數(shù)寄存到變量r中；③更新被除數(shù)和余數(shù)：m=n，n=r；④判斷余數(shù)r能否為0。若余數(shù)為0，則輸出結(jié)果；不然轉(zhuǎn)向第②步持續(xù)循環(huán)履行這樣循環(huán)，直到獲得結(jié)果為止。

n；4）更相減損術(shù)我國(guó)初期也有解決求最大條約數(shù)問(wèn)題的算法，就是更相減損術(shù)。在《九章算術(shù)》中記錄了更相減損術(shù)求最大條約數(shù)的步驟：可半者半之，不行半者，副置分母?子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之步驟：Ⅰ．隨意給出兩個(gè)正數(shù)；判斷它們能否都是偶數(shù)。假如，用2約簡(jiǎn)；若不是，履行第二步。Ⅱ．以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。持續(xù)這操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大條約數(shù)。2．秦九韶算法秦九韶算法的一般規(guī)則：秦九韶算法合用一般的多項(xiàng)式f(x)=anxn+an-1xn-1+.+a1x+a0的求值問(wèn)題。用秦九韶算法求一般多項(xiàng)式f(x)=anxn+an-1xn-1+.+a1x+a0當(dāng)x=x0時(shí)的函數(shù)值，可把n次多項(xiàng)式的求值問(wèn)題轉(zhuǎn)變成求n個(gè)一次多項(xiàng)式的值的問(wèn)題，即求v0=anv1=anx+an－1v2=v1x+an－2v3=v2x+an－3..vn=vn－1x+a0察看秦九韶算法的數(shù)學(xué)模型，計(jì)算vk時(shí)要用到vk－1的值，若令v0=an。我們能夠獲得下邊的遞推公式：v0=anvk=vk－1+an－k(k=1,2,n)這是一個(gè)在秦九韶算法中頻頻履行的步驟，能夠用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)排序排序的算法好多，課本主要介紹里兩種排序方法：直接插入排序和冒泡排序（1）直接插入排序在平時(shí)生活中，常常遇到這樣一類(lèi)排序問(wèn)題：把新的數(shù)據(jù)插入到已經(jīng)排好次序的數(shù)據(jù)列中。比如：一組從小到大排好次序的數(shù)據(jù)列{1，3，5，7，9，11，13}，往常稱(chēng)之為有序列，我們用序號(hào)1，2，3，表示數(shù)據(jù)的地點(diǎn)，欲把一個(gè)新的數(shù)據(jù)8插入到上述序列中。達(dá)成這個(gè)工作要考慮兩個(gè)問(wèn)題：（1）確立數(shù)據(jù)“8”在原有序列中應(yīng)當(dāng)據(jù)有的地點(diǎn)序號(hào)。數(shù)據(jù)“8”所處的地點(diǎn)應(yīng)知足小于或等于原有序列右側(cè)全部的數(shù)據(jù)，大于其左側(cè)地點(diǎn)上全部的數(shù)據(jù)。（2）將這個(gè)地點(diǎn)空出來(lái)，將數(shù)據(jù)“8”插進(jìn)去。對(duì)于一列無(wú)序的數(shù)據(jù)列，比如：{49，38，65，97，76，13，27，49}，怎樣使用這類(lèi)方法進(jìn)行排序呢？基本思想很簡(jiǎn)單，即頻頻使用上述方法排序，由序列的長(zhǎng)度不停增添，向來(lái)抵達(dá)成整個(gè)無(wú)序列就有序了第一，{49}是有序列，我們將38插入到有序列{49}中，獲得兩個(gè)數(shù)據(jù)的有序列：{38，49}，而后，將第三個(gè)數(shù)據(jù)65插入到上述序列中，獲得有序列：{38，49，65}依據(jù)這類(lèi)方法，直到將最后一個(gè)數(shù)據(jù)65插入到上述有序列中，獲得{13，27，38，49，49，65，76，97}這樣，就達(dá)成了整個(gè)數(shù)據(jù)列的排序工作。注意到無(wú)序列“插入排序算法”成為認(rèn)識(shí)決這類(lèi)問(wèn)題的平臺(tái)（2）冒泡法排序所謂冒泡法排序，形象地說(shuō)，就是將一組數(shù)據(jù)依據(jù)從小到大的次序擺列時(shí)，小的數(shù)據(jù)視為質(zhì)量輕的，大的數(shù)據(jù)視為質(zhì)量沉的。一個(gè)小的數(shù)據(jù)就好似水中的氣泡，往上挪動(dòng)，一個(gè)較大的數(shù)據(jù)就好似石頭，往下挪動(dòng)。明顯最后會(huì)沉到水底，最輕的會(huì)浮到頂，頻頻進(jìn)行，直到數(shù)據(jù)列排成為有序列。以上過(guò)程反應(yīng)了這類(lèi)排序方法的基本思路。我們先對(duì)一組數(shù)據(jù)進(jìn)行剖析。設(shè)待排序的數(shù)據(jù)為：{49，38，65，97，76，13，27，49}排序的詳細(xì)操作步驟以下：1．將第

1個(gè)數(shù)與右側(cè)相鄰的數(shù)

38進(jìn)行比較，因?yàn)?/p>

38<49，49應(yīng)下沉，即向右挪動(dòng)，所以互換他們的地點(diǎn)，獲得新的數(shù)據(jù)列：{38，49，65，97，76，13，27，49}2．將新數(shù)據(jù)列中的第

2個(gè)數(shù)

49與右側(cè)相鄰的數(shù)

65進(jìn)行比較，因?yàn)?/p>

65>49，所以次序不變，獲得新的數(shù)據(jù)列：{38，49，65，97，76，13，27，49}3．將新數(shù)據(jù)列中的第

3個(gè)數(shù)

65與右側(cè)相鄰的數(shù)

97進(jìn)行比較，因?yàn)?/p>

97>65，所以次序不變，獲得新的數(shù)據(jù)列：4．將新數(shù)據(jù)列中的第

{38，49，65，97，76，13，27，49}4個(gè)數(shù)97與右側(cè)相鄰的數(shù)76進(jìn)行比較，因?yàn)?/p>

76<97，97

應(yīng)下沉，所以次序不變，獲得新的數(shù)據(jù)列：5．將新數(shù)據(jù)列中的第

{38，49，65，76，97，13，27，49}5個(gè)數(shù)97與右側(cè)相鄰的數(shù)13進(jìn)行比較，

因?yàn)?/p>

13<97，97

應(yīng)下沉，所以次序改變，獲得新的數(shù)據(jù)列：6．將新數(shù)據(jù)列中的第

{38，49，65，76，13，97，27，49}6個(gè)數(shù)97與右側(cè)相鄰的數(shù)27進(jìn)行比較，因?yàn)?/p>

27<97，97

應(yīng)下沉，所以次序改變，獲得新的數(shù)據(jù)列：7．將新數(shù)據(jù)列中的第

{38，49，65，76，13，97，27，49}7個(gè)數(shù)97與右側(cè)相鄰的數(shù)49進(jìn)行比較，因?yàn)?/p>

49<97，97

應(yīng)下沉，所以次序改變，獲得新的數(shù)據(jù)列：{38，49，65，76，13，97，49，27}我們把上述過(guò)程稱(chēng)為一趟排序。其基本特色是最大的數(shù)據(jù)沉究竟，即排在最左側(cè)地點(diǎn)上的數(shù)據(jù)是數(shù)組中最大的數(shù)據(jù)。頻頻履行上邊的步驟，就能達(dá)成排序工作，排序過(guò)程不會(huì)超出趟。這類(lèi)排序的方法稱(chēng)為冒泡排序。上邊的剖析擁有一般性，假如數(shù)據(jù)列有n個(gè)數(shù)據(jù)構(gòu)成，至多經(jīng)過(guò)n－1趟排序，就能完成整個(gè)排序過(guò)程4．進(jìn)位制（1）觀點(diǎn)進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不一樣的地點(diǎn)表示不一樣的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱(chēng)為基數(shù)，基數(shù)為n，即可稱(chēng)n進(jìn)位制，簡(jiǎn)稱(chēng)n進(jìn)制。此刻最常用的是十進(jìn)制，往常使用10個(gè)阿拉伯?dāng)?shù)字0—9進(jìn)行記數(shù)。對(duì)于任何一個(gè)數(shù)，我們能夠用不一樣的進(jìn)位制來(lái)表示。比方：十進(jìn)數(shù)57，能夠用二進(jìn)制表示為111001，也能夠用八進(jìn)制表示為71、用十六進(jìn)制表示為39，它們所代表的數(shù)值都是同樣的。一般地，若k是一個(gè)大于一的整數(shù)，那么以k為基數(shù)的k進(jìn)制能夠表示為：anan1...a1a0(k)(0ank,0an1,...,a1,a0k)，而表示各樣進(jìn)位制數(shù)一般在數(shù)字右下腳加注來(lái)表示,如111001表示二進(jìn)制數(shù),34(5)表(2)示5進(jìn)制數(shù)。（2）進(jìn)位制間的變換對(duì)于進(jìn)位制的變換，教科書(shū)上以十進(jìn)制和二進(jìn)制之間的變換為例解說(shuō)，并推行到十進(jìn)制和其余進(jìn)制之間的變換。這樣做的原由是，計(jì)算機(jī)是以二進(jìn)制的形式進(jìn)行儲(chǔ)存和計(jì)算數(shù)據(jù)的，而一般我們傳輸給計(jì)算機(jī)的數(shù)據(jù)是十進(jìn)制數(shù)據(jù)，所以計(jì)算機(jī)一定先將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，再辦理，明顯運(yùn)算后初次獲得的結(jié)果為二進(jìn)制數(shù)，同時(shí)計(jì)算機(jī)又把運(yùn)算結(jié)果由二進(jìn)制數(shù)變換成十進(jìn)制數(shù)輸出。非十進(jìn)制數(shù)變換為十進(jìn)制數(shù)比較簡(jiǎn)單，只需計(jì)算下邊的式子值即可：第一步：從左到右挨次拿出k進(jìn)制數(shù)anan1.....a1a0(k)各位上的數(shù)字，乘以相應(yīng)的k的冪，k的冪從n開(kāi)始取值，每次遞減1，遞減到0，即ankn,an1kn1,.........,a1k,a0k0；第二步：把所獲得的乘積加起來(lái)，所得的結(jié)果就是相應(yīng)的十進(jìn)制數(shù)。十進(jìn)制數(shù)變換成非十進(jìn)制數(shù)把十進(jìn)制數(shù)變換為二進(jìn)制數(shù)，教科書(shū)上供給了“除2取余法”，我們能夠類(lèi)比獲得十進(jìn)制數(shù)變換成k進(jìn)制數(shù)的算法“除k取余法”。非十進(jìn)制之間的變換一個(gè)自然的想法是利用十進(jìn)制作為橋梁。教科書(shū)上供給了一個(gè)二進(jìn)制數(shù)據(jù)與16進(jìn)制數(shù)據(jù)之間的互化的方法，也就是先有二進(jìn)制數(shù)轉(zhuǎn)變?yōu)槭M(jìn)制數(shù)，再由十進(jìn)制數(shù)轉(zhuǎn)變成為16進(jìn)制數(shù)。四．【典例分析】題型1：求最大條約數(shù)例1．（1）用展轉(zhuǎn)相除法求123和48的最大條約數(shù)？（2）用更相減損來(lái)求80和36的最大條約數(shù)？分析：（1）展轉(zhuǎn)相除法求最大條約數(shù)的過(guò)程以下：（成立帶余除式）123＝2×48＋2748＝1×27＋2127＝1×21＋621＝3×6＋36＝2×3+0最后6能被3整除，得123和48的最大條約數(shù)為3。2）剖析：我們將80作為大數(shù)，36作為小數(shù)，履行更相減損術(shù)來(lái)求兩數(shù)的最大條約數(shù)。履行結(jié)束的準(zhǔn)則是減數(shù)和差相等更相減損術(shù)：因?yàn)?0和36都是偶數(shù)，要去公因數(shù)2。80÷2=40，36÷2=18；40和18都是偶數(shù)，要去公因數(shù)2。40÷2=20，18÷2=9下邊來(lái)求20與9的最大條約數(shù)，20－9=1111－9=29－2=77－2=55－2=33－2=12－1=1可得80和36的最大條約數(shù)為22×1=4。評(píng)論：對(duì)照兩種方法控制好算法的結(jié)束，展轉(zhuǎn)相除法是抵達(dá)余數(shù)為0，更相減損術(shù)是到達(dá)減數(shù)和差相等。例2．設(shè)計(jì)一個(gè)算法，求出840與1764的最大公因數(shù)。分析：我們已經(jīng)學(xué)習(xí)過(guò)了對(duì)自然數(shù)的素因數(shù)分解的方法，下邊的算法就是在此基礎(chǔ)上設(shè)計(jì)的。解題思路以下：第一對(duì)兩個(gè)數(shù)進(jìn)行素因數(shù)分解：840=23×3×5×7，1764=22×32×72，其次，確立兩個(gè)數(shù)的公共素因數(shù)：2，3，7。接著確立公共素因數(shù)的指數(shù)：對(duì)于公共素因數(shù)2，840中為23，1764中為22，應(yīng)取較少的一個(gè)22，同理可得下邊的因數(shù)為3和7。算法步驟：第一步：將840進(jìn)行素?cái)?shù)分解23×3×5×7；第二步：將1764進(jìn)行素?cái)?shù)分解22×32×72；第三步：確立它們的公共素因數(shù)：2，3，7；第四步：確立公共素因數(shù)2，3，7的指數(shù)分別是：2，1，1；第五步：最大公因數(shù)為22×31×71=84。評(píng)論：質(zhì)數(shù)是除１之外只好被１和自己整除的正整數(shù)，它應(yīng)當(dāng)是無(wú)窮多個(gè)，可是當(dāng)前沒(méi)有一個(gè)規(guī)律來(lái)確立全部的質(zhì)數(shù)題型2：秦九韶算法例3．（2009福州模擬）假如履行右邊的程序框圖，那么輸出的S（）開(kāi)始A．22B．46i1,s1C．94D．190答案C2、（2009浙江卷理）某程ii1序框圖以下圖，該程序運(yùn)轉(zhuǎn)后輸出的k的值是（）A．4B．5s2(s1)C．6D．7【分析】對(duì)于k0,s1,k1，而對(duì)于k1,s3,k2，則i5?否是輸出s結(jié)束k2,s38,k3，后邊是k3,s38211,k4，不切合條件時(shí)輸出的k4．答案A3、（2009天津卷理）閱讀上（右）圖的程序框圖，則輸出的S=()A26B35C40D57【分析】當(dāng)i1時(shí)，T2,S2；當(dāng)i2時(shí)，T5,S7；當(dāng)i3時(shí)，T8,S15；當(dāng)i4時(shí)，T11,S26；當(dāng)i5時(shí)，T14,S40；當(dāng)i6時(shí)，T17,S57，應(yīng)選擇C。答案Ｃ4（2009安徽卷文）程序框圖上（右）（即算法流程圖）以下圖，其輸入結(jié)果是_______?！痉治觥恳罁?jù)流程圖可得a的取值挨次為1、3、7、15、31、63答案127評(píng)論：秦九韶算法合用一般的多項(xiàng)式f(x)=anxn+an-1xn-1+.+a1x+a0的求值問(wèn)題。直接法乘法運(yùn)算的次數(shù)最多可抵達(dá)(n1)n，加法最多n次。秦九韶算法經(jīng)過(guò)轉(zhuǎn)變把乘法運(yùn)算的次數(shù)2減少到最多n次，加法最多n次。例4．已知多項(xiàng)式函數(shù)f(x)=2x5－5x4－4x3+3x2－6x+7，求當(dāng)x=5時(shí)的函數(shù)的值。分析：把多項(xiàng)式變形為：f(x)=2x5－5x4－4x3+3x2－6x+7=((((2x－5)x－4)x+3)x－6)x+7計(jì)算的過(guò)程能夠列表表示為：多項(xiàng)式x系數(shù)2－5－43－67運(yùn)算運(yùn)算所得的值10251055402670+變形后x的"系數(shù)"25211085342677*5最后的系數(shù)2677即為所求的值算法過(guò)程：0v=21v=2×5－5=5v2=5×5－4=21v3=21×5+3=1084v=108×5－6=534v=534×5+7=26775評(píng)論：假如多項(xiàng)式函數(shù)中出缺項(xiàng)的話(huà)，要以系數(shù)為0的項(xiàng)補(bǔ)齊后再計(jì)算。題型三：排序例4．試用兩種排序方法將以下8個(gè)數(shù)：7,1,3,12,8,4,9,10。依據(jù)從大到小的次序進(jìn)行排序。分析：能夠依據(jù)直接插入排序和冒泡排序這兩種方法的要求，聯(lián)合圖形，剖析寫(xiě)出。直接插入法排序：[7]131284910[71]31284910[731]1284910[12731]84910[128731]4910[1287431]910[12987431]10[1210987431]冒泡排序7777777711333333331121212121212121218888888814444444419999999911010101010101010第一趟771212121231288910128791098491088491077791044441033333111111第2趟第3趟第4趟第5趟第6趟評(píng)論：直接插入法和冒泡法排序是常有的排序方法，經(jīng)過(guò)該例，我們對(duì)照能夠發(fā)現(xiàn)，直接插入排序比冒泡排序更有效一些，履行的操作步驟更少一些例6．給出以下四個(gè)數(shù)：6，－3，0，15，用直接插入法排序?qū)⑺鼈儼磸男〉酱蟮拇涡驍[列，用冒泡法將它們按從大到小的次序排剖析：無(wú)論從大到小的次序仍是按從大到小的次序，都可按兩種方法的步驟進(jìn)行排序。分析：直接插入排序法：[6]－3015[－36]015[－306]15[－30615]用冒泡排序法排序：6666666151515－3－3000151566600－3151500000151515－3－3－3－3－3－3－3題型4：進(jìn)位值例7．把十進(jìn)制數(shù)89化為三進(jìn)制數(shù)，并寫(xiě)出程序語(yǔ)句.分析：詳細(xì)的計(jì)算方法以下：89=3×29+229=3×9+29=3×3+03=3×1+01=3×0+1所以:89（10）=1011001(3)。評(píng)論：依據(jù)三進(jìn)制數(shù)滿(mǎn)三進(jìn)一的原則，能夠用3連續(xù)去除89及其所的得的商，而后按倒序的先后次序拿出余數(shù)構(gòu)成數(shù)據(jù)即可。例8．將8進(jìn)制數(shù)314706（8）化為十進(jìn)制數(shù)，并編寫(xiě)出一個(gè)實(shí)現(xiàn)算法的程序。432分析：314706（8）=3×85+1×8+4×8+7×8+0×81+6×80=104902。所以，化為十進(jìn)制數(shù)是104902。評(píng)論：利用把k進(jìn)制數(shù)轉(zhuǎn)變?yōu)槭M(jìn)制數(shù)的一般方法就能夠把8進(jìn)制數(shù)314706（8）化為十進(jìn)制數(shù)，而后依據(jù)該算法，利用GET函數(shù)，應(yīng)用循環(huán)結(jié)構(gòu)能夠設(shè)計(jì)程序。五．【思想總結(jié)】1．求最大條約數(shù)開(kāi)始（1）展轉(zhuǎn)相除法程序框圖與程序語(yǔ)句輸入：m,n程序：INPUT“m，n=”;m,nr=mMODnDOr=mMODnm=nm=nn=rn=rLOOPUNTILr=0PRINTNr=0?ENDY輸出：開(kāi)始2）更相減損術(shù)更相減損術(shù)程序：INPUT“請(qǐng)輸入兩個(gè)不相等的正整數(shù)”；a，bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb<aTHENt=aa=bb=tENDIFc=a－ba=bb=cLOOPUNTILa=bPRINTa^iEND對(duì)于兩個(gè)正整數(shù)怎樣選擇適合的方法求他們的最大條約數(shù)方法合用范圍及特色短除法適合兩個(gè)較小的正整數(shù)或兩個(gè)質(zhì)因數(shù)較少的正整數(shù)，簡(jiǎn)易易操作。窮舉法適共計(jì)算機(jī)操作，但一一考證過(guò)于繁瑣。合用于兩個(gè)較大的正整數(shù)，以除法為主，展轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別展轉(zhuǎn)相除法當(dāng)兩個(gè)數(shù)字大小差異較大時(shí)計(jì)算次數(shù)較明顯。合用于兩個(gè)較大的正整數(shù)，更相減損術(shù)以減法為主，計(jì)算次數(shù)上相對(duì)于展轉(zhuǎn)相更相減損術(shù)處法許多。2．我們以這個(gè)5次多項(xiàng)式函數(shù)為