Question

中国古代数学著作《九章算法》中的“更相减损术”可用来求两个正整数的最大公约数．现应用此法求168与93的最大公约数：记（168，93）为初始状态，则第一步可得（75，93），第二步得到（75，18），第三步得到（57，18），第四步将得到（　　）

• A、（57，18）
• B、（39，3）
• C、（39，18）
• D、（21，18）

Answer 1

考点：用辗转相除计算最大公约数

专题：算法和程序框图

分析：本题考查的知识点是最大公因数和更相减损术，我们根据“以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的减数和差相等为止．”的原则，易求出168与93的最大公约数．然后找出第四步．

解答： 解：168-93=75，
93-75=18，①步
75-18=57，②步
57-18=39，③步
39-18=21，④步
21-18=3，
18-3=15．
15-3=12．
12-3=9
9-3=6．
6-3=3
因此168与93的最大公约数是3．
记（168，93）为初始状态，则第一步可得（75，93），第二步得到（75，18），…．以上解法中，第四步将得到（39，18）．
故选：C．

点评：更相减损术的方法和步骤是：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的减数和差相等为止．