人教A版高中數學必修3多思、創新、融合第1頁第2頁復習回顧基本結構流程圖次序結構變量與賦值循環結構基本語句循環語句條件語句WHILE語句UNTIL語句IF-THEN語句語句適用結構算法條件結構第3頁我們這節課就利用基本算法程序來處理一些實際問題，深入體會算法程序思想。案例1.輾轉相除法與更相減損術第4頁在初中，我們已經學過求最大條約數知識，你能求出18與30最大條約數嗎？230391535所以，18和30最大條約數是：2×3＝6互質因數不過，當我們處理較大數（如：8251與6105）最大公因數時，假如利用這種方法可能計算量比較大，步驟比較多。下面我們介紹一個古老而有效算法——輾轉相除法第5頁這種算法是歐幾里得公元前300年左右首先提出，所以又叫歐幾里得算法例1求兩個正數8251和6105最大條約數。分析：8251與6105兩數都比較大，而且沒有顯著條約數，如能把它們都變小一點，依據已經有知識即可求出最大條約數解8251＝6105×1＋2146顯然8251和6105最大條約數也必是2146約數，一樣6105與2146條約數也必是8251約數，所以8251與6105最大條約數也是6105與2146最大條約數繼續下去，我們得到：歐幾里得（公元前330-公元前275）：古希臘數學家，雅典人歐幾里得是柏拉圖學生，長久在亞歷山大里亞教書。公元前300年左右，代表作《幾何原本》13卷問世，創建了著名歐氏幾何，至今仍為中學生必學一門基礎知識。歐幾里得對光學也有一定研究。第6頁6105＝2146×2＋1813

2146＝1813×1＋333

1813＝333×5＋148

333＝148×2＋37

148＝37×4＋0

則37為8251與6105最大條約數這就是輾轉相除法，有除法性質能夠知道，對于任意兩個正整數，上述除法步驟總能夠在有限步驟之后完成你能寫出它的算法程序嗎？第7頁利用輾轉相除法求最大條約數步驟以下：第一步：用較大數m除以較小數n得到一個商q0和一個余數r0；第二步：若r0＝0，則n為m，n最大條約數；若r0≠0，則用除數n除以余數r0得到一個商q1和一個余數r1；第三步：若r1＝0，則r1為m，n最大條約數；若r1≠0，則用除數r0除以余數r1得到一個商q2和一個余數r2第n步：依次計算直至rn＝0，此時所得到rn－1即為所求最大條約數………………第8頁r=mMODnm=nn=rr=o?否是程序圖框帶余除法INPUT“請輸入m，n值”；m，nIFm>nTHENa=mm=nn=aENDIFDOr=mMODNm=nn=rLOOPUNTILr=0PRINTmEND作用是什么？為何要用直到型循環結構？第9頁練一練1.利用輾轉相除法求兩數4081與20723最大條約數，寫出它流程框圖和BASIC程序第10頁更相減損術我國早期也有處理求最大條約數問題算法《九章算術》（公元50年～100年或更早）是中國古代數學專著，承先秦數學發展源流，進入漢朝后又經許多學者刪補才最終成書，這大約是公元一世紀下半葉。它出現，標志著中國古代數學體系形成。第11頁歷代數學家把它尊為“算經之首”．這是世界上最早印刷本數學書。

《九章算術》共收有246個數學問題，分為九章。分別是：方田、栗米、衰分、少廣、商功、均輸、盈不足、方程、勾股。

《九章算術》是世界上最早系統敘述了分數運算著作；其中盈不足算法更是一項令人驚奇創造；“方程”章還在世界數學史上首次闡述了負數及其加減運算法則。第12頁更相減損術求最大條約數步驟以下：可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也，以等數約之。翻譯出來為：第一步：任意給出兩個正數；判斷它們是否都是偶數。若是，用2約簡；若不是，執行第二步。第二步：以較大數減去較小數，接著把較小數與所得差比較，并以大數減小數。第三部：繼續第二步，直到所得數相等為止，則這個數（等數）就是所求最大條約數第13頁例2用更相減損術求98與63最大條約數.解因為63不是偶數，把98和63以大數減小數，并輾轉相減98-63＝3563-35＝2835-28＝728-7＝1414-7＝7所以，98與63最大條約數是7兩種算法比較，你有什么發現？第14頁比較輾轉相除法與更相減損術區分（1）都是求最大條約數方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，尤其當兩個數字大小區分較大時計算次數區分較顯著。（2）從結果表達形式來看，輾轉相除法表達結果是以相除余數為0則得到，而更相減損術則以減數與差相等而得到第15頁練習思索一.用輾轉相除法求以下各組數最大條約數，并在自己編寫BASIC程序中驗證。

（1）225，135（2）98，196（3）72，168思索二：用更相減損法可否求上述3組數最大條約數？可否利用更相減損法設計出程序框圖及程序？若能，在電腦上測試自己程序；若不能說明無法實現理由。思索三：利用輾轉相除法是否能夠求兩數最大公倍數？試設計程序框圖并轉換成程序在BASIC中實現。第16頁案例二（秦九韶算法）怎樣求多項式當x=5時值？據我們計算統計能夠得出我們共需要10次乘法運算，5次加法運算我們把多項式變形為：再統計一下計算當初值時需要計算次數，能夠得出僅需4次乘法和5次加法運算即可得出結果。顯然少了6次乘法運算。這種算法就叫秦九韶算法。第17頁秦九韶（1202--1261年），字道古，安岳縣人。其父秦季棲，進士出身，官至工部郎中、秘書少監。秦九韶性敏慧，勤奮好學，幼年隨父居中都（今北京），受到名師指導，學習日益促進。及長，隨父遷湖州（今浙江吳興縣），在西門外修建住房，由秦九韶設計施工，堂分7間，后為列室，僅中堂1間，縱橫7丈，極其宏偉寬大，顯示出他在建筑方面才能它的一般計算步驟如下：第18頁把一個多項式改寫為：第19頁求多項式值時，首先計算最內層括號內一次多項式值，即：再有內向外逐層計算一次多項式值，即：這么將求n次多項式f(x)值轉化為求n個一次多項式值。第20頁例3設計利用秦九韶算法計算5次多項式當時值程序框圖以及BASIC程序。

i=0WHILEi≤5INPUTa[i]WENDDOv=a[5]v=v*x[0]+a[5-n]n=n+1LOOPUNTILn>6END第21頁用秦九韶算法求這個多項式當時值。3.已知一個5次多項式為思索：（1）例1計算時需要多少次乘法計算？多少次加法計算？（2）在利用秦九韶算法計算n次多項式當初需要多少次乘法計算和多少次加法計算？練習第22頁案例3.排序問題你會使用這些字典嗎？第23頁為了便于查詢和檢索，經常需要依據要求將被查尋對象按照一定次序排列，通常稱為排序，你會從這些書籍中查閱你想要東西嗎？第24頁我們在一個已經排好循序一系列數中插入一個數據，成為一個新系列，且仍按原來規則排序。直接插入排序要將8插入到{1,3,5,7,9,11,13}中，我們怎樣考慮？確定8在原系列中位置，使8小于或等于原系列中右邊數據，大于或等于左邊數據將這個位置空出來，將數據8插進去1357911138第25頁例題分析例3.將數列｛49,38,65,97,76,13,27,49}按小到大次序排列我們想法是：1.先排49，38次序：38，492.比較第三個數與它們大小得到：38，49，653.比較第四個數與2次序得到：38，49，65，97n.第n個數與前面數關系，得到最終排序：13，27，38，49，49，65，76，97……第26頁重復使用直接插入排序算法，即首先把第一個數看成一個基準，插入第二個數變成有兩個數據有序列，再插入第三個數，依這類推，就完成了整個無序列有序化。流程圖以下：你會設計它BASIC算法嗎？第27頁1排序號：數據序號12345678原始數據4938659776132749上述數據我們還能夠這么來排序：第28頁2排序數據序號12345678原始數據4938659776132749現將1號數據49和2號數據38比較，因為49>38所以，49和38位置交換，變為：數據序號12345678原始數據3849659776132749第一次排序第一步：1號2號排序第29頁數據序號12345678原始數據3849659776132749第二步：2號3號排序因為49<65所以這倆數序號不變數據序號12345678原始數據3849659776132749第30頁第三步：比較3、4號數據數據序號12345678原始數據3849659776132749方法同第二步，因為65<97所以數據次序不變數據序號12345678原始數據3849659776132749第31頁數據序號12345678原始數據3849659776132749數據序號12345678原始數據3849657697132749第四步：比較4、5號數據方法同第一步，因為97>76，所以4、5號數據交換，則：第32頁第五步：比較5、6號數據：數據序號12345678原始數據3849657697132749數據序號12345678原始數據3849657613972749方法同第二步，97>13則，交換5、6號數據，則：第33頁第六步：比較6、7號數據數據序號12345678原始數據3849657613972749數據序號12345678原始數據3849657613279749同理，上面次序能夠變為：同理第七步比較7、8號數據后能夠變為：第34頁這么就完成了第一次排序，它基本特征是將最大數排到了最右邊，然后再從頭開始，進行第二次排序，將第二大數據排到了倒數第二位，重復下去，就能夠完成排序。一共要進行7次才能完成。我們叫它冒泡排序（bubblesorting）思考你會用冒泡法將上面數據按從大到小次序排列嗎？完成全部排序需要多少步比較？你還有其它排序方法將上面數據按從大到小次序排列嗎？第35頁練習請你設計一個數據列為R[1],R[2],…,R[10],要求從小到大次序排列？1.畫出一次冒泡排序算法流程圖2.畫出整個冒泡排序算法流程圖第36頁一次排序N-1次排完整個排序流程圖如圖所表示第37頁說明1.冒泡法排序完成n個數據一次排序需要n-1次比較，完成整個排序需要(n-1)！次比較，對于數據較多時，計算量很大。2.有些數據冒泡法排序可能用更少步驟能夠完成，后面步驟可能毫無意義，但計算機必須完成。3.交換數據時注意引入第三方變量。第38頁案例4.進位制并請這個人算出5個數和N，在一個游戲中，魔術師請一個人隨意想一個三位數把N告訴魔術師，于是魔術師就能說出這個人所想數現在設N=3194，請你做魔術師，求出數值將也加到和N上，這么a、b、c就在每一位上都恰好出現兩次，所以有分析：①你知道它的原理嗎？第39頁從而3194<222(a+b+c)<3194+1000，而a、b、c是整數所以15≤a+b+c≤18因222

15-3194=136，22216-3194=358，22217-3194=580，22218-3194=802其中只有3+5+8=16能滿足①式實際上，這里面應用到了一個知識：進位制第40頁進位制是人們為了計數和運算方便而約定計數系統，約定滿二進一，就是二進制；滿十進一，就是十進制，等等，也就是說滿幾進一就是幾進制，幾進制基數就是幾大于1整數因為自然數有沒有限多個，對于每一個自然數假如都用一個獨立名稱或符號來讀出它或表示它，那是很不方便，也是不可能做到。所以，需要建立一個讀數、寫數制度--進位制第41頁十進制數表示實際數值為：K進