Implementando o Algorítmo estendido de Euclides

Programação Java
#1

Estou com problemas para implementar o Algoritmo estendido de Euclides.
Alguem pode me funciona a implementação do algoritmo?
até encontrei um exemplo em JS mais não sei oq tem haver com a teoria…

Exemplo a baixo:

[code]function aee(a,b) {
if (a<1) return(“Valor de a inadequado!”);
if (b<1) return(“Valor de b inadequado!”);

// Save original values.
a0 = a;
b0 = b;

// Initializations. We maintain the invariant pa0 + qb0 = a and ra0 + sb0 = b.
p = 1; q = 0;
r = 0; s = 1;

// The algorithm:
while (b != 0) {
c = a % b;
quot = Math.floor(a/b); //Javascript doesn’t have an integer division operator
a = b;
b = c;
new_r = p - quot * r; new_s = q - quot * s;
p = r; q = s;
r = new_r; s = new_s;
}

return(“MDC(” + a0 + “,” + b0 + ") = " + p + “" + a0 +
" + (" + q + ")” + b0 + " = " + a)
}
[/code]

#2

eu fiz assim:

import javax.swing.JOptionPane;

public class Euclides{
  public static void main(String[] args){
    int x, y;
      try{
        x = Integer.parseInt(JOptionPane.showInputDialog("1º número: "));
        if (x < 1)
            throw new NumberFormatException();
      } catch (NumberFormatException e){
          x = Integer.parseInt(JOptionPane.showInputDialog("1º número: "));
      }

    try{
        y = Integer.parseInt(JOptionPane.showInputDialog("1º número: "));
        if (y < 1)
            throw new NumberFormatException();
      } catch (NumberFormatException e){
          y = Integer.parseInt(JOptionPane.showInputDialog("1º número: "));
      }


    JOptionPane.showMessageDialog(null, "MDC de " + x + " e " + y + " é " + MDC(x,y));
  }

  public static int MDC(int a, int b){
    int resto;

    while(b != 0){
      resto = a % b;
      a = b;
      b = resto;
    }

    return a;
  }
}

axo que isso te ajuda ^^

#3

andre.froes esse é o Algoritmo de Euclides, quero implemenar o Algoritmo ESTENDIDO de Euclides.

#4

aqui tem um exemplo então:

http://www.javakb.com/Uwe/Forum.aspx/java-setup/12625/Extended-Euclidean-algorithm-for-java

deve te ajudar
:smiley:

#5

Valeu pela atenção andre.froes, encontrei oque proucurava em http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

#6