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

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

1個數與右側相鄰的數

38進行比較，因為

38<49，49應下沉，即向右挪動，所以互換他們的地點，獲得新的數據列：{38，49，65，97，76，13，27，49}2．將新數據列中的第

2個數

49與右側相鄰的數

65進行比較，因為

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

3個數

65與右側相鄰的數

97進行比較，因為

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

{38，49，65，97，76，13，27，49}4個數97與右側相鄰的數76進行比較，因為

76<97，97

應下沉，所以次序不變，獲得新的數據列：5．將新數據列中的第

{38，49，65，76，97，13，27，49}5個數97與右側相鄰的數13進行比較，

因為

13<97，97

應下沉，所以次序改變，獲得新的數據列：6．將新數據列中的第

{38，49，65，76，13，97，27，49}6個數97與右側相鄰的數27進行比較，因為

27<97，97

應下沉，所以次序改變，獲得新的數據列：7．將新數據列中的第

{38，49，65，76，13，97，27，49}7個數97與右側相鄰的數49進行比較，因為

49<97，97

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