輾轉(zhuǎn)相除法與更相減損術(shù)新人教必修實(shí)用教案

1、會(huì)計(jì)學(xué)1輾轉(zhuǎn)相除法與更相減損術(shù)輾轉(zhuǎn)相除法與更相減損術(shù) 新人新人(xnrn)教必修教必修第一頁(yè)，共19頁(yè)。第1頁(yè)/共19頁(yè)第二頁(yè)，共19頁(yè)。知識(shí)知識(shí)(zh shi)探究（一）探究（一）:輾轉(zhuǎn)相輾轉(zhuǎn)相除法除法思考思考1:181:18與與3030的最大公約數(shù)是多少的最大公約數(shù)是多少(dusho)(dusho)？你是怎樣得到的？你是怎樣得到的？ 先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)所有的除數(shù)(ch sh)(ch sh)連乘起來(lái)即為最大連乘起來(lái)即為最大公約數(shù)公約數(shù). . 第2頁(yè)/共19頁(yè)第三頁(yè)，

2、共19頁(yè)。思考思考2:2:對(duì)于對(duì)于82518251與與61056105這兩個(gè)數(shù)，由于這兩個(gè)數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難最大公約數(shù)就比較困難. .注意注意(zh y)(zh y)到到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩個(gè)數(shù)的公約數(shù)和這兩個(gè)數(shù)的公約數(shù)和61056105與與21462146的的公約數(shù)有什么關(guān)系？公約數(shù)有什么關(guān)系？ 第3頁(yè)/共19頁(yè)第四頁(yè)，共19頁(yè)。思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，6

3、1056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公的公約數(shù)相等約數(shù)相等. .重復(fù)重復(fù)(chngf)(chngf)上述操作，你上述操作，你能得到能得到82518251與與61056105這兩個(gè)數(shù)的最大公約數(shù)這兩個(gè)數(shù)的最大公約數(shù)嗎？嗎？21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131

4、813，第4頁(yè)/共19頁(yè)第五頁(yè)，共19頁(yè)。思考思考4:4:上述求兩個(gè)正整數(shù)的最大公約數(shù)上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱(chēng)為輾轉(zhuǎn)相除法或歐幾里得算法的方法稱(chēng)為輾轉(zhuǎn)相除法或歐幾里得算法. .一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，可以用什么邏輯結(jié)的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何構(gòu)來(lái)構(gòu)造算法？其算法步驟如何(rh)(rh)設(shè)計(jì)？設(shè)計(jì)？ 第一步，給定第一步，給定(i dn)(i dn)兩個(gè)正整數(shù)兩個(gè)正整數(shù)m m，n(mn).n(mn).第二步，計(jì)算第二步，計(jì)算(j sun)m(j sun)m除以除以n n所得的余數(shù)所得的余

5、數(shù)r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等的最大公約數(shù)等 于于m m；否則，返回第二步；否則，返回第二步. . 第5頁(yè)/共19頁(yè)第六頁(yè)，共19頁(yè)。思考思考(sko)5:(sko)5:該算法的程序框圖如何該算法的程序框圖如何表示？表示？開(kāi)始開(kāi)始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否第6頁(yè)/共19頁(yè)第七頁(yè)，共19頁(yè)。思考思考6:6:該程序框圖對(duì)應(yīng)該程序框圖對(duì)應(yīng)(duyng)(duyng)的程序如的程序如何表述？何表述？INPUT mINPUT m，n nDODO

6、r=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND開(kāi)始開(kāi)始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否第7頁(yè)/共19頁(yè)第八頁(yè)，共19頁(yè)。思考思考7:7:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)的程序的最大公約數(shù)的程序(chngx)(chngx)框圖框圖和程序和程序(chngx)(chngx)分別如何表示？分別如何表示？第8頁(yè)/共19頁(yè)第九頁(yè)，共19頁(yè)。開(kāi)始

7、開(kāi)始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm =nn 0？否否輸出輸出m結(jié)束結(jié)束是是n=rINPUT mINPUT m，n nWHILE nWHILE n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND第9頁(yè)/共19頁(yè)第十頁(yè)，共19頁(yè)。知識(shí)探究知識(shí)探究(tnji)（二）（二）:更相減更相減損術(shù)損術(shù) 思考思考(sko)1:(sko)1:設(shè)兩個(gè)正整數(shù)設(shè)兩個(gè)正整數(shù)mnmn，若，若m-m-n=kn=k，則，則m m與與n n的最大公約數(shù)和的最大公約數(shù)和n n與與k k的最大的最大公約數(shù)相等公約數(shù)相等. .反復(fù)利用這個(gè)原理，可求

8、得反復(fù)利用這個(gè)原理，可求得9898與與6363的最大公約數(shù)為多少？的最大公約數(shù)為多少？98-63=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，第10頁(yè)/共19頁(yè)第十一頁(yè)，共19頁(yè)。思考思考2:2:上述求兩個(gè)正整數(shù)的最大公約數(shù)的方上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱(chēng)為更相減損術(shù)法稱(chēng)為更相減損術(shù). .一般地，用更相減損術(shù)一般地，用更相減損術(shù)求兩個(gè)正整數(shù)求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，可以用什的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)么邏輯結(jié)構(gòu)(jigu)(jigu)來(lái)構(gòu)造

9、算法？其算法步來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？驟如何設(shè)計(jì)？第一步，給定第一步，給定(i dn)(i dn)兩個(gè)正整數(shù)兩個(gè)正整數(shù)m m，n(mn). n(mn). 第二步，計(jì)算第二步，計(jì)算(j sun)m-n(j sun)m-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于 m m；否則，返回第二步；否則，返回第二步. . 第11頁(yè)/共19頁(yè)第十二頁(yè)，共19頁(yè)。思考思考3:3:該算法的程序框圖如何該算

10、法的程序框圖如何(rh)(rh)表表示？示？開(kāi)始開(kāi)始輸入輸入m，nnk？m=n是是輸出輸出m結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否第12頁(yè)/共19頁(yè)第十三頁(yè)，共19頁(yè)。思考思考4:4:該程序該程序(chngx)(chngx)框圖對(duì)應(yīng)的程序框圖對(duì)應(yīng)的程序(chngx)(chngx)如何表述？如何表述？INPUT mINPUT m，n nWHILE WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND開(kāi)始開(kāi)始輸入輸入m，n

11、nk？m=n是是輸 出輸 出m結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否第13頁(yè)/共19頁(yè)第十四頁(yè)，共19頁(yè)?！案鄿p損術(shù)更相減損術(shù)”在中國(guó)古代數(shù)學(xué)專(zhuān)著九章在中國(guó)古代數(shù)學(xué)專(zhuān)著九章算術(shù)算術(shù)(ji zhn sun sh)(ji zhn sun sh)中記述為：中記述為： 可半者半之，不可半者，副置分母、子之?dāng)?shù)可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之約之. . 第14頁(yè)/共19頁(yè)第十五頁(yè)，共19頁(yè)。理論理論(lln)遷遷移移 例1 分別用輾轉(zhuǎn)(zhnzhun)相除法和更相減損術(shù)求168與93的最大公約數(shù). 輾轉(zhuǎn)輾

12、轉(zhuǎn)(zhnzhun)(zhnzhun)相除法：相除法：168=93168=931+751+75， 93=75 93=751+181+18， 75=18 75=184+34+3， 18=3 18=36.6.第15頁(yè)/共19頁(yè)第十六頁(yè)，共19頁(yè)。更相減損更相減損(jin sn)(jin sn)術(shù)術(shù):168-93=75:168-93=75， 93-75=18 93-75=18， 75-18=57 75-18=57， 57-18=39 57-18=39， 39-18=21 39-18=21， 21-18=3 21-18=3， 18-3=15 18-3=15， 15-3=12 15-3=12， 12-3

13、=9 12-3=9， 9-3=6 9-3=6， 6-3=3. 6-3=3.第16頁(yè)/共19頁(yè)第十七頁(yè)，共19頁(yè)。 例例2 2 求求325325，130130，270270三個(gè)數(shù)的最大公三個(gè)數(shù)的最大公約數(shù)約數(shù). . 因?yàn)橐驗(yàn)?yn wi)325=130(yn wi)325=1302+652+65，130=65130=652 2，所以，所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65. 65. 因?yàn)橐驗(yàn)?yn wi)270=65(yn wi)270=654+104+10，65=1065=106+56+5，10=510=52 2，所以，所以6565與與270270最大最大公約數(shù)是公約

14、數(shù)是5. 5. 故故325325，130130，270270三個(gè)數(shù)的最大公約三個(gè)數(shù)的最大公約數(shù)是數(shù)是5.5.第17頁(yè)/共19頁(yè)第十八頁(yè)，共19頁(yè)。 1. 1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)用較大的數(shù)除以較小的數(shù)，若余數(shù)(ysh)(ysh)不為零不為零，則將余數(shù)，則將余數(shù)(ysh)(ysh)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù)時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù). . 小結(jié)小結(jié)(xioj