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

算法案例之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。(注：若整數(shù)m和n滿足n整除m，則（m,n）=n。用（m,n）來表示m和n的最大公約數(shù)。)（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）（5）（301，133）解：21824用公有質(zhì)因數(shù)2除，3912用公有質(zhì)因數(shù)3除，343和4互質(zhì)不除了。得：18和24最大公約數(shù)是：2×3＝6

想一想，如何求8251與6105的最大公約數(shù)？

例、求18與24的最大公約數(shù)：6；8；63；8；7；短除法1感謝你的欣賞2019-10-6算法案例之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。解：2開始i=m+1輸入：m,nmMODi=0且nMODi=0?i=i-1輸出：i結(jié)束YNm>n?t=m,m=n,n=tNY窮舉法（也叫枚舉法）步驟：

從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)。窮舉法2感謝你的欣賞2019-10-6開始i=m+1輸入：m,nmMODi=0且nMOD定理：已知m,n,r為正整數(shù)，若m=nq+r（0≤r<n）（即r=mMODn）,則（m,n）=(n,r)。輾轉(zhuǎn)相除法分析：m=nq+r……①r=m-nq……②例1、求8251和6105的最大公約數(shù)。148=37×4=378251=6105×1+2146（8251，6105）=（6105，2146）6105=2146×2+1813=（2146，1813）2146=1813×1+333=（1813，333）1813=333×5+148=（333，148）333=148×2+37=（148，37）解：3感謝你的欣賞2019-10-6定理：已知m,n,r為正整數(shù)，若m=nq+r（0≤r<n）練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）459824174感謝你的欣賞2019-10-6練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：459824174次數(shù)123456mnr8251和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關(guān)系式m=np+r中m,n,r得取值變化情況825161052146610521462146181318133331813333148148333371483705感謝你的欣賞2019-10-6次數(shù)123456mnr8251和6105的最大公約數(shù)解：（8輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)

思考：輾轉(zhuǎn)相除直到何時結(jié)束？主要運用的是哪種算法結(jié)構(gòu)？如此循環(huán)，直到得到結(jié)果。①輸入兩個正整數(shù)m和n；②求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中；③更新被除數(shù)和余數(shù)：m=n，n=r。④判斷余數(shù)r是否為0：若余數(shù)為0則輸出結(jié)果，否則轉(zhuǎn)向第②步繼續(xù)循環(huán)執(zhí)行。6感謝你的欣賞2019-10-6輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除開始輸入：m,n輸出：m結(jié)束r=0?m=nNYr=mMODnn=r程序：

INPUT“m，n=”;m,n

DO

r=mMODn

m=n

n=r

LOOPUNTILr=0

PRINTm

END7感謝你的欣賞2019-10-6開始輸入：m,n輸出：m結(jié)束r=0?m=nNYr=mMOD更相減損術(shù)同理：a,b,c為正整數(shù)，若a-b=c，則（a,b）=(b,c)?！案鄿p損術(shù)”（也是求兩個正整數(shù)的最大公約數(shù)的算法）步驟：第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。8感謝你的欣賞2019-10-6更相減損術(shù)同理：a,b,c為正整數(shù)，若a-b=c，則（a,b例、用更相減損術(shù)求98與63的最大公約數(shù)（自己按照步驟求解）解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。=7所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）98-63=35

63-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）9感謝你的欣賞2019-10-6例、用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)練習(xí)：用更相減損術(shù)求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）4598241710感謝你的欣賞2019-10-6練習(xí)：用更相減損術(shù)求下列兩數(shù)的最大公約數(shù)：459824171例

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

98-63=35

63-35=28

35-28=7

28-7=2121-7=14

14-7=7

所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）=（35，28）=（28，7）=（21，7）=（14，7）=（7，7）=7次數(shù)123456a986335282114b633528777c3528721147關(guān)系式a-b=c中a,b,c得取值變化情況11感謝你的欣賞2019-10-6例用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)更相減損是一個反復(fù)執(zhí)行直到減數(shù)等于差時停止的步驟，這實際也是一個循環(huán)結(jié)構(gòu)

思考：更相減損直到何時結(jié)束？運用的是哪種算法結(jié)構(gòu)？12感謝你的欣賞2019-10-6更相減損是一個反復(fù)執(zhí)行直到減數(shù)等于差時停止的步驟，思考：更相程序：INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb>aTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND開始輸入：a,b輸出：a×2i結(jié)束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tb>a?aMOD2=0且bMOD2=0?YNNNYi=0i=i+113感謝你的欣賞2019-10-6程序：開始輸入：a,b輸出：a×2i結(jié)束a=b?a=a/2,輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：小結(jié)（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0而得到，而更相減損術(shù)則以減數(shù)與差相等而得到的。14感謝你的欣賞2019-10-6輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：小結(jié)（1）都是求最大公約數(shù)作業(yè)：P38習(xí)題：1.3第一題15感謝你的欣賞2019-10-6作業(yè)：15感謝你的欣賞2019-10-616感謝你的欣賞2019-10-616感謝你的欣賞2019-10-6再見17感謝你的欣賞2019-10-6再見17感謝你的欣賞2019-10-6算法案例之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。(注：若整數(shù)m和n滿足n整除m，則（m,n）=n。用（m,n）來表示m和n的最大公約數(shù)。)（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）（5）（301，133）解：21824用公有質(zhì)因數(shù)2除，3912用公有質(zhì)因數(shù)3除，343和4互質(zhì)不除了。得：18和24最大公約數(shù)是：2×3＝6

想一想，如何求8251與6105的最大公約數(shù)？

例、求18與24的最大公約數(shù)：6；8；63；8；7；短除法18感謝你的欣賞2019-10-6算法案例之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。解：2開始i=m+1輸入：m,nmMODi=0且nMODi=0?i=i-1輸出：i結(jié)束YNm>n?t=m,m=n,n=tNY窮舉法（也叫枚舉法）步驟：

從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)。窮舉法19感謝你的欣賞2019-10-6開始i=m+1輸入：m,nmMODi=0且nMOD定理：已知m,n,r為正整數(shù)，若m=nq+r（0≤r<n）（即r=mMODn）,則（m,n）=(n,r)。輾轉(zhuǎn)相除法分析：m=nq+r……①r=m-nq……②例1、求8251和6105的最大公約數(shù)。148=37×4=378251=6105×1+2146（8251，6105）=（6105，2146）6105=2146×2+1813=（2146，1813）2146=1813×1+333=（1813，333）1813=333×5+148=（333，148）333=148×2+37=（148，37）解：20感謝你的欣賞2019-10-6定理：已知m,n,r為正整數(shù)，若m=nq+r（0≤r<n）練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）4598241721感謝你的欣賞2019-10-6練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：459824174次數(shù)123456mnr8251和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關(guān)系式m=np+r中m,n,r得取值變化情況8251610521466105214621461813181333318133331481483333714837022感謝你的欣賞2019-10-6次數(shù)123456mnr8251和6105的最大公約數(shù)解：（8輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)

思考：輾轉(zhuǎn)相除直到何時結(jié)束？主要運用的是哪種算法結(jié)構(gòu)？如此循環(huán)，直到得到結(jié)果。①輸入兩個正整數(shù)m和n；②求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中；③更新被除數(shù)和余數(shù)：m=n，n=r。④判斷余數(shù)r是否為0：若余數(shù)為0則輸出結(jié)果，否則轉(zhuǎn)向第②步繼續(xù)循環(huán)執(zhí)行。23感謝你的欣賞2019-10-6輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除開始輸入：m,n輸出：m結(jié)束r=0?m=nNYr=mMODnn=r程序：

INPUT“m，n=”;m,n

DO

r=mMODn

m=n

n=r

LOOPUNTILr=0

PRINTm

END24感謝你的欣賞2019-10-6開始輸入：m,n輸出：m結(jié)束r=0?m=nNYr=mMOD更相減損術(shù)同理：a,b,c為正整數(shù)，若a-b=c，則（a,b）=(b,c)。“更相減損術(shù)”（也是求兩個正整數(shù)的最大公約數(shù)的算法）步驟：第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。25感謝你的欣賞2019-10-6更相減損術(shù)同理：a,b,c為正整數(shù)，若a-b=c，則（a,b例、用更相減損術(shù)求98與63的最大公約數(shù)（自己按照步驟求解）解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。=7所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）98-63=35

63-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）26感謝你的欣賞2019-10-6例、用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)練習(xí)：用更相減損術(shù)求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）4598241727感謝你的欣賞2019-10-6練習(xí)：用更相減損術(shù)求下列兩數(shù)的最大公約數(shù)：459824171例

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

98-63=35

63-35=28

35-28=7

28-7=2121-7=14

14-7=7

所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）=（35，28）=（28，7）=（21，7）=（14，7）=（7，7）=7次數(shù)123456a986335282114b633528777c3528721147關(guān)系式a-b=c中a,b,c得取值變化情況28感謝你的欣賞2019-10-6例用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)更相減損是一個反復(fù)執(zhí)行直到減數(shù)等于差時停止的步驟，這實際也是一個循環(huán)結(jié)構(gòu)

思考：更相減損直到何時結(jié)束？運用的是哪種算法結(jié)構(gòu)？29感謝你的欣賞2019-10