湖南師大附中高中數(shù)學新人教A版必修3課件：131輾轉相除法與更相減損術

1、1.3 1.3 算法案例算法案例 第一課時第一課時 問題提出問題提出t57301p2 1. 1.研究一個實際問題的算法，主要從研究一個實際問題的算法，主要從算法步驟、程序框圖和編寫程序三方面算法步驟、程序框圖和編寫程序三方面展開展開. .在程序框圖中算法的基本邏輯結構在程序框圖中算法的基本邏輯結構有哪幾種？在程序設計中基本的算法語有哪幾種？在程序設計中基本的算法語句有哪幾種？句有哪幾種？ 2.“ 2.“求兩個正整數(shù)的最大公約數(shù)求兩個正整數(shù)的最大公約數(shù)”是數(shù)學中的一個基礎性問題，它有各種是數(shù)學中的一個基礎性問題，它有各種解決辦法，我們以此為案例，對該問題解決辦法，我們以此為案例，對該問題的算法作

2、一些探究的算法作一些探究. .知識探究（一）知識探究（一）: :輾轉相除法輾轉相除法思考思考1:1:1818與與3030的最大公約數(shù)是多少？你的最大公約數(shù)是多少？你是怎樣得到的？是怎樣得到的？ 先用兩個數(shù)公有的質因數(shù)連續(xù)去除，先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是互質數(shù)為止，然一直除到所得的商是互質數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公后把所有的除數(shù)連乘起來即為最大公約數(shù)約數(shù). . 思考思考2:2:對于對于82518251與與61056105這兩個數(shù)，由于這兩個數(shù)，由于其公有的質因數(shù)較大，利用上述方法求其公有的質因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難最大公約數(shù)就比較困難.

3、 .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩個數(shù)的公約數(shù)和這兩個數(shù)的公約數(shù)和61056105與與21462146的公約的公約數(shù)有什么關系？數(shù)有什么關系？ 思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公的公約數(shù)相等約數(shù)相等. .重復上述操作，你能得到重復上述操作，你能得到82518251與與61056105這兩個數(shù)的最大公約數(shù)嗎？這兩個數(shù)的最大公約數(shù)嗎？21462146=

4、 =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，思考思考4:4:上述求兩個正整數(shù)的最大公約數(shù)上述求兩個正整數(shù)的最大公約數(shù)的方法稱為的方法稱為輾轉相除法輾轉相除法或或歐幾里得算法歐幾里得算法. .一般地，用輾轉相除法求兩個正整數(shù)一般地，用輾轉相除法求兩個正整數(shù)m m，n n的最大公約數(shù)，可以用什么邏輯結構來的最大公約數(shù)，可以用什么邏輯

5、結構來構造算法？其算法步驟如何設計？構造算法？其算法步驟如何設計？ 第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn(mn).n).第二步，計算第二步，計算m m除以除以n n所得的余數(shù)所得的余數(shù)r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等的最大公約數(shù)等 于于m m；否則，返回第二步；否則，返回第二步. . 思考思考5:5:該算法的程序框圖如何表示？該算法的程序框圖如何表示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結束結束否否思考思考6:6:該程序框圖對應

6、的程序如何表述？該程序框圖對應的程序如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結束結束否否思考思考7:7:如果用當型循環(huán)結構構造算法，如果用當型循環(huán)結構構造算法，則用輾轉相除法求兩個正整數(shù)則用輾轉相除法求兩個正整數(shù)m m，n n的最的最大公約數(shù)的程序框圖和程序分別如何表大公約數(shù)的程序框圖和程序分別如何表示？示？開始開始輸入輸入m，n求求m除以除以n的

7、余數(shù)的余數(shù)rm=nn0？否否輸出輸出m結束結束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND知識探究（二）知識探究（二）: :更相減損術更相減損術 思考思考1:1:設兩個正整數(shù)設兩個正整數(shù)m mn n，若，若m-n=km-n=k，則，則m m與與n n的最大公約數(shù)和的最大公約數(shù)和n n與與k k的最大公約數(shù)的最大公約數(shù)相等相等. .反復利用這個原理，可求得反復利用這個原理，可求得9898與與6363的最大公約數(shù)為多少？的最大公約數(shù)為多少？98-63=

8、3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，思考思考2:2:上述求兩個正整數(shù)的最大公約數(shù)上述求兩個正整數(shù)的最大公約數(shù)的方法稱為的方法稱為更相減損術更相減損術. .一般地，用更相一般地，用更相減損術求兩個正整數(shù)減損術求兩個正整數(shù)m m，n n的最大公約數(shù)，的最大公約數(shù)，可以用什么邏輯結構來構造算法？其算可以用什么邏輯結構來構造算法？其算法步驟如何設計？法步驟如何設計？第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn).n(mn). 第二步，計算第二步，計算

9、m-nm-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于 m m；否則，返回第二步；否則，返回第二步. . 思考思考3:3:該算法的程序框圖如何表示？該算法的程序框圖如何表示？開始開始輸入輸入m，nnk？m=n是是輸出輸出m結束結束mn？k=m- -n是是否否n=km=k否否思考思考4:4:該程序框圖對應的程序如何表述？該程序框圖對應的程序如何表述？INPUT mINPUT m，n nWHILE

10、WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND開始開始輸入輸入m，nnk？m=n是是輸出輸出m結束結束mn？k=m- -n是是否否n=km=k否否“更相減損術更相減損術”在中國古代數(shù)學專著在中國古代數(shù)學專著九章算術九章算術中記述為：中記述為： 可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之以等數(shù)約之. . 理論遷移理論遷移

11、例例1 1 分別用輾轉相除法和更相減損分別用輾轉相除法和更相減損術求術求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉相除法：輾轉相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.更相減損術更相減損術:168-93=75:168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12，

12、12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3. 例例2 2 求求325325，130130，270270三個數(shù)的最大三個數(shù)的最大公約數(shù)公約數(shù). . 因為因為325=130325=1302+652+65，130=65130=652 2，所以所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65.65. 因為因為270=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，270270三個數(shù)的最大公約三個數(shù)的最大公約數(shù)是數(shù)是5.5. 1. 1.輾轉相除法，就是對于給定的兩個正整輾轉相除法，就是對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構成新的一對數(shù)，零，則將余數(shù)和較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時的較小的數(shù)即為原來兩個數(shù)的最大公約這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù)數(shù). . 小結作業(yè)小結作業(yè) 2. 2. 更相減損術，就是對于給定的兩個正更相減損術，就