欧几里得算法（共 10 题）

单选题

1. 对如下代码实现的欧几里得算法（辗转相除法），执行 gcd(48,18) 得到的调用序列为（ ）。

   int gcd(int a, int b) {
       return b == 0 ? a : gcd(b, a % b);
   }
   

   {{ select(1) }}

• gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0)
• gcd(48,18) → gcd(30,18) → gcd(12,18)
• gcd(48,18) → gcd(18,30) → gcd(30,6)
• gcd(48,18) → gcd(12,18) → gcd(6,12)

2. 下面是根据欧几里得算法编写的函数，它计算的是 a 与 b 的（ ）。

   int gcd(int a, int b) {
       while (b != 0) {
           int temp = b;
           b = a % b;
           a = temp;
       }
       return a;
   }
   

   {{ select(2) }}

• 最小公倍数
• 最大公共质因子
• 最大公约数
• 最小公共质因子

3. 欧几里得算法还可以写成如下形式：

   int gcd(int a, int b) {
       return b == 0 ? a : gcd(b, a % b);
   }
   

   下面有关说法，错误的是（ ）。
   {{ select(3) }}

• 本题的 gcd() 实现为递归方式。
• 本题的 gcd() 代码量少，更容易理解其辗转相除的思想。
• 当 a 较大时，本题的 gcd() 实现会多次调用自身，需要较多额外的辅助空间。
• 当 a 较大时，相比上题中的 gcd() 的实现，本题的 gcd() 执行效率更高。

4. 两块长方形土地的长宽分别为 24 和 36 米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24,36) 来求正方形分块的边长，则函数 gcd 调用顺序为（ ）。

   int gcd(int a, int b) {
       int big = a > b ? a : b;
       int small = a < b ? a : b;
       if (big % small == 0) return small;
       return gcd(small, big % small);
   }
   

   {{ select(4) }}

• gcd(24,36)、gcd(24,12)、gcd(12,0)
• gcd(24,36)、gcd(12,24)、gcd(0,12)
• gcd(24,36)、gcd(24,12)
• gcd(24,36)、gcd(12,24)

5. 用以下辗转相除法（欧几里得算法）求 gcd(84,60) 的步骤中，第二步计算的数是（ ）。

   int gcd(int a, int b) {
       int big = a > b ? a : b;
       int small = a < b ? a : b;
       if (big % small == 0) return small;
       return gcd(small, big % small);
   }
   

   {{ select(5) }}

• 84 和 60
• 60 和 24
• 24 和 12
• 12 和 0

6. 下面代码实现了欧几里得算法。下面有关说法，错误的是（ ）。

   int gcd(int a, int b) {
       int big = a > b ? a : b;
       int small = a < b ? a : b;
       if (big % small == 0) return small;
       return gcd(small, big % small);
   }
   

   {{ select(6) }}

• 该算法可以求出最大公约数
• 该算法的时间复杂度为 O(log min(a,b))
• 如果 a 和 b 都是质数，该算法会递归一次
• 该算法在 a 和 b 相差很大时效率较低

7. 辗转相除法也被称为（ ）。
   {{ select(7) }}

• 高斯消元法
• 费马定理
• 欧几里德算法
• 牛顿迭代法

8. 下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（ ）。该代码也用到了欧几里得算法的思想吗？不，这里是高精度除法，但本题作为欧几里得算法部分的最后一题，实为高精度除法。不过为了保持分类，这里还是放一个与欧几里得相关的题目。实际上真题中有一道直接问欧几里得算法别名的题目（第7题）。第8题我改为：下面代码实现的是（ ）。

   int gcd(int a, int b) {
       if (b == 0) return a;
       return gcd(b, a % b);
   }
   

   该算法的时间复杂度是（ ）。
   {{ select(8) }}

• O(a)
• O(b)
• O(log min(a,b))
• O(ab)

判断题

9. 下面 C++ 代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，a 大于 b 还是小于 b 都适用。

   int gcd(int a, int b) {
       if (a % b == 0) return b;
       return gcd(b, a % b);
   }
   

   {{ select(9) }}

• 正确
• 错误

10. 假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。

    int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
    

    {{ select(10) }}

• 正确
• 错误