新高一數(shù)學(xué)《案例1輾轉(zhuǎn)相除法與更相減損術(shù)》

1、廣靈五中高一數(shù)學(xué)備課組廣靈五中高一數(shù)學(xué)備課組 劉鴻英劉鴻英1. 1. 回顧算法的三種表述：回顧算法的三種表述：自然語言自然語言程序框圖程序框圖程序語言程序語言（三種邏輯結(jié)構(gòu)）（三種邏輯結(jié)構(gòu)）（五種基本語句）（五種基本語句）2. 2. 思考：思考： 小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法？小學(xué)學(xué)過的求兩個數(shù)最大公約數(shù)的方法？ 先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來互為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來. .復(fù)復(fù) 習(xí)回顧習(xí)回顧所以，所以，7575和和105105的最的最大公約數(shù)為大公約數(shù)為15152 2、除

2、了用這種方法外還有沒有其它方法？、除了用這種方法外還有沒有其它方法？如求如求82518251和和61056105的最大公約數(shù)的最大公約數(shù). . 1 1、求兩個正整數(shù)的最大公約數(shù)、求兩個正整數(shù)的最大公約數(shù)求求7575和和105105的最大公約數(shù)的最大公約數(shù)75755 5151510510521215 57 73 31 1、輾轉(zhuǎn)相除法、輾轉(zhuǎn)相除法: :此算法是歐幾里得在公元前此算法是歐幾里得在公元前300300左右左右首先提出的首先提出的 （歐幾里得算法）（歐幾里得算法） 所謂輾轉(zhuǎn)相除法所謂輾轉(zhuǎn)相除法, ,就是對于給定的兩個數(shù)就是對于給定的兩個數(shù), ,用較大用較大的數(shù)除以較小的數(shù)的數(shù)除以較小的數(shù).

3、 .若余數(shù)不為零若余數(shù)不為零, ,則將余數(shù)和較小的則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)數(shù)構(gòu)成新的一對數(shù), ,繼續(xù)上面的除法繼續(xù)上面的除法, ,直到大數(shù)被小數(shù)直到大數(shù)被小數(shù)除盡除盡, ,則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù). .例例1.用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求161與與63的最大公約數(shù)的最大公約數(shù).161=2633563=1 352835=1 28728=4 70所以，所以，161與與63的最大公約數(shù)為的最大公約數(shù)為7 7新新 課課82518251= =610561051+1+21462146 61056105= =214621462+2+181318

4、13 21462146= =181318131+1+33333318131813= =3333335+5+148148333333= =1481482+2+3737148148= =37374 4所以所以3737是是82518251和和61056105的最大公約數(shù)的最大公約數(shù) 例例2 2、求、求82518251和和61056105的最大公的最大公約數(shù)約數(shù). . P P4545) )練習(xí)練習(xí)1(1)1(1)用輾轉(zhuǎn)相除法用輾轉(zhuǎn)相除法求求225225和和135135的最大公約數(shù)的最大公約數(shù)225225= =1351351+1+9090135135= =90901+1+45459090= =45452

5、 2所以所以4545是是225225和和135135的最大公約數(shù)的最大公約數(shù) 思考：從上面的兩個例子可思考：從上面的兩個例子可以看出計算的規(guī)律是什么？以看出計算的規(guī)律是什么？ S1S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3S3：重復(fù)：重復(fù)S1S1，直到余數(shù)為，直到余數(shù)為0 0 輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0 0停止的步驟停止的步驟, ,這實際上是這實際上是一個循環(huán)結(jié)構(gòu)一個循環(huán)結(jié)構(gòu)m=nm=nq qr r算法步驟算法步驟第一步：輸入兩個正整數(shù)第一步：輸入兩個正整數(shù)m,n(mm,n(mn)

6、.n).第二步：計算第二步：計算m m除以除以n n所得的余數(shù)所得的余數(shù)r.r.第三步：第三步：m=n,nm=n,n=r.=r.第四步：若第四步：若r r0,0,則則m,nm,n的最大公約數(shù)等于的最大公約數(shù)等于m;m;否則轉(zhuǎn)到第二步否則轉(zhuǎn)到第二步. . 第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)m.m.程序框圖程序框圖程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r開始開始輸入輸入m,nm,nr=0?r=0? 輸出輸出m m結(jié)束結(jié)束INPUT “m,n=“;m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND程序框

7、圖程序框圖程程 序序INPUT “m,n=“;m,nWHILE WEND r = m MOD nm = nn = rr0PRINT mENDr=1求求m m除以除以n n的余數(shù)的余數(shù)r rm=nm=n是是否否n=rn=r開始開始輸入輸入m,nm,nr0?r0? 輸出輸出m m結(jié)束結(jié)束r=1r=12 2、更相減損術(shù)、更相減損術(shù)第一步：任意給定兩個正整數(shù)第一步：任意給定兩個正整數(shù); ;判斷他們是否都是偶判斷他們是否都是偶數(shù)數(shù). .若是若是, ,則用則用2 2約簡約簡; ;若不是則執(zhí)行第二步若不是則執(zhí)行第二步. .第二步：以較大的數(shù)減較小的數(shù)第二步：以較大的數(shù)減較小的數(shù), ,接著把所得的差與接著把所

8、得的差與較小的數(shù)比較較小的數(shù)比較, ,并以大數(shù)減小數(shù)并以大數(shù)減小數(shù). .繼續(xù)這個操作繼續(xù)這個操作, ,直到直到所得的減數(shù)和差相等為止所得的減數(shù)和差相等為止, ,則這個等數(shù)就是所求的最則這個等數(shù)就是所求的最大公約數(shù)大公約數(shù). . 算理：可半者半之算理：可半者半之, ,不可半者不可半者, ,副置分母、子之?dāng)?shù)副置分母、子之?dāng)?shù), ,以少以少減多減多, ,更相減損更相減損, ,求其等也求其等也, ,以等數(shù)約之以等數(shù)約之. .例例3 3 用更相減損術(shù)求用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù)解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減以大數(shù)

9、減小數(shù)，并輾轉(zhuǎn)相減 989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以，9898和和6363的最大公約數(shù)等于的最大公約數(shù)等于7 7 98=6313563=3512835=2817 輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)(1)都是求最大公約數(shù)的方法都是求最大公約數(shù)的方法, ,計算上輾轉(zhuǎn)相除法以除法為主計算上輾轉(zhuǎn)相除法以除法為主, ,更相減損術(shù)以減法為主更相減損術(shù)以減法為主, ,計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少少, ,特別當(dāng)兩個數(shù)字大小區(qū)別較大

10、時計算次數(shù)的區(qū)別較明顯特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯. .(2)(2)從結(jié)果體現(xiàn)形式來看從結(jié)果體現(xiàn)形式來看, ,輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為為0 0而而 得到得到, ,而更相減損術(shù)則以減數(shù)與差相等而得到而更相減損術(shù)則以減數(shù)與差相等而得到解法1：（更相減損術(shù)）由于49不是偶數(shù)，把91和49以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：914942 49427 42735 35728 28721 21714 147791與49的最大公約數(shù)是7。解法2（輾轉(zhuǎn)相除法） 9149142 494217 4276 91與49的最大公約數(shù)是7。探究探究3:怎樣用更相減損術(shù)求

11、182與98的最大公約數(shù)? 方法：由于 182與98 都是偶數(shù)，故將它們同除以2，得91與49，再用上面的方法求得91與49的最大公約數(shù)為7，則72=14為182與98的最大公約數(shù).理論遷移理論遷移 例例1 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

12、-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=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3. 例例2 2 求求325325，130130，270270三個數(shù)的最大三個數(shù)的最大公約數(shù)公約數(shù). . 因為因為325=130325=1302+652+65，130=65130=652 2，所以所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65.65. 因為因為270=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以，所以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，270270三個數(shù)的最大公約三個數(shù)的最大公約數(shù)是數(shù)是5.5.用更相減損術(shù)求兩個整用更相減損術(shù)求兩個整數(shù)數(shù)m，n的最大公約數(shù)的最大公約數(shù)INPUT “m,n=”;m,nWHILE mn IF mn T