高一數(shù)學(xué)《1.3-1輾轉(zhuǎn)相除法與更相減損術(shù)》課件

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

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

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

4、131+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:上述求兩個(gè)正整數(shù)的最大公約數(shù)上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為的方法稱為輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法或或歐幾里得算法歐幾里得算法. .一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？

5、其算法步驟如何設(shè)計(jì)？構(gòu)造算法？其算法步驟如何設(shè)計(jì)？ 第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn(mn).n).第二步，計(jì)算第二步，計(jì)算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結(jié)束結(jié)束否否思考思考6:6:該程序框圖對(duì)應(yīng)的程序如何表述？

6、該程序框圖對(duì)應(yīng)的程序如何表述？INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否思考思考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ù)的程序框圖和程序分別如何表示？示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)r

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

8、-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:上述求兩個(gè)正整數(shù)的最大公約數(shù)上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為的方法稱為更相減損術(shù)更相減損術(shù). .一般地，用更相一般地，用更相減損術(shù)求兩個(gè)正整數(shù)減損術(shù)求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？法步驟如何設(shè)計(jì)？第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn(mn).n). 第二步，計(jì)算第二步，計(jì)算m-nm

9、-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結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否思考思考4:4:該程序框圖對(duì)應(yīng)的程序如何表述？該程序框圖對(duì)應(yīng)的程序如何表述？INPUT mINPUT m，n nWHILE WHIL

10、E 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結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否“更相減損術(shù)更相減損術(shù)”在中國(guó)古代數(shù)學(xué)專著在中國(guó)古代數(shù)學(xué)專著九章算術(shù)九章算術(shù)中記述為：中記述為： 可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之以等數(shù)約之. . 理論遷移理論遷移 例例1

11、1 分別用輾轉(zhuǎn)相除法和更相減損分別用輾轉(zhuǎn)相除法和更相減損術(shù)求術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.更相減損術(shù)更相減損術(shù):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-3

12、=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3. 例例2 2 求求325325，130130，270270三個(gè)數(shù)的最大三個(gè)數(shù)的最大公約數(shù)公約數(shù). . 因?yàn)橐驗(yàn)?25=130325=1302+652+65，130=65130=652 2，所以所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65.65. 因?yàn)橐驗(yàn)?70=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，270270三個(gè)數(shù)的最大公約三個(gè)數(shù)的最大公約數(shù)是數(shù)是5.5. 1. 1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約這時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公