[题解]《C语言入门100例》(第22例) 辗转相除法

[题解]《C语言入门100例》(第22例) 辗转相除法

文章目录

• 一. 辗转相除法
• • 1.1 公式
  • 1.2 证明
• 二. 相关练习
• • 2.1 找出数组的最大公约数

一. 辗转相除法

  辗转相除法又称欧几里得算法，是用来求两个数之间的最大公约数的算法。

1.1 公式

例如：

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)

所以1997与615的最大公约数就是1。
公式：

gcd(a, b) = gcd(b, a % b)

1.2 证明

  假设我们要求a,b两个数的最大公约数（a >= b），则我们可以得到如下式子：

a = [a / b] * b + a % b

其中[ ] 是向下取整的意思。
我们令k = [a / b]，m = a % b，则可得：

a = k * b + m => m = a - k * b

我们假设c 是a和b的一个公约数，两边同时除c
得：

m / c = a / c - k * b / c

通过分析我们可知，a / c 和 k * b / c都是整数，所以 m / c也是整数。
以此得证a,b的公约数与b, a % b的公约数一样，所以

gcd(a,b) = gcd(b, a % b)

得证。

二. 相关练习 2.1 找出数组的最大公约数

题目链接：
1979. 找出数组的最大公约数

分析：

首先我们要遍历数组，找出最大值和最小值，然后再根据公式gcd(a,b) = gcd(b, a%b)求他们的最大公约数。

代码如下：

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

int findGCD(int* nums, int numsSize){
    int max = INT_MIN;
    int min = INT_MAX;
    for(int i = 0; i < numsSize; i++){
        if(max < nums[i]){
            max = nums[i];
        }
        if(min > nums[i]){
            min = nums[i];
        }
    }
    return gcd(max, min);
}