详解“辗转相除法”(如何求最大公约数)

本篇博客来讲一讲学习C语言过程中遇到的一种解法——辗转相除法

首先我会介绍辗转相除法的概念,然后会用一道例题进行运用,最后会进行总结

一、辗转相除法的概念

辗转相除法又称欧几里得算法辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。

由概念可知,该算法主要是用于两个非负整数的最大公约数,那么如何求呢,请看下文分析

二、如何利用辗转相除法求两个数的最大公约数

这里先看代码:

int main()
{
    int m = 0;
    int n = 0;
    scanf("%d %d", &m, &n);
    int k = 0;
    while (k = m % n)
    {
        m = n;
        n = k;
    }
    printf("%dn", n);

    return 0;
}

所谓辗转,指的就是把 m % n 赋给k,把 n 赋给 m ,最后再把 k 赋给 n ,直到 k 为零的时候,while循环也会刚好停下,此时的 k 就是 m 和 n 的最大公约数了。

这样说属实有点绕,请C友们结合我画的思路图理解一下:

另外,辗转相除法相较于传统写法,有一个较大的优点就是:辗转相除法不用去求 m 和 n 哪个大哪个小,下面请看我用一幅图给大家解释清楚:

这里大家应该就能理解到我说的不用管 m 和 n 谁大谁小了吧,因为就算取模的数比较小(即“较小数”%“较大数”),辗转相除法会自动把两个数交换位置,变成这样子:“较大数” % “较小数”

 三、总结

辗转相除法是用于求两个非负整数的最大公约数的高效方法

这种方法可以不用去计算两个数谁大谁小,这样能够提高运算效率

具体还是看我上面的手绘图加深一下理解

这就是本篇博客的全部内容啦,如果有不足之处欢迎在评论区指出哦!