1.4.1算法案例

1、1.3 算 法 案 例- 輾轉相除法與更相減損術 授課教師：李梅知識回顧思考： 編寫計算機程序的步驟是？第一步，寫算法步驟第二步，畫程序框圖第三步，編制程序探究發(fā)現(xiàn)問題1.求下面數(shù)的最大公約數(shù).每組數(shù)的最大公約數(shù)為6問題2.求210與66的最大公約數(shù)還有什么方法？ 210與66的最大公約數(shù)和66與12的最大公約數(shù)相同66與12的最大公約數(shù)和12與6的最大公約數(shù)相同12與6的最大公約數(shù)為6所以210與66的最大公約數(shù)為6探究發(fā)現(xiàn)研探新知問題3.求8251與6105的最大公約數(shù).8251與6105最大公約數(shù)和6105與2146最大公約數(shù)相同6105與2146最大公約數(shù)和2146與1813最大公約數(shù)

2、相同2146與1813最大公約數(shù)和1813與333最大公約數(shù)相同1813與333最大公約數(shù)和333與148最大公約數(shù)相同333與148最大公約數(shù)148和37與最大公約數(shù)相同148與37最大公約數(shù)為37所以8251與6105最大公約數(shù)為37問題4.根據(jù)問題3求兩個數(shù)最大公約數(shù)的方法，試設計一個求兩個正整數(shù)m,n(mn)最大公約數(shù)的算法，并畫出程序框圖表示.研探新知算法步驟：第一步，給定兩個正整數(shù)m,n（mn).第二步，計算m除以n所得的余數(shù)r.第三步，若r=0,則m,n的最大公約數(shù)等于n;否則，執(zhí)行第四步.第四步，m=n,n=r.返回第二步研探新知 程序框圖： 輾轉相除法:對于給定的兩個正整數(shù)m

3、,n（mn)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)與較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù).研探新知更相減損術:更相減損術求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。問題5.求較大兩數(shù)的最大公約數(shù)?？梢杂贸ㄞD化為求

4、較小兩數(shù)的最大公約數(shù)外，還可以用什么方法？課堂練習1. 用更相減損術求378與90的最大公約數(shù)并用輾轉相除法驗證結果. 更相減損術 輾轉相除法 解：378與90都是偶數(shù) 189-45=144 144-45=99 99-45=54 54-45=9 45-9=36 36-9=27 27-9=18 18-9=9 所以3378與90的最大公約數(shù)為18小結輾轉相除法與更相減損術的區(qū)別與聯(lián)系名稱輾轉相除法 更相減損術區(qū)別 以除法為主相除，余數(shù)為0時得結果兩個數(shù)字大小區(qū)別較大時計算次數(shù)相對較少以減法為主相減，減數(shù)與差相等得結果兩個數(shù)字大小區(qū)別較大時計算次數(shù)相對較多相減前要做是否都是偶數(shù)的判斷聯(lián)系都是求最大公約數(shù)的方