Loading... 一个比较简单的算法,这里记录一下相关笔记。 最大公约数是指能够整除多个整数的最大正整数(这里面多个整数不能都为0)例如6和4的最大公约数就是2,13和3的最大公约数是1。 ## 算法实现 平时用的时候如果是C++,那么std库里面就已经有这个函数了,直接调用就行。具体可以看`std::gcd`的用法。比较常见的实现方式是: ```C++ int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } ``` 这里采用的是辗转相除法,两数相除取余数和除数继续相除,直到余数为0,这时前一个余数就是最大公约数。举个例子: 252和105,求最大公约数: 首先第一步,$252 \mod 105 = 147$。下一步要用余数和除数继续相除,因为$147 > 105$所以$147$在下一步要继续当被除数。 第二步,$147 \mod 105 = 42$,得到余数$42$,因为$42$小于$105$,所以下一步需要$105$当被除数,$42$当除数。 第三步,$105 \mod 42 = 21 $,得到余数$21$。 最后一步,$42 \mod 21 = 0$,取上一步的余数$21$,就是最大公约数。 这里解释一下,实际上`y`充当的是求余之后的结果,当求余结果等于0的时候那么说明已经不需要继续递归下去了,直接取上一次求余的结果,就可以得到最大公约数,而刚好`x`存放的就是上一次传入的y(此时假设已经在递归中),即`x%y`,上一次求余的结果,因此在当前`y`为0时应当返回`x`。 ## 参考资料 1. [C++ 中的 std::gcd 函数](https://www.delftstack.com/zh/howto/cpp/cpp-gcd/) 2. [辗转相除法](https://zh.wikipedia.org/zh-hans/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95) 最后修改:2022 年 02 月 10 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 随缘