1、算 法 案 例,(第一課時),孫子算經(jīng)中的孫子問題,秦九韶數(shù)書九章的“大衍求一術”,45世紀,中國剩余定理,南宋時期,意大利學者斐波那契的算術,1202年,歐拉發(fā)表關于同余式的解法,高斯的巨著算術研究,1734年,1801年,早500多年,1、求兩 個正整數(shù)的最大公約數(shù),（1）求25和 35的最大公約數(shù) （2）求49和63的最大公約數(shù),2、求8251和6105 的最大公約數(shù),所以，25和35的最大公約數(shù)為 5,所以，49和63的最大公約數(shù)為7,輾轉相除法 （歐幾里得算法）,觀察用輾 轉相除法求8251和6105的最大公約數(shù)的過程,第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61

2、051+2146,結論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。,第二步 對6105和2146重復第一步的做法6105=21462+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。,為什么呢？,思考：從上述的過程你體會到了什么？,完整的過程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例2 用輾轉相除法求225和135的最大公約數(shù),225=1351

3、+90,135=901+45,90=452,顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù),顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù),思考1：從上面的兩個例子可以看出計算的規(guī)律是什么？,S1：用大數(shù)除以小數(shù),S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù),S3：重復S1，直到余數(shù)為0,輾轉相除法是一個反復執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結構。,m = n q r,用程序框圖表示出右邊的過程,r=m MOD n,m = n,n = r,r=0?,是,否,思考2：輾轉相除法中的關鍵步驟是哪種邏輯結構？,九章算術更相減損術,算理：可半者半之，不

4、可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。,第一步：任意給頂兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。,例3 用更相減損術求98與63的最大公約數(shù),解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減,9863356335283528728721 21714 1477,所以，98和63的最大公約數(shù)等于7,歐幾里得輾轉相除法找出a,b的最大公約數(shù)的步驟是: （1）計算ab的余數(shù)r,若r

5、=0,則b為a,b的最大公約數(shù)； （2）若r=0,則把前面的除數(shù)b作為新的被除數(shù),把r作為新的除數(shù),繼續(xù)運算,直到余數(shù)為0,此時的除數(shù)即為a,b的最大公約數(shù).,更相減損術找出a,b的最大公約數(shù)的步驟是 （1）任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。 （2）以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。,比較輾轉相除法與更相減損術的區(qū)別,（1）都是求最大公約數(shù)的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。 （2）從結果體現(xiàn)形式來看，輾轉相除法體現(xiàn)結果是以相除余數(shù)為0則得到，而更相減損術則以減數(shù)與差相等而得到,回顧反思,輾轉相除法是當大數(shù)被小數(shù)除盡時，結束除法運算，較小的數(shù)就是最大公約數(shù) 更相