算法|最大公约数

本文主要是介绍算法|最大公约数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

完成阅读您将会了解最大公约数二进制方法的：

1. 算法思想
2. 实现步骤
3. 实践范例（C++/Rust）

1. 算法思想

最大公约数（Greatest Common Divisor）的二进制求解算法基于三个基本定理：
对于任意给定的两个不等正整数\(a\)与\(b\)有，

1. 若\(a\)，\(b\)同为偶，\(a\)与\(b\)的最大公约数为\(\frac{a}{2}\)与\(\frac{b}{2}\)的最大公约数的两倍；
2. 若\(a\)奇\(b\)偶，\(a\)与\(b\)的最大公约数为\(a\)与\(\frac{b}{2}\)的最大公约数；
3. 若\(a\)，\(b\)同为奇，且\(a>b\)，\(a\)与\(b\)的最大公约数为\(\frac{a-b}{2}\)与\(b\)的最大公约数。

最大公约数的经典求解方法是欧几里得（Euclid）算法。众所周知，欧几里得算法中存在反复的取模运算（Modulo Operation），然而取模运算在计算机中属于开销较大的运算操作之一。最大公约数二进制求解方法通过移位避免了对数据直接取模，一定程度改善了运算性能。

与最大公约数相关联的还有最小公倍数（Least Common Multiple）。假设正整数\(a\)与\(b\)的最大公约数是\(c\)，那么其最小公倍数为\(\frac{a\times b}{c}\)。

2. 实现步骤

1. 将两个数分别右移至同为奇数，并记录各自移位次数；
2. 求两数差量，并将其右移至奇数，并以此更新较大的数；
3. 若两数不等，重复上一步；
4. 若两数相等，将其中一个数按初始两数移位较少的次数左移得到最大公约数。

3. 实践范例（C++/Rust）

问题描述：
给定正整数a，b，求其最大公约数c。
输入：a，b
输出：c
解答思路：
运用最大公约数二进制方法求解。

---

伪代码1：
变量说明：

\[\begin{aligned} &GCD(a,b) \\ &~~~~~~intialize ~~~m ~~~and~~~ n~~~ as~~~ 0 \\ &~~~~~~while~~~a~~~is~~~even \\ &~~~~~~~~~~~~shift~~~a~~~1~~~bit~~~right \\ &~~~~~~~~~~~~m\leftarrow m+1 \\ &~~~~~~while~~~b~~~is~~~even \\ &~~~~~~~~~~~~shift~~~b~~~1~~~bit~~~right \\ &~~~~~~~~~~~~n\leftarrow n+1 \\ &~~~~~~if~~~a<b \\ &~~~~~~~~~~~~swap(a,b) \\ &~~~~~~while~~~a>b \\ &~~~~~~~~~~~~a\leftarrow a-b \\ &~~~~~~~~~~~~while~~~a~~~is~~~even \\ &~~~~~~~~~~~~~~~~~~shift~~~a~~~1~~~bit~~~right \\ &~~~~~~~~~~~~if~~~a<b \\ &~~~~~~~~~~~~~~~~~~swap(a,b) \\ &~~~~~~shift~~~b~~~\min(m,n)~~~bits~~~left\\ &~~~~~~return ~~~b \end{aligned} \]

---

C++解答：

auto GCD(unsigned a, unsigned b) {
  if (a > 0 && b > 0) {
    auto m = 0, n = 0;
    while (++m, !(a & 1))
      a >>= 1;
    while (++n, !(b & 1))
      b >>= 1;
    while (a < b ? std::swap(a, b), true : a > b) {
      a -= b;
      while (!(a & 1))
        a >>= 1;
    }
    return b << std::min(m, n) - 1;
  }
  return 0;
}

Rust解答：

pub fn GCD(mut a: u32, mut b: u32) -> u32 {
    if a == 0 || b == 0 { return 0; }
    let (mut m, mut n) = (0, 0);
    while { m += 1; a & 1 == 0 } { a >>= 1; }
    while { n += 1; b & 1 == 0 } { b >>= 1; }
    while if a < b { swap(&mut a, &mut b); true } else { a > b } {
        a -= b;
        while a & 1 == 0 { a >>= 1; }
    }
    b << min(m, n) - 1
}

4. 自我测试

伪代码实践：
N/A

LeetCode选荐：
N/A

让每一天足够精致，期待与您的再次相遇! ^_^

这篇关于算法|最大公约数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！