欧几里得算法（辗转相除法）

迈不过友情╰ 2023-07-13 15:28 119阅读 0赞

算法是程序的灵魂，不懂算法的程序员不是一个合格的程序员。

源自LeetCode上的一道算法题，说实话，我已经忘记欧几里得算法是怎么实现的了。。。

## **简介：** ##

欧几里得算法（又称辗转相除法），旨在解决求两个正整数的最大公约数的算法。

计算公式**gcd(a,b) = gcd(b,a mod b)**

**编码实现：**

**c语言（参考百度百科）**

/*
    欧几里德算法：辗转求余
    原理： gcd(a,b)=gcd(b,a mod b)
    当b为0时，两数的最大公约数即为a
    getchar()会接受前一个scanf的回车符
    */
    #include<stdio.h>
    unsigned int Gcd(unsigned int M,unsigned int N)
    {
        unsigned int Rem;
        while(N > 0)
        {
            Rem = M % N;
            M = N;
            N = Rem;
        }
        return M;
    }
    int main(void)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        printf("the greatest common factor of %d and %d is ",a,b);
        printf("%d\n",Gcd(a,b));
        return 0;
    }

**c++实现（参考百度百科）**

#include <algorithm> // std::swap for c++ before c++11
    #include <utility> // std::swap for c++ since c++11
    int gcd(int a，int b)
    {
        if (a < b)
            std::swap(a, b);
        return b == 0 ? a : gcd(b, a % b);
    }

## LeetCode题目 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyNjQyMjM5_size_16_color_FFFFFF_t_70][]

自己折腾了一下，写了比较繁重的代码实现，不忍直视，简洁度和复杂度都与精辟答案无法比较，这里采纳评论区的一位coder的答案学习

class Solution {
    public:
       inline int gcd(int a, int b) {return b == 0? a : gcd(b , a % b);}
    
        string gcdOfStrings(string str1, string str2) 
        {
            if (str1 + str2 != str2 + str1) return "";
            return str1.substr(0, gcd(str1.size(), str2.size()));
        }
    };

**总结：**通过这一道题目，首先我了解了这个算法，知道这个算法的基本历史，基本原理，以及略微感受到的思想，这道题目也算是这个算法的一种实用，算法思想是一样的。算法我感觉也是一种工具，只有用熟练了才可以领悟的更深。

参考资料：leetcode，百度百科

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyNjQyMjM5_size_16_color_FFFFFF_t_70]: /images/20230529/ad7d1b4748874575877684b31f254d71.png