Question

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

其中能夠實現求兩個正整數的最大公約數的算法有（　�。﹤�．

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

Answer 1

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

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

點評 輾轉相除法與更相減損術的區別：
（1）都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯．
（2）從結果體現形式來看，輾轉相除法體現結果是以相除余數為0則得到，而更相減損術則以減數與差相等而得到．