GCD算法的学习

GCD算法的学习

学习了前辈wzx15927662183的文章GCD算法精讲-CSDN博客

介绍

GCD通常用来求两个数的最大公约数

算法的核心：gcd(a,b) = gcd(b,a % b)

证明的思路：

证明 gcd(a, b) = gcd(b, a % b) 的思路：
设 a > b
1. 构造 a % b : 设 r = a % b, 即 a = kb + r (r < b)
2. 构造 a, b的公约数： 设 d 为 a, b的公约数，记作 d | a, d | b
3. 联系要证明的式子 ： a = kb + r 两边同时处以 d, 稍作移动，得 a / d - kb / d = r / d由于 d | a 且 d | b故得到 d | r，即 d | (a % b)所以 d 是 a、b、a % b的公约数。我们只需要通过迭代 / 递归 找到 gcd(b, a % b) 即可

模版

递归版

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

迭代版

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

例题

1. easy: 1979.找出数组的最大公约数