C语言经典算法（一）——求最大公约数的四种方法

痛定思痛。 2022-06-03 05:26 168阅读 0赞

今后继续整理算法并写出自己的理解和备注。  
C++实现的：最大公约数。C语言或其他语言同理。  
多回头看看 很有帮助。

1、 最大公约数  
<1> 题目描述:求解两个整数(不能是负数)的最大公约数(要求两数不能同时为0)  
<2> 方法一:穷举法  
<3> 方法二:相减法  
<4> 方法三: 欧几里德辗转相除法  
<5> 方法四: 欧几里德辗转相除法 递归实现

源码：  
一、 最大公约数  
1、 穷举法

#include<iostream>
    using namespace std;
    unsigned long GCD(unsigned long a, unsigned long b)
    {
        if(a == 0)
            return b;
        else if(b == 0)
            return a;
        else if(a == b)
            return a;//判断边界条件，任何一个数为0，返回另外一个数
    
        unsigned long gcd;
        gcd = a>b?b:a;//取出较小的一个
        while(gcd > 1)
        {
            if((a%gcd==0) && (b%gcd==0))
                return gcd;
            gcd--;
        }
        return gcd;
    }
    void main()
    {
        unsigned long a,b;
        cout<<"请输入a 和b:>";
        cin>>a>>b;
        unsigned long gcd = GCD(a,b);
        cout<<"gcd = "<<gcd<<endl;
    }

2、 相减法

#include<iostream>
    using namespace std;
    unsigned long GCD(unsigned long a, unsigned long b)
    {
        if(a == 0)
            return b;
        else if(b == 0)
            return a;
        else if(a == b)
            return a;
        unsigned long gcd;
        while(a != b)
        {
            gcd = a > b ? (a-=b) : (b-=a);//较大的减去较小的 直到两个数相等
        }
        return gcd;
    }
    void main()
    {
        unsigned long a,b;
        cout<<"请输入a 和b:>";
        cin>>a>>b;
        unsigned long gcd = GCD(a,b);
        cout<<"gcd = "<<gcd<<endl;
    }

3、 欧几里德辗转相除法

#include<iostream>
    using namespace std;
    unsigned long GCD(unsigned long a, unsigned long b)
    {
        if(a == 0)
            return b;
        else if(b == 0)
            return a;
        else if(a == b)
            return a;
        unsigned long mod = a % b;
        while(mod != 0)//辗转相除余数为0时则是最大公约数；即使a<b，如a=15,b=27,经过多循环一次，会修正为a=27,b=15
        {
            a = b;//小的赋值给大的
            b = mod;//余数赋值给小的
            mod = a % b;//求余
        }
        return b;
    }
    void main()
    {
        unsigned long a,b;
        cout<<"请输入a 和b:>";
        cin>>a>>b;
        unsigned long gcd = GCD(a,b);
        cout<<"gcd = "<<gcd<<endl;
    }

4、 欧几里德辗转相除法 递归实现

#include<iostream>
    using namespace std;
    unsigned long GCD(unsigned long a, unsigned long b)
    {
        if(b == 0)
            return a;//理解 b的含义 a%b之后模为0，赋值给b，代表辗转相除循环结束，输出a的值即是最大公约数。 
        else
            return GCD(b, a%b);//简便版的辗转相除法 需要理解
    }
    void main()
    {
        unsigned long a,b;
        cout<<"请输入a 和b:>";
        cin>>a>>b;
        unsigned long gcd = GCD(a,b);
        cout<<"gcd = "<<gcd<<endl;
    }

> 引用《每周算法》