题目陈述

题目大意：求正整数a,b的最大公约数x
仔细审题：最大公约数，即不存在一个比x大，且同时能整除整数a,b的正整数

算法一：暴力做法

算法思路

  1. 设mi=min(a,b),即mi为a,b中较小的那个数字
  2. for循环暴力求解，i从1开始循环，到mi截至（因为不存在因数比原数字大的情况），如果能整除，则将i记录到c中
  3. 最后返回c，因为i是递增的，最后返回的也一定是最大的那个数字
  4. 时间复杂度为,这边a,b最大可以到1e9，但是数据很弱，我试了一下，特判a,b是否能整除对方的情况，再for循环，可以AC……（还是学正解吧）

    代码实现

    class Solution {
public:
 int gcd(int a, int b) {
     int c=1,mi=min(a,b);//Mi为a,b中较小的那个数
     if(a%b==0)return b;//判断一个数是否是另一个数字的整数倍
     if(b%a==0)return a;
     for(int i=2;i<=mi;i++){
         if(a%i==0&&b%i==0){//i为ab的公约数
             c=i;
         }
     }
     return c;
 }
};

    算法二：辗转相减法

    算法思路

    1、（先讲思路，待会给大家简单证明一下算法的正确性）
    2、此处设a>b，gcd(a,b)表示为a,b的最大公约数，求解gcd(a,b)，等价于求解gcd(b,a- b)，当其中一个数为0的时候，即gcd(a,0)，答案就是a
    3、递归反复执行上述操作，就能得到gcd(a,b)

    证明：算法正确性

  • 设
  • 设有整数x，若,，设,则那么有，即，
  • 即a,b的约数也是c的约数，所以a,b的gcd,也必然是c的约数
  • 算法正确性得证
  1. 但是理论上来说，这个算法的时间复杂度依旧可以达到O(n),博主造了一组数据（不用数了，9个零），这种情况，我们就需要执行次操作，依旧会超时
  2. 但是题目数据很弱，程序还是过了……（过了不代表对哦，还是需要学会正解）
  3. 时间复杂度,此处肯定有同学好奇了，这个算法怎么比上一个算法时间复杂度还大？那我学他干嘛？
  4. 注意，O(***)代表的是最坏时间复杂度，我们一般分析的是最坏时间复杂度，但是一般情况下，我们遇到的平均时间复杂度，可以理解为算法2大部分情况比算法1优，但是在某种情况下面他甚至没有算法1优

    代码实现

    class Solution {
public:
 int gcd(int a, int b) {
    if(a<b)swap(a,b);//保证a比b大,不然就会出现a-b是负数，gcd（a,b）等价于gcd(b,a)
     return !b?a:gcd(b,a-b);//b为0返回a，否则返回a-b
 }
};

    算法三：辗转相除法

    算法思路

  5. 相比于前两个算法，这个算法已经足以过掉任何强的数据了
  6. ，直到b为0的时候,a即为答案,如何理解呢？
  7. 这边就不数学证明了，毕竟对于刚开始学习算法的小白，我们可以基于上面的证明“感性理解”，毕竟有些东西证明不需要特别严谨。
  8. 在上面的算法二中,对于gcd(9,2),会执行，(下面省略交换a,b的过程，默认大的数字在前面)最后返回1，
  9. 我们会发现前面一直执行这个减去2的操作，很耗时间，最后要取到的1,不过是9除以2的余数，即9%2,所以这一过程我们用a%b来代替a-b
  10. 不难理解，算法二中，什么时候会交换a,b？即反复执行a-b，直到a比b小的情况，那么这个不就是，a除以b的余数吗？
  11. 时间复杂度，有一篇论文证明过，过于繁琐，此处不展开，有兴趣的同学建议上网百度

    动画演示

    图片说明

代码实现

C++

class Solution {
public:
    int gcd(int a, int b) {
        return !b?a:gcd(b,a%b);
        //为a<b的情况，a%b依旧等于，即gcd(b,a%b)<==>gcd(b,a)相当于交换a,b，所以此处不用写swap
    }
};

Python

class Solution:
    def gcd(self , a , b ):
        if b==0:
            return a
        else :
            return self.gcd(b,a%b)