算法|最大公约数

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

  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

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

上一篇:rust 大神crypto2的例子AES加解密


下一篇:Rust IO 操作简介