前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定两个数 n1和n2，使用一行代码求的n1和n2的最小公因数
如：
n1 = 18, n2 = 12
结果为：6

解决方案

原问题：
辗转相除法：
两个数较大的数n1，较小的n2，
n1%n2 = m
再使用n2%m…如此辗转下去直到为0时，除数为最大公因数。

代码编写

java语言版本

原问题：
方法一:

   /*** 辗转相除法（欧几里得）* 原理：* 1、两个数一定是最大公约数的倍数没问题* 2、所以两个数的差值一定是最大公约数的倍数，也就是大数字比小数字多了几倍的公约数* 3、所以余数一定就是公约数的倍数并且倍数一定比n的公约数倍数小，否则商+1* 4、这时n大于余数，两个又都是公约数的倍数，所以问题变成了n和余数之间的最大公约数问题（辗转）* 5、n比余数大几个公约数呢？辗转到余数为一倍的公约数时，n此时一定是余数的倍数，这时公约数就是较小的那个数了* 图解：* ||||||||||| 12个* |||||||| 8个* 求最大公约数* 12 = 8 * 0 + 4* 此时12由3个4组成，8由2个4组成，余数由一个4组成* 8 = 4*2 + 0* 此时余数为0， 最小公约数为4* @param m* @param n* @return*/public static int gcd(int m, int n){return n == 0? m : gcd(n, m%n);}public static int gcdCp1(int m, int n) {return Math.max(m, n) % Math.min(m, n) == 0 ? Math.min(m, n) : gcdCp1(Math.min(m, n), Math.max(m, n) % Math.min(m, n));}public static void main(String[] args) {System.out.println(gcdCp1(22, 16));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

其实一句话求就是要求递归的求法，这里我给了两种解法，其实都是一样的，只不过思考的角度不太一样，首先第一种方式就是认为m是被除数，n是除数，由于余数一定都是小于除数的，所以我们递归的时候就使用除数作为下一轮的被除数，余数作为除数，刚好避免了比较大小，并且体现了辗转的特点，就是除数和余数之间的辗转相除。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！