本文共 1322 字，大约阅读时间需要 4 分钟。
JAVA算法：欧几里德算法(GCD)又称辗转相除法计算两个整数a,b的最大公约数（JAVA代码）
package com.bean.algorithmbasic;public class GDCDemo { /* * 欧几里德算法(GCD)又称辗转相除法，用于计算两个整数a,b的最大公约数。 * 基本思路：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。 * */ public static int gcd(int a, int b) { if (b==0) { return a; }else { return gcd(b,a%b); } } /* * 扩展算法 * * 基本思路：对于不全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数， * 必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。 * * 证明：设 a>b。 * 1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0； * 2，ab!=0 时，设 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b); * 根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b); * 则:ax1+by1=bx2+(a mod b)y2; * 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; * 根据恒等定理得：x1=y2; y1=x2-(a/b)*y2; * 这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2 * 上面的思想是以递归定义的，因为 gcd不断的递归求解一定会有个时候 b=0，所以递归可以结束。 * * */ public static int[] egcd(int a,int b) { int[] array=new int[2]; if(b==0) { array[0]=1; array[1]=0; return array; }else { array=egcd(b,a%b); array[0]=array[1]; array[1]=array[0]-a/b*array[1]; return array; } } public static void main(String[] args) { // TODO Auto-generated method stub int x=8; int y=12; int result=gcd(x,y); System.out.println("RESULT is: "+result); int[] array=egcd(x,y); System.out.println("RESULT is: "+array[0]+"\t"+array[1]); }} 程序运行结果：
RESULT is: 4
RESULT is: 0 0
转载地址：http://dntdi.baihongyu.com/