本人菜鸟一枚，突然之间，偶得上帝灵光闪现，突然感觉自己日子过的太轻松，然后，自杀式的买了一本算法书，从今天开始了地狱般的生活；
算法第一章讲的是，欧几里得算法求其目的就是找到两个数的最大公约数，然后，我马上关上书，喝了一杯茶，脑海中回想着，这都是啥？？对于一个数学从来都没有及格的我来说，想放弃
这。。。。是啥？没看懂
其实，最大公约数，即为能够同时被两个整数除的最大的数，还不懂？上图
如果还不懂，请关闭本页面，然后，打开百度，找个视频看一下吧！我无能为力了。
欧几里得算法：又称辗转相除法，用于计算两个正整数，a,b的最大公约数，计算原理依赖于下面的定理
定理：gcd(a,b) = gcd(b,a mod b)(a>b且a mod b不为0)
有人会问，mod是啥？这个是求余啊！ MOD是求余运算符，例如a mod b=c，表明a除以b余数为c
证明：a 可以表示成a = kb +r 则 r=a mod b
假设 d是a,b的一个公约数，则有 d|a ,d|b 而，r=a-kb 因此d|r
因此d也是(b,a mod b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，最大的公约数也必然相等
看懂没？我也没咋看懂
分析一下吧，
假设x>y x和y的最大公约数用 f(x,y)表示
假设 x/y = a
x%y = b
所以 a*y+b = x
因为a为x除以的整数部分，b为x除以y的余数部分，所以 a*y+b = x
将上面的调换一下 b= x-a*y
因为x和y都能被f(x,y)整数 所以f(x,y)是x和y的最大公约数
所以b也同样能被f(x,y)整除 即x和y的最大公约数f(x,y)它是b的约数，所以求x和y的最大公约数也就相当于求y和b的最大公约数（因为，这里x>y 而且 x%y肯定小于y，所以，这样一来，我们的范围缩小了）
所以 欧几里得公式也就这么来了
f(x,y) = f(y,x%y)
所以，这个算法就是不停的迭代，直到找出x%y=0的时候，停止迭代，那个时候，最大的公约数就是y了
下面为，书中的一个求最大公约数的案例
/** * 算法分析： * 计算两个非负数p和q的最大公约数，若q是0，则最大的公约数是p，否则，p除q，得到余数r，p和q最 * 大公约数即为q和r的最大公约数 * Created by huxd on 2017/9/14. */ //欧几里得算法 public static int gcd(int p ,int q){ if(q == 0) return p; int r = p%q; return gcd(q,r); } |
实际代码
package Test1; import java.util.*; public class Tset1 { public static void (String[] args) { Scanner scan = new Scanner(System.in);// 接收控制台输入的信息 System.out.print("请输入第一个整数："); int x = scan.nextInt(); // 取出控制台输入的信息 System.out.print("请输入第二个整数："); int y = scan.nextInt(); // 取出控制台输入的信息 System.out.println(gcd(x, y));// 调用maxCommonDivisor()方法 } public static int gcd(int x, int y) { // 防止输入为0 if (x == 0 || y == 0) { return 0; } //添加一个保证 x>y if (x < y) { int temp = x; temp = y; y = x; } //算法实现 if (x % y == 0) { return y; } else { return gcd(y, x % y); } } } |
