算法案例(輾轉(zhuǎn)相除法和更相減損術(shù))

第第頁算法案例(輾轉(zhuǎn)相除法和更相減損術(shù))數(shù)學(xué)教學(xué)

算法案例

(第一課時(shí))

數(shù)學(xué)教學(xué)

1、求兩個(gè)正整數(shù)的最大公約數(shù)、(1)求25和35的最大公約數(shù))和的最大公約數(shù)(2)求49和63的最大公約數(shù))和的最大公約數(shù)(1)5)255357(2)7)497639

所以，和的最大公約數(shù)為的最大公約數(shù)為5所以，25和35的最大公約數(shù)為

所以，和的最大公約數(shù)為的最大公約數(shù)為7所以，49和63的最大公約數(shù)為

2、求8251和6105的最大公約數(shù)、和的最大公約數(shù)

數(shù)學(xué)教學(xué)

輾轉(zhuǎn)相除法,又名“歐幾里德算法”(Euclideanalgorithm)乃求兩數(shù)之最大公因數(shù)算法。它是已知最古老的算法,其可追溯至前300年。它首次涌現(xiàn)于歐幾里德的《幾何原本》中，而在中國那么可以追溯至東漢涌現(xiàn)的《九章算術(shù)》。它并不需要把二數(shù)作質(zhì)因數(shù)分解

歐幾里德

數(shù)學(xué)教學(xué)

輾轉(zhuǎn)相除法(歐幾里得算法)輾轉(zhuǎn)相除法(歐幾里得算法)觀測用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過程和觀測用輾轉(zhuǎn)相除法求的最大公約數(shù)的過程用兩數(shù)中較大的數(shù)除以較小的數(shù)，第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論：8251和6105的公約數(shù)就是結(jié)論：和的公約數(shù)就是6105和2146的公約數(shù)，求8251和和的公約數(shù)，和的公約數(shù)就是的公約數(shù)6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。的最大公約數(shù)，只要求出和的公約數(shù)就可以了。的最大公約數(shù)的公約數(shù)就可以了

第二步對6105和2146重復(fù)第一步的做法和重復(fù)第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和1813的最大公約數(shù)。的最大公約數(shù)。同理和的最大公約數(shù)也是和的最大公約數(shù)

數(shù)學(xué)教學(xué)

完整的過程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0顯著37是顯著是148和37的最大公約和的最大公約也就是8251和6105的最數(shù)，也就是和的最大公約數(shù)

用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)例2用輾轉(zhuǎn)相除法求和的最大公約數(shù)225=1351+90135=901+4590=452顯著45是和的最大公約數(shù)的最大公約數(shù)，顯著是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)225和135的最大公約數(shù)思索1:思索：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？算的規(guī)律是什么？S1:用大數(shù)除以小數(shù)：S2:除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，S3:重復(fù)S1,直到余數(shù)為：重復(fù)，直到余數(shù)為0

數(shù)學(xué)教學(xué)

輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于停止的步驟，這事實(shí)上是停止的步驟一個(gè)循環(huán)結(jié)構(gòu)。一個(gè)循環(huán)結(jié)構(gòu)。

m=nq+r

用程序框圖表示出右邊的過程

8251=61051+21466105=21462+1813

2146=18131+3331813=3335+148

r=mMODnm=nn=rr=0?是否

333=1482+37148=374+0

數(shù)學(xué)教學(xué)

《九章算術(shù)》——更相減損術(shù)九章算術(shù)》更相減損術(shù)算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減求其等也，以等數(shù)約之。損，求其等也，以等數(shù)約之。

第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。假設(shè)是，那么用第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。假設(shè)是，那么用2約簡；假設(shè)不是那么執(zhí)行第二步。約簡；假設(shè)不是那么執(zhí)行第二步。

第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，那么這個(gè)等數(shù)就是所求的最大公約數(shù)。等數(shù)就是所求的最大公約數(shù)。

數(shù)學(xué)教學(xué)

用更相減損術(shù)求98與的最大公約數(shù)例3用更相減損術(shù)求與63的最大公約數(shù)不是偶數(shù)，以大數(shù)減小數(shù)，解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減由于不是偶數(shù)和以大數(shù)減小數(shù)98-63=35-=63-35=28-=35-28=7-=28-7=21-=