輾轉(zhuǎn)相除法與更相減損術(shù)

1、1 算 法 案 例23 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo) 1.通過輾轉(zhuǎn)相除法與更相減損術(shù)的學(xué)習(xí)通過輾轉(zhuǎn)相除法與更相減損術(shù)的學(xué)習(xí),進(jìn)一步體會(huì)算法思進(jìn)一步體會(huì)算法思想想 2.通過古代著名的算法通過古代著名的算法,理解掌握輾轉(zhuǎn)相除法與更相減損術(shù)理解掌握輾轉(zhuǎn)相除法與更相減損術(shù)算法的含義算法的含義;了解其計(jì)算過程了解其計(jì)算過程;了解其算法程序框圖和程序了解其算法程序框圖和程序41. 1. 回顧算法的三種表述：回顧算法的三種表述：自然語(yǔ)言自然語(yǔ)言程序框圖程序框圖程序語(yǔ)言程序語(yǔ)言（三種邏輯結(jié)構(gòu)）（三種邏輯結(jié)構(gòu)）（五種基本語(yǔ)句）（五種基本語(yǔ)句）2. 2. 思考：思考： 小學(xué)學(xué)過的求兩個(gè)數(shù)最大公約數(shù)的方法？小學(xué)學(xué)過的求兩個(gè)數(shù)最

2、大公約數(shù)的方法？ 先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái)為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái). .復(fù)復(fù) 習(xí)習(xí)52525（1 1）5 55 535357 7所以，所以，2525和和3535的的最大公約數(shù)為最大公約數(shù)為5 54949（2 2）7 77 763639 9所以，所以，4949和和6363的的最大公約數(shù)為最大公約數(shù)為7 72 2、除了用這種方法外還有沒有其它方法？、除了用這種方法外還有沒有其它方法？算出算出82518251和和61056105的最大公約數(shù)的最大公約數(shù). . 1 1、求兩個(gè)正整

3、數(shù)的最大公約數(shù)、求兩個(gè)正整數(shù)的最大公約數(shù)（1 1）求）求2525和和3535的最大公約數(shù)的最大公約數(shù) （2 2）求）求4949和和6363的最大公約數(shù)的最大公約數(shù)61 1、輾轉(zhuǎn)相除法（歐幾里得算法）、輾轉(zhuǎn)相除法（歐幾里得算法） 所謂輾轉(zhuǎn)相除法所謂輾轉(zhuǎn)相除法, ,就是對(duì)于給定的兩個(gè)數(shù)就是對(duì)于給定的兩個(gè)數(shù), ,用較大的數(shù)除以較用較大的數(shù)除以較小的數(shù)小的數(shù). .若余數(shù)不為零若余數(shù)不為零, ,則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù), ,繼續(xù)繼續(xù)上面的除法上面的除法, ,直到大數(shù)被小數(shù)除盡直到大數(shù)被小數(shù)除盡, ,則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)

4、數(shù)的最大公約數(shù). .例例1.用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求98與與63的最大公約數(shù)的最大公約數(shù).98=1633563=1 352835=1 28728=4 70所以，所以，98與與63的最大公約數(shù)為的最大公約數(shù)為7 7新新 課課7輾轉(zhuǎn)相除法的原理：輾轉(zhuǎn)相除法的原理：如果如果q q和和r r是是m m除以除以n n的商及余數(shù)的商及余數(shù), , 即即 m m= =n nq+q+r r, ,則則gcd(m,n)=gcd(n,rgcd(m,n)=gcd(n,r).).證明證明: : 設(shè)設(shè) a=gcd(m,n),b=gcd(n,ra=gcd(m,n),b=gcd(n,r) ) 則有則有a|a|m m 及及a

5、|a|n n, ,因此因此a|(m-nqa|(m-nq), ), 即即 a|ra|r及及a|na|n, ,所以所以a|ba|b又又 b|b|r r及及b|b|n n, ,所以所以b|(nq+rb|(nq+r),),即即b|mb|m及及b|nb|n, ,所以所以b|ab|a因?yàn)橐驗(yàn)閍|ba|b并且并且b|ab|a, ,所以所以a=ba=b, ,即即gcd(m,n)=gcd(n,rgcd(m,n)=gcd(n,r).). 如計(jì)算如計(jì)算 gcd(546, 429)gcd(546, 429) 546=1 546=1429+117,429+117, 429=3 429=3117+78,117+78, 1

6、17=1 117=178+39,78+39, 78=2 78=23939 geatest common divisor882518251= =610561051+1+21462146 61056105= =214621462+2+18131813 21462146= =181318131+1+33333318131813= =3333335+5+148148333333= =1481482+2+3737148148= =37374 4所以所以3737是是82518251和和61056105的的最大公約數(shù)最大公約數(shù) 求求82518251和和61056105的最大公約數(shù)的最大公約數(shù). . P P4

7、545) )練習(xí)練習(xí)1(1)1(1)用輾轉(zhuǎn)相除法用輾轉(zhuǎn)相除法求求225225和和135135的最大公約數(shù)的最大公約數(shù)225225= =1351351+1+9090135135= =90901+1+45459090= =45452 2所以所以4545是是225225和和135135的最大公約數(shù)的最大公約數(shù) 思考：從上面的兩個(gè)例子可思考：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？以看出計(jì)算的規(guī)律是什么？ S1S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3S3：重復(fù)：重復(fù)S1S1，直到余數(shù)為，直到余數(shù)為0 09 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直

8、到余數(shù)等于輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0 0停止的步驟停止的步驟, ,這實(shí)際上是一個(gè)這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)m=nm=nq qr r算法步驟算法步驟第一步：輸入兩個(gè)正整數(shù)第一步：輸入兩個(gè)正整數(shù)m,n(mm,n(mn).n).第二步：計(jì)算第二步：計(jì)算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.10程序框圖程序框圖程程 序序r=m MOD nr=m MOD

9、nm=nm=n是是否否n=rn=r開始開始輸入輸入m,nm,nr=0?r=0? 輸出輸出m m結(jié)束結(jié)束直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)INPUT “m,n=“;m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND11程序框圖程序框圖程程 序序當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)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=1122 2、更

10、相減損術(shù)、更相減損術(shù) 算理算理：所謂更相減損術(shù)所謂更相減損術(shù), ,就是對(duì)于給定的兩個(gè)數(shù)就是對(duì)于給定的兩個(gè)數(shù), ,用較大用較大的數(shù)減去較小的數(shù)的數(shù)減去較小的數(shù), ,然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù), ,再再用較大的數(shù)減去較小的數(shù)用較大的數(shù)減去較小的數(shù), ,反復(fù)執(zhí)行此步驟直到差數(shù)和較小反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等的數(shù)相等, ,此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù)此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù). .第一步：任意給定兩個(gè)正整數(shù)第一步：任意給定兩個(gè)正整數(shù); ;判斷他們是否都是偶數(shù)判斷他們是否都是偶數(shù). .若是若是, ,則用則用2 2約簡(jiǎn)約簡(jiǎn); ;若不

11、是則執(zhí)行第二步若不是則執(zhí)行第二步. .第二步：以較大的數(shù)減較小的數(shù)第二步：以較大的數(shù)減較小的數(shù), ,接著把所得的差與較小的數(shù)接著把所得的差與較小的數(shù)比較比較, ,并以大數(shù)減小數(shù)并以大數(shù)減小數(shù). .繼續(xù)這個(gè)操作繼續(xù)這個(gè)操作, ,直到所得的減數(shù)和差相直到所得的減數(shù)和差相等為止等為止, ,則這個(gè)等數(shù)就是所求的最大公約數(shù)則這個(gè)等數(shù)就是所求的最大公約數(shù). . 算理：可半者半之算理：可半者半之, ,不可半者不可半者, ,副置分母、子之?dāng)?shù)副置分母、子之?dāng)?shù), ,以少以少減多減多, ,更相減損更相減損, ,求其等也求其等也, ,以等數(shù)約之以等數(shù)約之. .13例例3 3 用更相減損術(shù)求用更相減損術(shù)求9898與與6

12、363的最大公約數(shù)的最大公約數(shù)解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 989863633535636335352828353528287 728287 7212121217 7212114147 77 7所以，所以，9898和和6363的最大公約數(shù)等于的最大公約數(shù)等于7 7 98=6313563=3512835=2817 輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)(1)都是求最大公約數(shù)的方法都是求最大公約數(shù)的方法, ,計(jì)算上輾轉(zhuǎn)相除法以除法為主計(jì)算上輾轉(zhuǎn)相除法以除法為主, ,更相減損術(shù)以減法為主更相減損術(shù)以減法為主, ,計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少少, ,特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯. .(2)(2)從結(jié)果體現(xiàn)形式來(lái)看從結(jié)果體現(xiàn)形式來(lái)看, ,輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0 0則得到則得到, ,而更相減損術(shù)則以減數(shù)與差相等而得到而更相減損術(shù)則以減數(shù)與差相等而得到14用更相減損術(shù)求兩個(gè)整用更相減損術(shù)求兩個(gè)整數(shù)數(shù)m，n的最大公約數(shù)的最大公約數(shù)INPUT “m,n=”;m,nWHILE mn IF