算法案例之求最大公約數(shù)課件

算法案例之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。(注：若整數(shù)m和n滿足n整除m，則（m,n）=n。用（m,n）來表示m和n的最大公約數(shù)。)（2）（24，16）（4）（72，8）（1）（18，30）（3）（63，63）（5）（301，133）解：2

18 24

用公有質因數(shù)2除，3

9 12

用公有質因數(shù)3除，3

4 3和4互質不除了。得：18和24最大公約數(shù)是：2×3＝6想一想，如何求8251與6105的最大公約數(shù)？例、求18與24的最大公約數(shù)：8；8；6；63；7；短除法1謝謝你的關注2019-11-7開始i=m+1輸入：m,nm

MOD

i=0且n

MODi=0?i=i-1結束Y輸出：iNt=m,m=n,n=tNm>n?Y窮舉法窮舉法（也叫枚舉法）步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)。2謝謝你的關注2019-11-7定理：已知m,n,r為正整數(shù)，若m=nq+r（0≤r<n）（即r=m

MOD

n）,則（m,n）=(n,r)。2019-11-73謝謝你的關注輾轉相除法分析：m=nq+rr=m-nq……

①……②例1、求8251和6105的最大公約數(shù)。（8251，6105）=（6105，2146）=（2146，1813）=（1813，333）=（333，148）=（148，37）=37解：8251=6105×1+21466105=2146

×2+18132146=1813

×1+3331813=333

×5+148333=148

×2+37148=37

×4練習：用輾轉相除法求下列兩數(shù)的最大公約數(shù)：2019-11-74謝謝你的關注（1）（225，135）（3）（72，168）45

（2）（98，196）

9824

（4）（153，119）

17次數(shù)456nr8251和6105的最大公約數(shù)解：8251=6105×1+21466105=2146

×2+18132146=1813

×1+3331813=333

×5+148333=148

×2+37148=37

×4（8251，6105）=（6105，2146）=（2146，1813）=（1813，333）=（333，148）=（148，37）=37關系式m=np+r中m,n,r得取值變化情況1

2

3m

8251

6105

21466105

2146

18132146

1813

3331813333148148333371482019-11-75謝謝你的關注370思考：輾轉相除直到何時結束？主要運用的是哪種算法結構？輾轉相除法是一個反復執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結構輾轉相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：①輸入兩個正整數(shù)m和n；②求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中；③更新被除數(shù)和余數(shù)：m=n，n=r。④判斷余數(shù)r是否為0：若余數(shù)為0則輸出結果，否則轉向第②步繼續(xù)循環(huán)執(zhí)行。如此循環(huán)，直到得到結果。2019-11-76謝謝你的關注開始輸入：m,n結束m=nNr=0?Y輸出：mr=m

MOD

nn=r程序：INPUT

“m，n=”;m,nDOr=m

MOD

nm=nn=rLOOP

UNTIL

r=0PRINT

mEND2019-11-77謝謝你的關注更相減損術2019-11-78謝謝你的關注同理：a,b,c為正整數(shù)，若a-b=c，則（a,b）=(b,c)?！案鄿p損術”（也是求兩個正整數(shù)的最大公約數(shù)的算法）步驟：第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。例、用更相減損術求98與63的最大公約數(shù)2019-11-79謝謝你的關注=

7所以，98和63的最大公約數(shù)等于7。（自己按照步驟求解）解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減。（98，63）=（63，35）=（35，28）=（28，7）98-63=3563-35=2835-28=728-7=2121-7=1414-7=7=（21，7）=（14，7）=（7，7）練習：用更相減損術求下列兩數(shù)的最大公約數(shù)：2019-11-710謝謝你的關注（2）（98，196）（1）（225，135）

45

98（3）（72，168）

24（4）（153，119）

17例用更相減損術求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉相減98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）=（35，28）=（28，7）=（21，7）=（14，7）=（7，7）=7次數(shù)56a1

2

3

498

63

35

28

21

14b63

35

28

77735

28

21

147關系式a-b=c中a,b,c得取值變化情況11謝謝7你的關注2019-11c-7更相減損是一個反復執(zhí)行直到減數(shù)等于差時停止的步驟，這實際也是一個循環(huán)結構思考：更相減損直到何時結束？運用的是哪種算法結構？12謝謝你的關注2019-11-7程序：INPUT

“a,b”;a,bi=0WHILE

a

MOD

2=0

AND

b

MOD

2=0a=a/2b=b/2i=i+1WENDDOIF

b>a

THENt=aa=bb=tEND

IFa=a-bLOOP

UNTIL

a=bPRINT

a*2^iEND開始輸入：a,ba=a/2,b=b/2Ya=a-bt=a,a=b,b=ta

MOD

2=0且b

MOD

2=0?a=b?Y輸出：a×2iNNNb>a?Yi=0i=i+113謝謝你的關注2019-11-7結束小

結2019-11-714謝謝你的關注輾轉相除法與更相減損術的區(qū)別：都是求最大公約數(shù)的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉相除法計