1、1.3.1 案例1、輾轉相除法與更相減損術,回顧算法的三種表示方法：,（1）、自然語言,（2）、程序框圖,（3）、程序語言,（三種邏輯結構）,（五種基本語句）,復習引入,思考：,小學學過的求兩個數(shù)最大公約數(shù)的方法？,先用兩個公有的質因數(shù)連續(xù)去除，一直除到所得的商是互為質數(shù)為止，然后把所有的除數(shù)連乘起來.,問題：如何求8251與6105的最大公約數(shù)？ ( 8251 ,6105 )=?,例、求18與24的最大公約數(shù)：,用輾轉相除法求8251和6105的最大公約數(shù)的過程,第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù) 8251=61051+2146,結論： 8251和6105的公約數(shù)就是6105

2、和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。 (8251 , 6105 )=(6105 , 2146 ),第二步 對6105和2146重復第一步的做法 6105=21462 + 1813, 輾轉相除法（歐幾里得算法） ,同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。 (8251 , 6105 )=(6105 , 2146 ) =(2146 ,1813),以此類推,完整的過程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37

3、,148=374+0,例2 用輾轉相除法求225和135的最大公約數(shù),225=1351+90,135=901+45,90=452,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),思考1：從上面的兩個例子可以看出計算的規(guī)律是什么？,第一步：用大數(shù)除以小數(shù),第二步：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),第三步：重復第一步，直到余數(shù)為0時的 除數(shù)即為最大公約數(shù),輾轉相除法（歐幾里得算法）,所謂輾轉相除法,就是對于給定的兩個數(shù),用較大的數(shù)除以較小的數(shù).若余數(shù)不為零,則將除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),繼續(xù)上面的除法,直

4、到余數(shù)為0,則這時的除數(shù)就是原來兩個數(shù)的最大公約數(shù).,練習：利用輾轉相除法求兩數(shù)4081與20723的最大公約數(shù),（答案：53）,輾轉相除法是一個反復執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結構。,m = n q r,用程序框圖表示出右邊的過程,r=m MOD n,m = n,n = r,r=0?,是,否,思考2：輾轉相除法中的關鍵步驟是哪種邏輯結構？,思考3：你能把輾轉相除法編成一個計算機程序嗎？,算法步驟：,第一步：輸入兩個正整數(shù)m,n(mn). 第二步：計算m除以n所得的余數(shù)r. 第三步：m=n,n=r. 第四步：若r0,則m,n的最大公約數(shù)等于m； 否則轉到第二步. 第五步：輸

5、出最大公約數(shù)m.,程序框圖：,程序：,課后必做作業(yè)： 請同學們課后閱讀教材，理解并掌握輾轉相除法的程序設計,更相減損術,我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術。 更相減損術求最大公約數(shù)的步驟如下： 可半者半之，不可半者，副置分母、子之數(shù)， 以少減多，更相減損，求其等也，以等數(shù)約之。 翻譯出來為： 第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用 2約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù) 比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù) 相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘 積就是所求的最大公約數(shù)。,更相減損術,第

6、一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡； 若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較， 并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù) （等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。,例 用更相減損術求98與63的最大公約數(shù),解：由于兩個數(shù)不都是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減,1477,所以，98和63的最大公約數(shù)等于7,練習：用更相減損術求兩個正數(shù)84與72的最大公約數(shù)。,（答案：12）,986335,633528,35287,28721,21714,（1）都是求最大公約數(shù)的方法，計算上輾轉相除法以除法 為主，更相減損術以減法為主，計算次數(shù)上輾轉相除法計算 次數(shù)相對較少，特別當兩個數(shù)比較大時更適合用輾轉相除法。,（2）從結果體現(xiàn)形式來看，輾轉相除法體現(xiàn)結果是以相除 余數(shù)為0而得到，而更相減損術則以減數(shù)與差相等而得到的。,輾轉相除法與更相減損術的區(qū)別,用更相減損術求兩個正整數(shù)m，n的最大公約數(shù),用更相減損術求兩個正整數(shù)m，n的最大公約數(shù),程序框圖,更相減損術的算法程序：,程序框圖,（1）都是求最大公約數(shù)的方法，計算上輾轉相除法以除法 為主，更相減損術以減法為主，計算次數(shù)上輾轉相