本篇博客来讲一讲学习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("%d\n", n); return 0; }讯享网
所谓辗转，指的就是把 m % n 赋给k，把 n 赋给 m ，最后再把 k 赋给 n ，直到 k 为零的时候，while循环也会刚好停下，此时的 n 就是 m 和 n 的最大公约数了。
这样说属实有点绕，请C友们结合我画的思路图理解一下：
【笔误👆】故24和28的最大公约数为6
另外，辗转相除法相较于传统写法，有一个较大的优点就是：辗转相除法不用去求 m 和 n 哪个大哪个小，下面请看我用一幅图给大家解释清楚：
这里大家应该就能理解到我说的不用管 m 和 n 谁大谁小了吧，因为就算取模的数比较小（即“较小数”%“较大数”），辗转相除法会自动把两个数交换位置，变成这样子：“较大数” % “较小数”
三、总结
辗转相除法是用于求两个非负整数的最大公约数的高效方法
这种方法可以不用去计算两个数谁大谁小，这样能够提高运算效率
具体还是看我上面的手绘图加深一下理解
这就是本篇博客的全部内容啦，如果有不足之处欢迎在评论区指出哦！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/124430.html