Algoritmo de Euclides

Foros de discusión -> Básico

Lun May 08, 2006 12:37 pm

dacons
Perlero Nuevo

Registrado: 27 Feb 2006
Mensajes: 48

Algoritmo de Euclides

Hola, ¿alguien sabe como se resuelve el mcd al reves? si c=mcd(a,b) ¿como se puede calcular la x y la y de la funcion c=ax + by por más ejemplos que miro no me entero de como resolverlo, el mcd esta calculado con el algoritmo de Euclides y está se función se calcula justo al reves, pero ¿como?

Lun May 08, 2006 3:17 pm

kidd
Creador de Perl en Español

Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México

Hola:

No entiendo bien tu pregunta, pero aquí te va una manera de encontrar el máximo común divisor con el algoritmo de Euclides que encontré por ahí:

Código:

sub euclid {
my( $a, $b ) = @_;
return ($b) ? euclid( $b, $a % $b ) : $a;
}

my $mcd = (18,9); #Es 9

Saludos

Lun May 08, 2006 3:59 pm

creating021
Vive para Perl en Español

Registrado: 23 Feb 2006
Mensajes: 478
Ubicación: Frente al monitor

kidd:

Cita:

sub euclid {
my( $a, $b ) = @_;
return ($b) ? euclid( $b, $a % $b ) : $a;
}

my $mcd = (8,3); #Es 3? según el algoritmo si

dacons:
c = mcd(a,b);
x = mcm(a);
y = mcm(b);

Mira:
9 = 18, 9
9 = 18x - 9y
y = 9-18x/9 =>
9 = (18*2)+(9*-3)

Bueno, no se, depronte sea eso.
Suerte

Mar May 09, 2006 2:22 pm

dacons
Perlero Nuevo

Registrado: 27 Feb 2006
Mensajes: 48



La solucion es esa, ¿pero como llegas a ella? El algoritmo de Euclides es if a < b #intercambiar valores while b != 0 r= a mod b a=b b=r return a Y ahora para llegar a tu solución supuestamente el método consiste en ir despejando el resto de la última solución que es el mcd de arriba. Mediante código como sacarías el 2?

Mar May 09, 2006 3:34 pm

creating021
Vive para Perl en Español

Registrado: 23 Feb 2006
Mensajes: 478
Ubicación: Frente al monitor



He, no se, pero segun el algoritmo si a = 3 y b = 4 la respuesta es 4 y no 12. Bueno, pero como dije NO SE

Mar May 09, 2006 4:27 pm

kidd
Creador de Perl en Español

Registrado: 15 Oct 2003
Mensajes: 1389
Ubicación: México

Hola:

La primera función que te puse para conseguir el MCD con el algoritmo de Euclides no funciona bien, la correcta es:

Código:

sub gcd {
my ($a, $b) = @_;

($a,$b) = ($b,$a) if $a > $b;

while ($a) {
($a, $b) = ($b % $a, $a);
}
return $b;
}

Ahora, te recomiendo le heches un vistazo al módulo Math::Algebra::Symbols

http://search.cpan.org/~prbrenan/Math-Algebra-Symbols-1.21/pod/userGuide.pod

Con el puedes realizar operaciones algebraicas, que es lo que necesitas en tu caso.

Saludos

	Foros de discusión -> Básico	Todas las horas son GMT - 6 Horas
Página 1 de 1