「算法」求最大公约数

最大公约数定义: 两个不全为0的非负整数m和n的最大公约数记为 gcd(m, n) , 代表能整除m和n的最大正整数。

算法1: 辗转相除法/欧几里得算法

举例来说

算法步骤:

  • 第一步:如果n==0,返回m的值,流程结束
  • 第二步:m 除以 n,将余数赋值给r
  • 第三步:n赋值给m,r赋值给n,返回第一步

算法一定会结束吗?会出现死循环吗?

不难发现这个流程一定会结束,不会出现死循环:

第二个算子是 m%n , 它永远不可能为负数,并且,每一轮计算过后,它都会减小,所以它一定会达到0

实现这个算法

方法1

// 递归写法
func gcd(a, b int) int{

    if b == 0 {
        return a
    }
    return gcd(b, a % b)
}

方法2

// 非递归写法
func gcd2(a, b int) int {

    for b != 0 {
        temp := a % b
        a = b // a = b
        b = temp // b = a%b
    }
    return a
}

方法3

不用临时变量temp

func gcd2_2(a, b int) int {
    // 用异或交换
    for b != 0 {
        a %= b // a = a % b
        b ^= a // b = a%b ^ b
        a ^= b // a = a%b ^b ^ a%b = b
        b ^= a // b = b ^ a%b ^ b == a%b
    }
    /*
    其他语言可以写的更简洁
    while( b ^= a ^= b ^ a %= b );
    return a;
     */
    return a
}

辗转相除法,每轮计算都可以把数字缩小一定的范围,时间复杂度为指数级别,但每次计算都需要去模运算,当数字较大时,模运算可能会很消耗性能

算法2: 更相减损术

m > n 时:

算法步骤:

  • 第一步:如果n==m,返回m的值,流程结束
  • 第二步:m - n,将绝对值赋值给r
  • 第三步:r赋值给m,n 中较大的那个,较小的那个不变,返回第一步

方法1

func gcd3(a, b int) int{
    // 更相减损术
    if a == b{
        return a
    }else if a > b {
        return gcd(a-b, b)
    }else{
        return gcd(b-a,a)
    }
}

此方法虽然避免了模运算,但需要运算的次数较多。可以考虑分情况讨论来减少运算次数

  • m,n 均为偶数:2一定是它们的公约数, 只需考虑 gcd(m/2, n/2) 。 最后结果为 2 * gcd(m/2, n/2)
  • m 为偶数,n为奇数: 2一定不是它们的公约数,只需考虑 gcd(m/2, n) .最后结果为 gcd(m/2, n)
  • m 为奇数,n为偶数: 2一定不是它们的公约数,只需考虑 gcd(m, n/2) .最后结果为 gcd(m, n/2)
  • m,n 均为奇数,无法用2来优化,只能老老实实走流程

方法2

// 继续优化
func gcd3_2(a, b int) int{
    if a == b{
        return a
    }
    if a %2 == 0 && b %2 == 0 {
        // 两个都是偶数
        return 2 * gcd3_2(a/2, b/2)
    }else if a %2 == 0 && b%2 != 0{
        return gcd3_2(a/2, b)
    }else if a %2 != 0 && b%2 == 0{
        return gcd3_2(a, b/2)
    }else{
        if a > b {
            return gcd3_2(a-b, b)
        }else{
            return gcd3_2(b-a, a)
        }
    }
}

无法遇到了第四种情况,都是奇数,会不会退化为方法1 ?

不会,因为两个奇数之差 a-b / b-a 一定为偶数,第四种情况的下一轮一定是第二或第三种情况。

方法3

// 进一步优化,去掉模运算 ,用位运算替代
// 乘法除法也用位运算
func gcd3_3(a, b int) int{
    // 更相减损术
    if a == b{
        return a
    }
    if (a&1) == 0 && (b&1) == 0 {
        // 两个都是偶数
        return gcd3_3(a>>1, b>>1) << 1
    }else if (a&1) == 0 && (b&1) != 0{
        return gcd3_3(a>>1, b)
    }else if (a&1) != 0 && (b&1) == 0{
        return gcd3_3(a, b>>1)
    }else{
        if a > b {
            return gcd3_3(a-b, b)
        }else{
            return gcd3_3(b-a, a)
        }
    }
}

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

「面试」腾讯 下一篇