Java: obtener máximo común divisor
-
25-09-2019 - |
Pregunta
I han visto que existe tal función para BigInteger
, es decir, BigInteger#gcd
. ¿Hay otras funciones en Java que también trabajan para otros tipos (int
, long
o Integer
)? Parece que esto tendría sentido como java.lang.Math.gcd
(con todo tipo de sobrecargas), pero no está allí. Es en otra parte?
(no confundir esta pregunta con "¿Cómo se implementa esto mismo", por favor!)
Solución
Para int y largo, como primitivas, no realmente. Para Entero, es posible que alguien escribió uno.
Dado que BigInteger es un superconjunto (matemática / funcional) de Int, Integer, largo y largo, si es necesario utilizar estos tipos, convertirlos a un BigInteger, hacer el MCD, y convertir la parte posterior resultado.
private static int gcdThing(int a, int b) {
BigInteger b1 = BigInteger.valueOf(a);
BigInteger b2 = BigInteger.valueOf(b);
BigInteger gcd = b1.gcd(b2);
return gcd.intValue();
}
Otros consejos
Por lo que yo sé, no hay ningún método integrado para primitivas. Sin embargo, algo tan simple como esto debe hacer el truco:
public int GCD(int a, int b) {
if (b==0) return a;
return GCD(b,a%b);
}
Puede también una línea que si usted está en ese tipo de cosas:
public int GCD(int a, int b) { return b==0 ? a : GCD(b, a%b); }
Debe tenerse en cuenta que no hay absolutamente no diferencia entre los dos que compilan con el mismo código de bytes.
O el algoritmo de Euclides para calcular el MCD ...
public int egcd(int a, int b) {
if (a == 0)
return b;
while (b != 0) {
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}
El uso de Guayaba LongMath.gcd()
y IntMath.gcd()
Jakarta Commons Matemáticas tiene exactamente eso.
A menos que tenga la guayaba, que definen así:
int gcd(int a, int b) {
return a == 0 ? b : gcd(b % a, a);
}
Se puede utilizar esta aplicación de binario GCD algoritmo
public class BinaryGCD {
public static int gcd(int p, int q) {
if (q == 0) return p;
if (p == 0) return q;
// p and q even
if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;
// p is even, q is odd
else if ((p & 1) == 0) return gcd(p >> 1, q);
// p is odd, q is even
else if ((q & 1) == 0) return gcd(p, q >> 1);
// p and q odd, p >= q
else if (p >= q) return gcd((p-q) >> 1, q);
// p and q odd, p < q
else return gcd(p, (q-p) >> 1);
}
public static void main(String[] args) {
int p = Integer.parseInt(args[0]);
int q = Integer.parseInt(args[1]);
System.out.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
}
}
http://introcs.cs.princeton.edu/java /23recursion/BinaryGCD.java.html
Algunas implementaciones aquí no están funcionando correctamente si ambos números son negativos. gcd (-12, -18) es 6, no -6.
Así que un valor absoluto debe ser devuelto, algo así como
public static int gcd(int a, int b) {
if (b == 0) {
return Math.abs(a);
}
return gcd(b, a % b);
}
podemos utilizar la función recursiva para encontrar mcd
public class Test
{
static int gcd(int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver method
public static void main(String[] args)
{
int a = 98, b = 56;
System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
}
}
Si está utilizando Java 1.5 o posterior, entonces este es un algoritmo iterativo que GCD binaria usos Integer.numberOfTrailingZeros()
para reducir el número de controles e iteraciones requeridas.
public class Utils {
public static final int gcd( int a, int b ){
// Deal with the degenerate case where values are Integer.MIN_VALUE
// since -Integer.MIN_VALUE = Integer.MAX_VALUE+1
if ( a == Integer.MIN_VALUE )
{
if ( b == Integer.MIN_VALUE )
throw new IllegalArgumentException( "gcd() is greater than Integer.MAX_VALUE" );
return 1 << Integer.numberOfTrailingZeros( Math.abs(b) );
}
if ( b == Integer.MIN_VALUE )
return 1 << Integer.numberOfTrailingZeros( Math.abs(a) );
a = Math.abs(a);
b = Math.abs(b);
if ( a == 0 ) return b;
if ( b == 0 ) return a;
int factorsOfTwoInA = Integer.numberOfTrailingZeros(a),
factorsOfTwoInB = Integer.numberOfTrailingZeros(b),
commonFactorsOfTwo = Math.min(factorsOfTwoInA,factorsOfTwoInB);
a >>= factorsOfTwoInA;
b >>= factorsOfTwoInB;
while(a != b){
if ( a > b ) {
a = (a - b);
a >>= Integer.numberOfTrailingZeros( a );
} else {
b = (b - a);
b >>= Integer.numberOfTrailingZeros( b );
}
}
return a << commonFactorsOfTwo;
}
}
Unidad de prueba:
import java.math.BigInteger;
import org.junit.Test;
import static org.junit.Assert.*;
public class UtilsTest {
@Test
public void gcdUpToOneThousand(){
for ( int x = -1000; x <= 1000; ++x )
for ( int y = -1000; y <= 1000; ++y )
{
int gcd = Utils.gcd(x, y);
int expected = BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).intValue();
assertEquals( expected, gcd );
}
}
@Test
public void gcdMinValue(){
for ( int x = 0; x < Integer.SIZE-1; x++ ){
int gcd = Utils.gcd(Integer.MIN_VALUE,1<<x);
int expected = BigInteger.valueOf(Integer.MIN_VALUE).gcd(BigInteger.valueOf(1<<x)).intValue();
assertEquals( expected, gcd );
}
}
}
public int gcd(int num1, int num2) {
int max = Math.abs(num1);
int min = Math.abs(num2);
while (max > 0) {
if (max < min) {
int x = max;
max = min;
min = x;
}
max %= min;
}
return min;
}
Este método utiliza el algoritmo de Euclides para obtener el "máximo común divisor" de dos enteros. Se recibe dos enteros y devuelve el máximo común divisor de ellos. así de fácil!
/*
import scanner and instantiate scanner class;
declare your method with two parameters
declare a third variable;
set condition;
swap the parameter values if condition is met;
set second conditon based on result of first condition;
divide and assign remainder to the third variable;
swap the result;
in the main method, allow for user input;
Call the method;
*/
public class gcf {
public static void main (String[]args){//start of main method
Scanner input = new Scanner (System.in);//allow for user input
System.out.println("Please enter the first integer: ");//prompt
int a = input.nextInt();//initial user input
System.out.println("Please enter a second interger: ");//prompt
int b = input.nextInt();//second user input
Divide(a,b);//call method
}
public static void Divide(int a, int b) {//start of your method
int temp;
// making a greater than b
if (b > a) {
temp = a;
a = b;
b = temp;
}
while (b !=0) {
// gcd of b and a%b
temp = a%b;
// always make a greater than b
a =b;
b =temp;
}
System.out.println(a);//print to console
}
}
He utilizado este método que creé cuando tenía 14 años de edad.
public static int gcd (int a, int b) {
int s = 1;
int ia = Math.abs(a);//<-- turns to absolute value
int ib = Math.abs(b);
if (a == b) {
s = a;
}else {
while (ib != ia) {
if (ib > ia) {
s = ib - ia;
ib = s;
}else {
s = ia - ib;
ia = s;
}
}
}
return s;
}
Es otro lugar?
Apache -! que tiene tanto mcd y mcm, así enfriar
Sin embargo, debido a la profundidad de su aplicación, es más lento en comparación con la versión simple escrito a mano (si es importante).
Esas funciones GCD proporcionadas por Commons-Math y guayaba tiene algunas diferencias.
- Commons-Math lanza un
ArithematicException.class
sólo paraInteger.MIN_VALUE
oLong.MIN_VALUE
.- Si no, maneja el valor como un valor absoluto.
- Guayaba lanza una
IllegalArgumentException.class
para cualquier valor negativo.
El% nos va a dar el máximo común divisor entre dos números, que significa: -
% O mod de big_number / small_number son = gcd,
y lo escribimos en java como esto big_number % small_number
.
EX1: de dos números enteros
public static int gcd(int x1,int x2)
{
if(x1>x2)
{
if(x2!=0)
{
if(x1%x2==0)
return x2;
return x1%x2;
}
return x1;
}
else if(x1!=0)
{
if(x2%x1==0)
return x1;
return x2%x1;
}
return x2;
}
EX2: por tres números enteros
public static int gcd(int x1,int x2,int x3)
{
int m,t;
if(x1>x2)
t=x1;
t=x2;
if(t>x3)
m=t;
m=x3;
for(int i=m;i>=1;i--)
{
if(x1%i==0 && x2%i==0 && x3%i==0)
{
return i;
}
}
return 1;
}