Question

12．下列的算法流程圖中，

其中能夠?qū)崿F(xiàn)求兩個正整數(shù)的最大公約數(shù)的算法有（　　）個．

• A． 1
• B． 2
• C． 3
• D． 0

Answer 1

分析 先寫出用輾轉(zhuǎn)相除法和更相減損術(shù)求最大公約數(shù)的算法，模擬執(zhí)行流程圖，即可得解．

解答 解：①輾轉(zhuǎn)相除法是求兩個自然數(shù)的最大公約數(shù)的一種方法，也叫歐幾里得算法，算法如下：
第一步，輸入兩個正整數(shù)m，n，
第二步，m除以n的余數(shù)是r，
接下來，將原來的除數(shù)作為新的被除數(shù)，原來的余數(shù)作為除數(shù)，繼續(xù)上面的過程，直到余數(shù)r=0，
退出程序，輸出兩個正整數(shù)的最大公約數(shù)m．
②更相減損術(shù)，是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，算法如下：
第一步：任意給定兩個正整數(shù)；判斷它們是否都是偶數(shù)．若是，則用2約簡；若不是則執(zhí)行第二步．
第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)．繼續(xù)這個操作，直到所得的減數(shù)和差相等為止．
則第一步中約掉的若干個2與第二步中等數(shù)的乘積就是所求的最大公約數(shù)．
結(jié)合算法，模擬執(zhí)行流程圖，即可得解能夠?qū)崿F(xiàn)兩個正整數(shù)的最大公約數(shù)的算法有3個．
故選：C．

點評 輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：
（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ù)與差相等而得到．