1.3-2更相減損術(精)

1、1.3算法案例第二課時知識探究(二)：更相減損術思考 1：設兩個正整數(shù) mn,若 m-n=k,貝!Jm與n的最大公約數(shù)和n與k的最大公約數(shù) 有什么關系？反復利用這個原理，可求 得 98與 63 的最大公約數(shù)為多少？98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7.思考 2:上述求兩個正整數(shù)的最大公約數(shù) 的方法稱為更相減損術一般地，用更相 減損術求兩個正整數(shù) m, n 的最大公約數(shù)， 可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算 法步驟如何設計？第一步，給定兩個正整數(shù)n (mn).第二步，計算m-n所得的差k.第三步，比較n與k的大小，其中大者用說 示，小者

2、用n表示.第四步，若m=m則m, n的最大公約數(shù)等于m;否則，返回第二步.思考 3:該算法的程序框圖如何表示?INPUT m, nWHILE monk=m-nIF nk THENm=n n=k ELSE .END IF WENDPRINT mEND“更相減損術”n/m=k k=m-n思考 4:該程序框圖對應的程序如何表述?開始在中國古代數(shù)學專著九章算術中記述為：可半者半之，不可半者，副置分母、子 之數(shù)，以少減多，更相減損，求其等也， 以等數(shù)約之.理論遷移例 1 分別用輾轉(zhuǎn)相除法和更相減損 術求 168 與 93 的最大公約數(shù).輾轉(zhuǎn)相除法：168=93X1+75, 93=75X1+18,75=1

3、8X4+3,18=3X6.更相減損術:168-93=75,93-75=18,75-18=57,57-18=39,39-18=21,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,例 2 求 325, 130, 270 三個數(shù)的最大 公約數(shù).因為 325=130X2+65, 130=65X2, 所以325 與 130 的最大公約數(shù)是 65.因為 270=65X4+10, 65=10X6+5,10=5X2,所以 65 與 270 最大公約數(shù)是 5.故 325, 130, 270 三個數(shù)的最大公約 數(shù)是 5.小結(jié)作業(yè)1輾轉(zhuǎn)相除法，就是對于給定的兩個正整 數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為 零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)， 繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止， 這時的較小的數(shù)即為原來兩個數(shù)的最大公約 數(shù).2.更相減損術，就是對于給定的兩個正 整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差 和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的減 法，直到差