輾轉(zhuǎn)相除法與更相減損術PPT學習教案

1、會計學1輾轉(zhuǎn)相除法與更相減損術輾轉(zhuǎn)相除法與更相減損術自學教材自學教材P34-P37 解決下列問解決下列問題題一、能用輾轉(zhuǎn)相除法和更相減損術求兩個正整數(shù)的最大公約數(shù)一、能用輾轉(zhuǎn)相除法和更相減損術求兩個正整數(shù)的最大公約數(shù).二、二、學海導航學海導航 P25-P26 “雙層練習雙層練習” “范例剖析范例剖析”三、教材三、教材 P45 第第1題題第2頁/共26頁例：求下面兩個正整數(shù)的最大公約例：求下面兩個正整數(shù)的最大公約數(shù)：數(shù)：（1）求）求25和和35的最大公約數(shù)的最大公約數(shù)（2）求）求49和和63的最大公約數(shù)的最大公約數(shù)25（1） 5535749（2） 77639所以，所以，25和和35的最大公約數(shù)為

2、的最大公約數(shù)為5所以，所以，49和和63的最大公約數(shù)為的最大公約數(shù)為7思考：除了用這種方法外還有沒有其它方法？思考：除了用這種方法外還有沒有其它方法？例：如何算出例：如何算出8251和和6105的最大公約數(shù)？的最大公約數(shù)？第3頁/共26頁一、輾轉(zhuǎn)相除法（歐幾里得算法）一、輾轉(zhuǎn)相除法（歐幾里得算法）1 1、定義：、定義： 所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)

3、被小數(shù)除盡,則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。第4頁/共26頁 2、步驟、步驟:（以求（以求8251和和6105的最大公約數(shù)的過程為例）的最大公約數(shù)的過程為例）第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(shù)，求8251和和6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公約數(shù)就可的公約數(shù)就可以了。以了。第二步第二步 對對6105和和2146重

4、復第一步的做法重復第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 第5頁/共26頁完整的過程完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例: 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù)225=1351+90135=901+4590=452顯然顯然37是是148和和37的最大的最大公約數(shù)，也就是公約數(shù)，也就是8251和和6105的最大公約數(shù)的最

5、大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，也的最大公約數(shù)，也就是就是225和和135的最大公約數(shù)的最大公約數(shù) 思考思考1：從上面的兩個例子中可以：從上面的兩個例子中可以看出計算的規(guī)律是什么？看出計算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)數(shù)S3：重復：重復S1，直到余數(shù)為，直到余數(shù)為0第6頁/共26頁 輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個反復執(zhí)行直到余數(shù)等于0才停止的步驟，這才停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)。實際上是一個循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813

6、 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是是否否第7頁/共26頁思考：思考：你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎？(1)、算法步驟：、算法步驟：第一步：輸入兩個正整數(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ù)第五

7、步：輸出最大公約數(shù)m.第8頁/共26頁開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否(2)(2)、程序框圖：、程序框圖：第9頁/共26頁開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否INPUT m，nDOr=m MODnm=nn=rLOOP UNTIL r=0PRINT mEND(3)(3)、程序：、程序：第10頁/共26頁思考思考:如果用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾如果用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)的的最大公約數(shù)的程序框圖和程序分別

8、如何表示？程序框圖和程序分別如何表示？第11頁/共26頁開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm =nn 0？否否輸出輸出m結(jié)束結(jié)束是是n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND第12頁/共26頁二、更相減損術二、更相減損術 可半者半之，不可半者，副置分母、子之數(shù)，以少減多，可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。更相減損，求其等也，以等數(shù)約之。第一步：第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用是，則用2約簡；若不是則執(zhí)行

9、第二步。約簡；若不是則執(zhí)行第二步。第二步：第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。（1 1）、）、九章算術九章算術中的更相減損術：中的更相減損術：1 1、背景介紹：、背景介紹：（2 2）、現(xiàn)代數(shù)學中的更相減損術：）、現(xiàn)代數(shù)學中的更相減損術：第13頁/共26頁2 2、定義：、定義： 所謂更相減損術，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后

10、將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。所謂更相減損術，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。第14頁/共26頁例例: 用更相減損術求用更相減損術求98與與63的最大公約數(shù)的最大公約數(shù).解：由于解：由于63不是偶數(shù)，把不是偶數(shù)，把98和和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減減 9863356335283528728721217211477所

11、以，所以，98和和63的最大公約數(shù)等于的最大公約數(shù)等于7 3、方法：、方法：第15頁/共26頁(1)、算法步驟、算法步驟第一步：輸入兩個正整數(shù)第一步：輸入兩個正整數(shù)a,b(ab);第二步：若第二步：若a不等于不等于b ,則執(zhí)行第三步；否則轉(zhuǎn)到第五步；則執(zhí)行第三步；否則轉(zhuǎn)到第五步；第三步：把第三步：把a-b的差賦予的差賦予r;第四步：如果第四步：如果br, 那么把那么把b賦給賦給a,把把r賦給賦給b;否則把否則把r賦給賦給a,執(zhí)行第二步；執(zhí)行第二步；第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)b.思考：你能根據(jù)更相減損術設計程序，求兩個正整思考：你能根據(jù)更相減損術設計程序，求兩個正整數(shù)的最大公約

12、數(shù)嗎？數(shù)的最大公約數(shù)嗎？第16頁/共26頁(2)(2)、程序框圖、程序框圖開始開始輸入輸入m，nnk？m=n是是輸出輸出m結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否第17頁/共26頁(3)(3)、程序、程序開始開始輸入輸入m，nnk？m=n是是輸 出輸 出m結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否INPUT m，nWHILE mnk=m-nIF nk THENm=nn=kELSEm=kEND IFWENDPRINT mEND第18頁/共26頁【例例1】分別用輾轉(zhuǎn)相除法和更相減損術求分別用輾轉(zhuǎn)相除法和更相減損術求168與與93的最大公約數(shù)的最大公約數(shù). 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除

13、法：168=93168=931+751+75， 93=75 93=751+181+18， 75=18 75=184+34+3， 18=3 18=36.6.第19頁/共26頁更相減損術更相減損術: :168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.第20頁/共26頁 因為因為325=1302+65，130=652，所以所以325與與130的最大公約數(shù)是的最大公約數(shù)是65. 因為因為270=654+10，65=106+5，10=52，所所以以65與與

14、270最大公約數(shù)是最大公約數(shù)是5. 故故325，130，270三個數(shù)的最大公約數(shù)是三個數(shù)的最大公約數(shù)是5.【例例2】求求325，130，270三個數(shù)的最大公約數(shù)三個數(shù)的最大公約數(shù). 第21頁/共26頁三、教材三、教材 P45 第第1題題第22頁/共26頁對自己說，你有什么收獲？對自己說，你有什么收獲？對同學說，你有什么提示？對同學說，你有什么提示？對老師說，你有什么疑惑？對老師說，你有什么疑惑？第23頁/共26頁比較輾轉(zhuǎn)相除法與更相減損術的區(qū)別比較輾轉(zhuǎn)相除法與更相減損術的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法