(新)人教版高中數(shù)學(xué)必修三1.3.1《輾轉(zhuǎn)相除法與更相減損術(shù)》精品課件

1、 算 法 案 例案例1 輾轉(zhuǎn)相除法與更相減損術(shù) 學(xué)習(xí)目標(biāo) 1.通過輾轉(zhuǎn)相除法與更相減損術(shù)的學(xué)習(xí),進(jìn)一步體會(huì)算法思想 2.通過古代著名的算法,理解掌握輾轉(zhuǎn)相除法與更相減損術(shù)算法的含義;了解其計(jì)算過程;了解其算法程序框圖和程序1. 回顧算法的三種表述：自然語(yǔ)言程序框圖程序語(yǔ)言（三種邏輯結(jié)構(gòu)）（五種基本語(yǔ)句）2. 思考： 小學(xué)學(xué)過的求兩個(gè)數(shù)最大公約數(shù)的方法？ 先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互為質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái).復(fù) 習(xí)25（1）55357所以，25和35的最大公約數(shù)為549（2）77639所以，49和63的最大公約數(shù)為72、除了用這種方法外還有沒有其它方法？算出82

2、51和6105的最大公約數(shù). 1、求兩個(gè)正整數(shù)的最大公約數(shù)（1）求25和35的最大公約數(shù) （2）求49和63的最大公約數(shù)1、輾轉(zhuǎn)相除法（歐幾里得算法） 所謂輾轉(zhuǎn)相除法,就是對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)除以較小的數(shù).若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù),繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡,則這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù).例1.用輾轉(zhuǎn)相除法求98與63的最大公約數(shù).98=1633563=1 352835=1 28728=4 70所以，98與63的最大公約數(shù)為7新 課輾轉(zhuǎn)相除法的原理：如果q和r是m除以n的商及余數(shù), 即 m=nq+r,則gcd(m,n)=gcd(n,r).證明:

3、 設(shè) a=gcd(m,n),b=gcd(n,r) 則有a|m 及a|n,因此a|(m-nq), 即 a|r及a|n,所以a|b又 b|r及b|n,所以b|(nq+r),即b|m及b|n,所以b|a因?yàn)閍|b并且b|a,所以a=b,即gcd(m,n)=gcd(n,r). 如計(jì)算 gcd(546, 429) 546=1429+117, 429=3117+78, 117=178+39, 78=2398251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374所以37是8251和6105的最大公約數(shù) 求825

4、1和6105的最大公約數(shù). P45)練習(xí)1(1)用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=1351+90135=901+4590=452所以45是225和135的最大公約數(shù) 思考：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟,這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)m=nqr思考：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 算法步驟第一步：輸入兩個(gè)正整數(shù)m,n(mn).第二步：計(jì)算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：若r0,則m,n的最大公約數(shù)等于m;否則轉(zhuǎn)到第

5、二步. 第五步：輸出最大公約數(shù)m.程序框圖程 序r=m MOD nm=n是否n=r開始輸入m,nr=0? 輸出m結(jié)束直到型循環(huán)結(jié)構(gòu)INPUT “m,n=“;m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND程序框圖程 序當(dāng)型循環(huán)結(jié)構(gòu)INPUT “m,n=“;m,nWHILE WEND r = m MOD nm = nn = rr0PRINT mENDr=1求m除以n的余數(shù)rm=n是否n=r開始輸入m,nr0? 輸出m結(jié)束r=12、更相減損術(shù) 算理：所謂更相減損術(shù),就是對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)減去較小的數(shù),然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù),再

6、用較大的數(shù)減去較小的數(shù),反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等,此時(shí)相等的兩數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù).第一步：任意給定兩個(gè)正整數(shù);判斷他們是否都是偶數(shù).若是,則用2約簡(jiǎn);若不是則執(zhí)行第二步.第二步：以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作,直到所得的減數(shù)和差相等為止,則這個(gè)等數(shù)就是所求的最大公約數(shù). 算理：可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以等數(shù)約之.例3 用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721217211477所以，98和63的最大公約數(shù)等于7 98=6313563=3512835=2817 輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)都是求最大公約數(shù)的方法,計(jì)算上輾轉(zhuǎn)相除法以除法為主,更相減損術(shù)以減法為主,計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少,特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯.(2)從結(jié)果體現(xiàn)形式來(lái)看,輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到,而更相減損術(shù)則以減數(shù)與差相等而得到用更相減損術(shù)求兩個(gè)整數(shù)m，n的最大公約數(shù)INPUT “m,n=”;m,nWHILE mn IF mn THEN m=m-n ELSE n=n-m END IFWENDPRINT nEND程 序程