課程內(nèi)容

《算法案例—輾轉(zhuǎn)相除法與更相減損術(shù)》
知識探究（一）：輾轉(zhuǎn)相除法
思考1：18與30的最大公約數(shù)是多少？你是怎樣得到的？
思考2：8251與6105的最大公約數(shù)是多少？
思考3：注意到8251=6105×1+2146，那么8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？
又6105=2146×2+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等。重復(fù)上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎？
  8251=6105×1+2146
  6105=2146×2+1813
  2146=1813×1+333
  1813=333×5+148
  333=148×2+37
  148=37×4+0
所以，37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)。
上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法。
思考4：一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？
思考5：該算法的程序框圖如何表示？
思考6：該程序框圖對應(yīng)的程序如何表述？
知識探究（二）：更相減損術(shù)
思考1：設(shè)兩個正整數(shù)m>n，若m-n=k，則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等。反復(fù)利用這個原理，可求得98與63的最大公約數(shù)為多少？
  98-63=35
  63-35=28
  35-28=7
  28-7=21
  21-7=14
  14-7=7
上述求兩個正整數(shù)的最大公約數(shù)的方法稱為更相減損術(shù)。
思考2：一般地，用更相減損術(shù)求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？
思考3：該算法的程序框圖如何表示？
思考4：該程序框圖對應(yīng)的程序如何表述？
典型例題
例：分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù)。