1、算 法 案 例,(第一課時(shí)),1、求兩個(gè)正整數(shù)的最大公約數(shù),（1）求25和35的最大公約數(shù) （2）求49和63的最大公約數(shù),2、求8251和6105的最大公約數(shù),所以，25和35的最大公約數(shù)為5,所以，49和63的最大公約數(shù)為7,輾轉(zhuǎn)相除法（歐幾里得算法）,觀(guān)察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過(guò)程,第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146,結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。,第二步 對(duì)6105和2146重復(fù)第一步的做法6105=21

2、462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。,為什么呢？,思考：從上述的過(guò)程你體會(huì)到了什么？,完整的過(guò)程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例2 用輾轉(zhuǎn)相除法求225和135的最 大公約數(shù),225=1351+90,135=901+45,90=452,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),思考1：從上面的兩個(gè)例子可以看出計(jì)

3、算的規(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 = n q r,用程序框圖表示出右邊的過(guò)程,r=m MOD n,m = n,n = r,r=0?,是,否,思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？,當(dāng) 型 循 環(huán) 結(jié) 構(gòu) 的 程 序 框 圖,開(kāi)始,輸入m,n,r=1,r0?,否,是,求m除以n的余數(shù)r,m=n,r=n,輸出m,結(jié)束,Input m,n r=1 While r0 r=m mod n m=n n=r Wend Print m End,程序,九章算術(shù)更相減損術(shù),算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,第一步：任意給頂兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。,例3 用更相減損術(shù)求98與63的最大公約數(shù),解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn) 相減,98633563