Implementando o Algorítmo estendido de Euclides

4 de setembro de 2010 4 respostas

DavidUser 4 de setembro de 2010

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:

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 p*a0 + q*b0 = a and r*a0 + s*b0 = 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)
}

4 Respostas

andre.froes 5 de set. de 2010

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 ^^

DavidUser 6 de set. de 2010

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

andre.froes 6 de set. de 2010

aqui tem um exemplo então:

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

deve te ajudar

DavidUser 6 de set. de 2010

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

Criado 4 de setembro de 2010

Ultima resposta 6 de set. de 2010

Respostas 4

Participantes 2

4 Respostas

Topicos relacionados