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

1、會計(jì)學(xué)1案例案例(n l)輾轉(zhuǎn)相除輾轉(zhuǎn)相除第一頁，共19頁。3 59 15 問題問題11：在小學(xué)：在小學(xué)(xioxu)(xioxu)，我們已經(jīng)學(xué)過求最大公約數(shù)的，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出知識，你能求出1818與與3030的最大公約數(shù)嗎？的最大公約數(shù)嗎？18 30231818和和3030的最大公約數(shù)是的最大公約數(shù)是2 23=6.3=6.先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除除(q ch),(q ch),一直除到所得的商一直除到所得的商是互質(zhì)數(shù)為止是互質(zhì)數(shù)為止, ,然后把所有的除然后把所有的除數(shù)連乘起來數(shù)連乘起來. . 問題問題2:2:我們都是利用找公約數(shù)的方法

2、來求最大公約數(shù)，如果我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣們又應(yīng)該怎樣(znyng)(znyng)求它們的最大公約數(shù)？比如求求它們的最大公約數(shù)？比如求82518251與與61056105的最大公約數(shù)的最大公約數(shù)? ? 第1頁/共18頁第二頁，共19頁。1.1.輾轉(zhuǎn)輾轉(zhuǎn)(zhnzhun)(zhnzhun)相相除法除法: :例例1 1 求兩個(gè)求兩個(gè)(lin )(lin )正數(shù)正數(shù)82518251和和61056105的最大公約數(shù)。的最大公約數(shù)。分析：分析：82518251與

3、與61056105兩數(shù)都比較大，而且沒有兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們明顯的公約數(shù)，如能把它們(t men)(t men)都變小一點(diǎn)，都變小一點(diǎn)，根據(jù)已有的知識即可求出最大公約數(shù)根據(jù)已有的知識即可求出最大公約數(shù). .解：解：82518251610561051 121462146顯然顯然82518251與與61056105的最大公約數(shù)也必是的最大公約數(shù)也必是21462146的約數(shù)，同樣的約數(shù)，同樣61056105與與21462146的公約數(shù)也必是的公約數(shù)也必是82518251的約數(shù)，所以的約數(shù)，所以82518251與與61056105的最大公的最大公約數(shù)也是約數(shù)也是6105610

4、5與與21462146的最大公約數(shù)。的最大公約數(shù)。第2頁/共18頁第三頁，共19頁。例例1 1 求兩個(gè)求兩個(gè)(lin )(lin )正數(shù)正數(shù)82518251和和61056105的最大的最大公約數(shù)。公約數(shù)。解：解：82518251610561051 12146;2146;61056105214621462 21813;1813;21462146181318131 1333;333;181318133333335 5148;148;3333331481482 237;3740.0.則則3737為為82518251與與61056105的最大公約數(shù)。的最大公約數(shù)。以上我們求最

5、大公約數(shù)的方法以上我們求最大公約數(shù)的方法(fngf)(fngf)就就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前德在公元前300300年左右首先提出的。年左右首先提出的。 1.1.輾轉(zhuǎn)輾轉(zhuǎn)(zhnzhun)(zhnzhun)相除相除法法: :第3頁/共18頁第四頁，共19頁。觀察觀察(gunch)用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過程的最大公約數(shù)的過程 第一步第一步 用兩數(shù)中較大用兩數(shù)中較大(jio d)的數(shù)除以較小的數(shù)，求得商的數(shù)除以較小的數(shù)，求得商和余數(shù)和余數(shù)8251=61051+2146結(jié)論結(jié)論(jiln)

6、： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約的公約數(shù)，求數(shù)，求8251和和6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公的公約數(shù)就可以了。約數(shù)就可以了。第二步第二步 對對6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約的最大公約數(shù)。數(shù)。 1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: :第4頁/共18頁第五頁，共19頁。完整完整(wnzhng)(wnzhng)的過程的過程8251=61051+2146 6105=21462+18

7、13 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 2 用輾轉(zhuǎn)用輾轉(zhuǎn)(zhnzhun)(zhnzhun)相相除法求除法求225225和和135135的最大公的最大公約數(shù)約數(shù)225=1351+90135=901+4590=452顯然顯然(xinrn)37(xinrn)37是是148148和和3737的最的最大公約數(shù)，也就是大公約數(shù)，也就是82518251和和61056105的的最大公約數(shù)最大公約數(shù) 顯然顯然4545是是9090和和4545的最大公約數(shù)的最大公約數(shù)，也就是，也就是225225和和135135的最大公約的最大公約數(shù)數(shù) 第5頁/共

8、18頁第六頁，共19頁。S1：給定：給定(i dn)兩個(gè)正整數(shù)兩個(gè)正整數(shù)m,nS2：用大數(shù)：用大數(shù)(d sh)除以小數(shù)，計(jì)算除以小數(shù)，計(jì)算m除除以以n所得的余數(shù)；所得的余數(shù)；S3：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)，即：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)，即 m=n , n=r；S4：重復(fù)：重復(fù)S2,直到余數(shù)為直到余數(shù)為0，即若，即若r=0，則，則m, n 的最大公約數(shù)為的最大公約數(shù)為m，否則返回，否則返回S2.第6頁/共18頁第七頁，共19頁。 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法(chf)(chf)是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0 0停止的步驟，這實(shí)際上是一個(gè)循停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)

9、。環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊用程序框圖表示出右邊(yu bian)的過程的過程r=m MOD nm = nn = rr=0?是否第7頁/共18頁第八頁，共19頁。r=m MOD nm = nn = rr=0?是否開始 輸入兩個(gè)正數(shù)m,n 輸出m,n結(jié)束INPUT m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND第8頁/共18頁第九頁，共19頁。(53)(53)第9頁/共18頁第

10、十頁，共19頁。第10頁/共18頁第十一頁，共19頁。 輸入兩個(gè)正數(shù)輸入兩個(gè)正數(shù)m,n否否開始開始r=m MOD nr0?輸出輸出n結(jié)束結(jié)束m=nn=r是是INPUT m,nr=m MOD nWHILE r0 m=nn=rr=m MOD n WENDPRINT nEND第11頁/共18頁第十二頁，共19頁。算理：可半者半之，不可半者，副置分母算理：可半者半之，不可半者，副置分母(fnm)、子之?dāng)?shù)、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個(gè)第一步：任意給定兩個(gè)(lin )(lin )正整數(shù)；判斷他們是否都正整數(shù)；判斷他們是否

11、都是偶數(shù)。若是，則用是偶數(shù)。若是，則用2 2約簡；若不是則執(zhí)行第二步。約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較(bjio)(bjio)，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。2.2.更相減損法更相減損法九章算術(shù)九章算術(shù)第12頁/共18頁第十三頁，共19頁。例例3 用更相減損用更相減損(jin sn)術(shù)求術(shù)求98與與63的最大公約數(shù)的最大公約數(shù)解：由于解

12、：由于63不是偶數(shù)，把不是偶數(shù)，把98和和63以大數(shù)以大數(shù)(d sh)減小數(shù)，并輾轉(zhuǎn)相減減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721217141477所以所以(suy)，98和和63的最大公約數(shù)等于的最大公約數(shù)等于7 第13頁/共18頁第十四頁，共19頁。練習(xí)練習(xí)3 3：分別：分別(fnbi)(fnbi)用輾轉(zhuǎn)相除法和更相減用輾轉(zhuǎn)相除法和更相減損術(shù)求損術(shù)求204204與與8585的最大公約數(shù)。的最大公約數(shù)。 解解：20485234853421734172204 85 119119 85 3485 34 5151 34 1734 17 17輾轉(zhuǎn)輾轉(zhuǎn)(zhnzhun)(zhnz

13、hun)相除法相除法更相減損更相減損(jin sn)(jin sn)法法第14頁/共18頁第十五頁，共19頁。 思考：把更相減損術(shù)與輾轉(zhuǎn)相除法相比較，你有思考：把更相減損術(shù)與輾轉(zhuǎn)相除法相比較，你有什么什么(shn me)發(fā)現(xiàn)？發(fā)現(xiàn)？怎樣根據(jù)更相減損術(shù)設(shè)計(jì)怎樣根據(jù)更相減損術(shù)設(shè)計(jì)(shj)程序，求兩個(gè)正整程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？數(shù)的最大公約數(shù)嗎？第15頁/共18頁第十六頁，共19頁。開始開始輸入輸入m,n(mn)k=0m,n為偶數(shù)為偶數(shù)?k=k+1m=m/2n=n/2d=m-ndn?dn?否否m=nn=dd=m-nm=d是是輸出輸出2k *d結(jié)束結(jié)束是是否否否否是是第16頁/共18頁第十七頁，共19頁。WHILE dn IF dn then m=d ELSE m=n n=d END IF d=m-nWEND d=2k*dPRINT dEnd INPUT “m,n=“;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m- n第17頁/共18頁第十八頁，共19頁。NoImage內(nèi)容(nirng)總結(jié)會計(jì)學(xué)。