GESP 5级客观题｜最大公约数与最小公倍数｜课后作业

考试频率：高频。本卷共 6 题。

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

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

{{ select(1) }}

• 对
• 错

2. 辗转相除法用于求两个整数的最大公约数。

   {{ 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. 以下代码计算两个正整数的最大公约数(GCD)，横线上应填写( )。

int gcd0(int a, int b){    
    if(a< b){        
        swap(a, b);    
    }    
    while(b!= 0){        
        int temp= a% b;        
        a= b;        
        b= temp;    
    }    
    return______; 
}

{{ select(4) }}

• b
• a
• temp
• a * b

5. 假设函数 gcd() 能正确求两个正整数的最大公约数，则下面的 findMusicalPattern(4，6) 函数返回2。

void findMusicalPattern(int rhythm1, int rhythm2){    
    int commonDivisor= gcd(rhythm1, rhythm2);    
    int patternLength=(rhythm1* rhythm2)/ commonDivisor;    
    return patternLength； 
}

{{ select(5) }}

• 正确
• 错误

6. 两块长方形土地的长宽分别为 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(6) }}

• 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)