輾轉(zhuǎn)相除法好PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 輾轉(zhuǎn)相除法好輾轉(zhuǎn)相除法好 1、求兩個(gè)正整數(shù)的最大公約數(shù) （1）求25和35的最大公約數(shù) （2）求49和63的最大公約數(shù) 2、求8251和6105的最大公約數(shù) 25（1） 5 5 35 7 49（2） 7 7 63 9 所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7 第1頁(yè)/共23頁(yè) 輾轉(zhuǎn)相除法（歐幾里得算法） 觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過(guò)程 第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù) 8251=61051+2146 結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和 6105的最大公約數(shù)，只要求出6105和

2、2146的公約數(shù)就可以了。 第二步 對(duì)6105和2146重復(fù)第一步的做法 6105=21462+1813 同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。 第2頁(yè)/共23頁(yè) 完整的過(guò)程 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 例2 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù) 225=1351+90 135=901+45 90=452 顯然37是148和37的最大公約 數(shù)，也就是8251和6105的最 大公約數(shù) 顯然45是90和45的最大公約數(shù)，也就是

3、 225和135的最大公約數(shù) 第3頁(yè)/共23頁(yè) S1：給定兩個(gè)正整數(shù)m,n S2：用大數(shù)除以小數(shù)，計(jì)算m除以n所得的余數(shù)； S3：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)，即 m=n , n=r S4：重復(fù)S2,直到余數(shù)為0，即 若r=0，則m, n 的最大公約數(shù)為m，否則返回S2 第4頁(yè)/共23頁(yè) 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是 一個(gè)循環(huán)結(jié)構(gòu)。 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 m = n q r 用程序框圖表示出右邊的過(guò)程 r=m MOD n

4、 m = n n = r r=0? 是 否 第5頁(yè)/共23頁(yè) r=m MOD n m = n n = r r=0? 是 否 開(kāi)始 輸入兩個(gè)正數(shù)m,n 輸出m 結(jié)束 INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 第6頁(yè)/共23頁(yè) 第7頁(yè)/共23頁(yè) 開(kāi)始 輸入m，n 求m除以n的余數(shù)r m=n n0？ 否 輸出m 結(jié)束 是 n=r INPUT m，n WHILE n0 r=m MODn m=n n=r WEND PRINT m END 第8頁(yè)/共23頁(yè) (53) 第9頁(yè)/共23頁(yè) 九章算術(shù)更相減損術(shù) 算理：可半者半之，不可半者，

5、副置分母、子之?dāng)?shù)，以少減多，更相減損 ，求其等也，以等數(shù)約之。 第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若 不是則執(zhí)行第二步。 第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大 數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù) 就是所求的最大公約數(shù)。 第10頁(yè)/共23頁(yè) 例3 用更相減損術(shù)求98與63的最大公約數(shù) 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 986335 633528 35287 28721 21714 1477 所以，98和63的最大公約數(shù)等于7 第11頁(yè)/共23頁(yè) 練習(xí)3：分別用輾轉(zhuǎn)相除法和更相減損

6、術(shù)求204與85的最大公約數(shù) 。 解： 20485 234 8534 2 17 3417 2 204 85 119 119 85 34 85 34 51 51 34 17 34 17 17 第12頁(yè)/共23頁(yè) 第13頁(yè)/共23頁(yè) 開(kāi)始 輸m,n(mn) K=0 M,n為偶數(shù) ? K=k+1 M=m/2 N=n/2 dn ? dn? 否 M=n N=d d=m-n M=d 是 輸出2k *d 結(jié)束 是 否 否 是 d=m-n 第14頁(yè)/共23頁(yè) INPUT “m,n=“;m,n IF mn THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD

7、 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n While dn IF dn then m=d ELSE m=n n=d End if d=m-n Wend d=2k*d PRINT d End 第15頁(yè)/共23頁(yè) 例3 用更相減損術(shù)求98與63的最大公約數(shù) 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù) ，并輾轉(zhuǎn)相減 986335 633528 35287 28721 21721 1477 所以，98和63的最大公約數(shù)等于7 用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù) 練習(xí)： 先約簡(jiǎn)，再求21與18的最大公約數(shù),然后乘 以兩次約簡(jiǎn)的質(zhì)因數(shù)4 第16頁(yè)/共23頁(yè) 理論遷

8、移 例1 分別用輾轉(zhuǎn)相除法和更相減損 術(shù)求168與93的最大公約數(shù).最小公倍數(shù)? 輾轉(zhuǎn)相除法：168=931+75， 93=751+18， 75=184+3， 18=36. 第17頁(yè)/共23頁(yè) 更相減損術(shù):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.第18頁(yè)/共23頁(yè) 例2、求325、130、270這三個(gè)數(shù)的最大公 約數(shù)。 思路分析：求三個(gè)數(shù)的最大公約數(shù)可以先求出兩個(gè) 數(shù)的最大公約數(shù)，第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約 數(shù)的最大公約數(shù)即為所求。 第19頁(yè)/共23頁(yè) 例2 求325，130，270三個(gè)數(shù)的最大 公約數(shù). 因?yàn)?25=1302+65，130=652， 所以325與130的最大公約數(shù)是65. 因?yàn)?70=654+10，65=106+5， 10=52，所以65與270最大公約數(shù)是5. 故325，130，270三個(gè)數(shù)的最大公約 數(shù)是5. 第20頁(yè)/共23頁(yè) 3.輾轉(zhuǎn)相除法與更相減損術(shù)的比較: （1）都是求最大公約數(shù)的方法，計(jì)算上 輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為 主;計(jì)算次數(shù)上輾轉(zhuǎn)相除