【高中數(shù)學(xué)必修三】1.3.1輾轉(zhuǎn)相除法與更相減損術(shù)

1、1.3.1 案例案例1、輾轉(zhuǎn)相除法與更相減損術(shù)、輾轉(zhuǎn)相除法與更相減損術(shù) 回顧算法的三種表示方法：回顧算法的三種表示方法：（1）、自然語言）、自然語言（2）、程序框圖）、程序框圖（3）、程序語言）、程序語言（三種邏輯結(jié)構(gòu)）（三種邏輯結(jié)構(gòu)）（五種基本語句）（五種基本語句）復(fù)習(xí)引入復(fù)習(xí)引入 思考：思考：小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法？小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法？ 先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來的商是互為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來. .解：解：2 1 8 2 4 用公有質(zhì)因數(shù)用公有質(zhì)因

2、數(shù)2除，除， 3 9 1 2 用公有質(zhì)因數(shù)用公有質(zhì)因數(shù)3除，除， 3 4 3和和4互質(zhì)不除了?；ベ|(zhì)不除了。 得：得：18和和24最大公約數(shù)是：最大公約數(shù)是：236 問題：如何求問題：如何求8251與與6105的最大公約數(shù)？的最大公約數(shù)？( 8251 ,6105 )=? 例、求例、求18與與24的最大公約數(shù)：的最大公約數(shù)：用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過程的最大公約數(shù)的過程 第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù) 8251=61051+2146結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的公約數(shù)就是61

3、05和和2146的公約數(shù)，求的公約數(shù)，求8251和和6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公約數(shù)就可以了。的公約數(shù)就可以了。 (8251 , 6105 )=(6105 , 2146 ) 第二步第二步 對對6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法 6105=21462 + 1813 輾轉(zhuǎn)相除法（歐幾里得算法）輾轉(zhuǎn)相除法（歐幾里得算法） 同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 (8251 , 6105 )=(6105 , 2146 ) =(2146 ,1813)以此類推以此類推完整

4、的過程完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù)225=1351+90135=901+4590=452顯然顯然37是是148和和37的最大公約的最大公約數(shù)，也就是數(shù)，也就是8251和和6105的最的最大公約數(shù)大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是225和和135的最大公約數(shù)的最大公約數(shù) 思考思考1：從上面的兩個例子可以看出計：從上面的兩個例子可以看出計算的

5、規(guī)律是什么？算的規(guī)律是什么？ 第一步：用大數(shù)除以小數(shù)第一步：用大數(shù)除以小數(shù)第二步：第二步：除數(shù)除數(shù)變成變成被除數(shù)被除數(shù)，余數(shù)余數(shù)變成變成除數(shù)除數(shù)第三步：重復(fù)第一步，直到第三步：重復(fù)第一步，直到余數(shù)為余數(shù)為0時的時的 除數(shù)除數(shù)即為最大公約數(shù)即為最大公約數(shù)輾轉(zhuǎn)相除法（歐幾里得算法）輾轉(zhuǎn)相除法（歐幾里得算法） 所謂輾轉(zhuǎn)相除法所謂輾轉(zhuǎn)相除法, ,就是對于給定的兩個數(shù)就是對于給定的兩個數(shù), ,用用較大的數(shù)除以較小的數(shù)較大的數(shù)除以較小的數(shù). .若余數(shù)不為零若余數(shù)不為零, ,則將則將除數(shù)除數(shù)變成變成被除數(shù)被除數(shù)，余數(shù)余數(shù)變成變成除數(shù)除數(shù), ,繼續(xù)上面的除法繼續(xù)上面的除法, ,直直到余數(shù)為到余數(shù)為0,0,則這

6、時的除數(shù)就是原來兩個數(shù)的最大則這時的除數(shù)就是原來兩個數(shù)的最大公約數(shù)公約數(shù). .練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與與20723的最大公約數(shù)的最大公約數(shù)（答案：（答案：53） 輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。這實際上是一個循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程r=m MOD nm =

7、nn = rr=0?是是否否思考思考3：你能把輾轉(zhuǎn)相除法編成一個計算機(jī)程序嗎？你能把輾轉(zhuǎn)相除法編成一個計算機(jī)程序嗎？算法步驟：算法步驟：第一步：輸入兩個正整數(shù)第一步：輸入兩個正整數(shù)m,n(mn).第二步：計算第二步：計算m除以除以n所得的余數(shù)所得的余數(shù)r.第三步：第三步：m=n,n=r.第四步：若第四步：若r0,則則m,n的最大公約數(shù)等于的最大公約數(shù)等于m； 否則轉(zhuǎn)到第二步否則轉(zhuǎn)到第二步. 第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)m.r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r開始開始輸入輸入m,nm,nr=0?r=0? 輸出輸出m m結(jié)束結(jié)束程序框圖：程序框圖：I

8、NPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND程序：程序：課后必做作業(yè)：課后必做作業(yè)： 請同學(xué)們課后閱讀教材，理解并掌握輾轉(zhuǎn)相除法的請同學(xué)們課后閱讀教材，理解并掌握輾轉(zhuǎn)相除法的程序設(shè)計程序設(shè)計更相減損術(shù)更相減損術(shù)我國早期也有解決求最大公約數(shù)問題的算法，就是我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)更相減損術(shù)。更相減損術(shù)求最大公約數(shù)的步驟如下：更相減損術(shù)求最大公約數(shù)的步驟如下： 可半者半之，不可半者，副置分母、子之?dāng)?shù)，可半者半之，不可半者，副置分母、子之?dāng)?shù)， 以少減多，更相減損，求其等也，以等數(shù)約之。以少減多，更相減損，求其等

9、也，以等數(shù)約之。翻譯出來為：翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用 2 2約簡；若不是，執(zhí)行第二步。約簡；若不是，執(zhí)行第二步。第二步：以較大的數(shù)減去較小的數(shù)，接著把所第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與得的差與較小的數(shù)較小的數(shù) 比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù) 相等為止，則相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘 積積就是所求的最大公約數(shù)。就是所求的最大公約數(shù)。更相減損術(shù)更相減損術(shù)第一步第一

10、步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2 2約簡；約簡；若不是，執(zhí)行第二步。若不是，執(zhí)行第二步。第二步第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。就是所求的最大公約數(shù)。例例 用更相減損術(shù)求用更相減損術(shù)求98與與63的最大公約數(shù)的最大公約數(shù)解：由于兩個數(shù)不都

11、是偶數(shù)，把解：由于兩個數(shù)不都是偶數(shù)，把98和和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 1477所以，所以，98和和63的最大公約數(shù)等于的最大公約數(shù)等于7 練習(xí)：用更相減損術(shù)求兩個正數(shù)練習(xí)：用更相減損術(shù)求兩個正數(shù)84與與72的最大公約數(shù)。的最大公約數(shù)。（答案：（答案：12）986335633528352872872121714（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)比較大時更適合用輾轉(zhuǎn)相除法。次

12、數(shù)相對較少，特別當(dāng)兩個數(shù)比較大時更適合用輾轉(zhuǎn)相除法。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為余數(shù)為0而得到，而更相減損術(shù)則以減數(shù)與差相等而得到的。而得到，而更相減損術(shù)則以減數(shù)與差相等而得到的。輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別用更相減損術(shù)求兩個正整用更相減損術(shù)求兩個正整數(shù)數(shù)m，n的最大公約數(shù)的最大公約數(shù)算法步驟算法步驟(1)輸入兩個整數(shù)輸入兩個整數(shù)m，n(2)若若mn,轉(zhuǎn)到轉(zhuǎn)到(3),否則轉(zhuǎn)到否則轉(zhuǎn)到(4)(3)若若mn,則則m=m-n,否則否則n=n-m,轉(zhuǎn)到轉(zhuǎn)到(2)(4)輸出最大公約數(shù)輸出最大公約數(shù)n

13、用更相減損術(shù)求兩個正整用更相減損術(shù)求兩個正整數(shù)數(shù)m，n的最大公約數(shù)的最大公約數(shù)程序框圖程序框圖輸入輸入m,n開始開始mn？mn？m=m-nn=n-m輸出輸出n結(jié)束結(jié)束NYYN算法步驟算法步驟(1)輸入兩個整數(shù)輸入兩個整數(shù)m，n(2)若若mn,轉(zhuǎn)到轉(zhuǎn)到(3),否則轉(zhuǎn)到否則轉(zhuǎn)到(4)(3)若若mn,則則m=m-n,否則否則n=n-m,轉(zhuǎn)到轉(zhuǎn)到(2)(4)輸出最大公約數(shù)輸出最大公約數(shù)n更相減損術(shù)更相減損術(shù)的算法程序：的算法程序：INPUT “m,n=”;m,nWHILE mn IF mn THEN m=m-n ELSE n=n-m END IFWENDPRINT nEND程程 序序程序框圖程序框圖輸入輸入m,n開始開始mn？mn？m=m-nn=n-m輸出輸出n結(jié)束結(jié)束NYYN算法步驟算法步驟(1)輸入兩個整數(shù)輸入兩個整數(shù)m，n(2)若若mn,轉(zhuǎn)到轉(zhuǎn)到(3),否則轉(zhuǎn)到否則轉(zhuǎn)到(4)(3)若若mn,則則m=m-n,否則否則n=n-m,轉(zhuǎn)到轉(zhuǎn)到(2)(4)輸出最大公約數(shù)輸出最大公約數(shù)n（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算