2.求两个数的最大公约数

题目:求两个数的最大公约数

方式一：使用辗转相除法求两个数的最大公约数

辗转相除法.png

具体代码如下:
这里有两个问题？
问题1: 为什么while循环用b，不用余数temp
问题2: b 是最大公约数,为什么最后返回的是a;
while循环一直在做一件事，不停的把b赋值给a,不停的把余数temp赋值给b

//  最大公约数（greatest common divisor)
int gcd(int a,int b)
{
    int temp = 0; //中间变量
    if(a<b){ // 保证大数在前，小数在后，永远都是计算:大数%小数的余数
        temp = a;
        a = b;
        b = temp;
    }
    
    while (b!=0) { //  如果余数不为0(应为总是会将余数的值赋值给b,所以这里用b作为判断条件),一直循环;如果余数为0，a就是最大公约数
        temp = a%b; // 计算a%b的余数
        a = b; // 把b赋值给a
        b = temp; // 让余数等于b
    }
    return a; // 循环结束后
}

方式二:辗转相除法求两个数的最大公约数

2.相减法.png

转换为代码:

// 怎么转化为代码
int gcd2(int a, int b)
{
    while (a!=b) {
        if(a>b)
        {
            a=a-b;
        }else{
            b = b-a;
        }
    }
    return a;
}

方式三:穷举法,求两个数的最大公约数

最直接，最好理解，效率最低一种方式
就是一个个的试:取两个数中的较小的数temp，对较小的数进行求余运算，同时temp-- ；直到余数都为0时，结束循环，此时temp就是两个数的最大公约数。

3.穷举法.png

// 穷举法求两个数的最大公约数
int gcd(int a,int b)
{
    int temp=0; // 定义一个中间变量temp
    a>b?(temp = b):(temp =a); // 让temp等于两个数中较小的哪一个数
    
    while (a%temp || b%temp) { // 两个数分别对temp求余数。同时temp--
        temp--;
    }
    return temp;
}