Arquivo Discussoes de Programacao e Tecnologia 
Bom Dia galera.
Apesar de ser novato aqui, tenho muitas duvidas.
Gostaria de saber como criar um programa simples para calcular o MDC(x,y) e verificar se esse numero que retornou é par.
Clareando as ideias
class MDC{
public static int CalcularMDC(int x,int y){
/**
Não sei como fazer isso
*/
}
public static void main(String args[]){
int a = 1920,b = 1650;
int resp;
resp = CalcularMDC(a,b);
if(resp % 2 == 0)
System.out.println("PAR");
else
System.out.println("IMPAR");
}
}
Álgebra I -> divisibilidade -> MDC e MMC -> Algoritmo de Euclides
Apesar de ser um algoritmo de fácil compreensão, não é trivial. Na Wikipedia tem uma explicação e uma implementação mas eu aconselharia fazê-la sem ser recursiva para aprender. Acho que isso mata boa parte dos seus problemas, já que você já sabe ver se um número é par ou não.
Até!
Oi Java + Eclipse,
Se entendi bem, acho q a recursividade será a melhor maneira de resolver esse problema, porém concordo com o maquavelbona. Se vc optar pela recursão, faça um estudo desta técnica a parte até entender e dominar, depois aplique no exercicio.
Se a coisa complicar muito post de novo.
[]'s
No meu tempo aprendia-se MMC e MDC no ensino fundamental (lá pela 6ª ou 7ª série do primeiro grau, como se dizia naquele tempo). O algoritmo usado era o de Euclides, e você não precisa fazê-lo recursivamente; se souber fazê-lo em lápis e papel, é realmente muito simples.
No meu tempo aprendia-se MMC e MDC no ensino fundamental (lá pela 6ª ou 7ª série do primeiro grau, como se dizia naquele tempo). O algoritmo usado era o de Euclides, e você não precisa fazê-lo recursivamente; se souber fazê-lo em lápis e papel, é realmente muito simples.
Até!
Uma implementação possível:
public int calculaMDC(int x, int y){
if(x == y){
return x;
}
if (x > y){
return calculaMDC((x-y), y);
}else{
return calculaMDC((y-x), x);
}
}
}
Essa implementação é baseada em uma das soluções proposta na Wikipedia (http://pt.wikipedia.org/wiki/Mdc), de como calcular o MDC de dois números, e foi feito da forma recursiva.
Valeu galera, vou dar uma olhadinha aqui
vlw
public int mdc (int x, int y)
{
BigInteger bigX = new BigInteger(Integer.toString(x));
BigInteger bigY = new BigInteger(Integer.toString(y));
return bigX.gcd(bigY).intValue();
}
Provavelmente a maneira mais simples:E provalmente você não aprendeu nada. :) Esse tipo de questão em geral é coisa de faculdade e não se pode usar essas coisas.public int mdc (int x, int y) { BigInteger bigX = new BigInteger(Integer.toString(x)); BigInteger bigY = new BigInteger(Integer.toString(y)); return bigX.gcd(bigY).intValue(); }
Até!
E provalmente você não aprendeu nada.
Esse tipo de questão em geral é coisa de faculdade e não se pode usar essas coisas.
Lá da pra ver que eles implementam o algorítmo de euclides. Ate fazem referência de sua implementação à “Algorithm B from Knuth section 4.5.2”. Daí basta caçar o livro do Knuth.
Sem querer desmerecer a resposta, nem puxar a sardinha pro meu lado, usando gcd facilita a coisa demais… e a lógica, onde fica??? Numa faculdade, usar um esquema desses é pedir pra tirar um zero bonito… 
Mas tá valendo, pelo menos a gente fica sabendo q tem a forma mais fácil de fazer a coisa…
Abraços!!!
Tem razão, não esqueço de um cara aqui na faculdade, em plena aula de recursão, num exercício simples de fatorial, o cara estava se matando para encontrar uma tal feunção Fib pronta…
Fibonacci é outra lógica q os professores de faculdade adoram… 
Parece ser complicada, mas na verdade é só verificar q o valor atual vai ser a soma dos dois anteriores na sequência e montar a lógica…
Pra quem não lembra, Fibonacci é uma sequência que começa com 0 e 1, e o próximo número é sempre a soma dos dois anteriores… algo como:
0,1,1,2,3,5,8,13,21,34,…
Abraços!!!
Fibonacci é outra lógica q os professores de faculdade adoram…Parece ser complicada, mas na verdade é só verificar q o valor atual vai ser a soma dos dois anteriores na sequência e montar a lógica…
Pra quem não lembra, Fibonacci é uma sequência que começa com 0 e 1, e o próximo número é sempre a soma dos dois anteriores… algo como:
0,1,1,2,3,5,8,13,21,34,…
Abraços!!!
Seria legal fazer um algoritmo desse… nao é certeza de conseguir mas valeu cara, voce me deu uma ideia
Abraços
Álgebra I -> divisibilidade -> MDC e MMC -> Algoritmo de EuclidesApesar de ser um algoritmo de fácil compreensão, não é trivial.
Até!
Isso me lembra o Algoritmo de Kruskal 
Cara, Fibonacci, pra quem quer “brincar” um pouco com lógica, é excelente… não é à toa q os professores de faculdade adoram… geralmente pedem pra descobrir o n-ésimo número da sequência…
Depois vou tentar desenvolver um método pra isso… se conseguir, depois eu posto aqui… aliás, se alguém conseguir, tanto Fibonacci qto MDC ou qualquer outra q mexa com a lógica, posta aqui o desafio pra galera!!
Abraços!!! 
Eu tive que fazer fibonacci no primeiro ano da faculdade… me bati bastante, mas fiz!
No segundo ano tive que fazer fibonacci recursivo, mas nem me lembro como fiz.
Um código bem ‘porco’ de fibonacci normal tá aqui:
import java.util.Scanner;
public class Fibonacci {
private int fibonacci(int n)
{
int a1 = 0, a2 = 1, soma = 0, contador = 2;
if (n == 1)
{
return a1;
}
else if (n == 2)
{
return a2;
}
else
{
while (contador < n)
{
soma = a1 + a2;
a1 = a2;
a2 = soma;
contador++;
}
}
return soma;
}
public static void main(String[] args)
{
Scanner leitor = new Scanner(System.in);
Fibonacci f = new Fibonacci();
int n;
System.out.print("n = ");
n = Integer.parseInt(leitor.nextLine());
for (int contador = 1; contador <= n; contador++)
{
System.out.print(f.fibonacci(contador) + " ");
}
}
}
Acho que tem jeitos de melhorar bastante ainda (principalmente no tempo de execução). Dá pra fazer recursivo também. Enfim…
Pra quem gosta desses desafios legais, tem o site do UVa Judge Online, Topcoder e os tribonaccis e tetranaccis da vida.
Essa conversa me lembra uma frase que li na internet:
“Não contrate alguém que implemente fatorial com recursão.” Ou será que era fibonacci?
Bom, qto a recursividade, não sei discutir qdo é melhor ou não usar… falo somente pela implementação q eu postei aqui, q me pareceu ser bem mais fácil de implementar usando recursividade (embora seja completamente possível implementar uma solução para calcular o MDC sem usá-la…)
Uma coisa deve-se dizer: mais importante do que usar ou não, o mais importante é fazer de uma forma eficiente…
Abraços!!!
Ae galera, a quem possa interessar, uma implementação pra calcular o MMC (Mínimo Múltiplo Comum):
public int calculaMMC(int x, int y){
int mult = 0;
Integer multMax = 0;
Integer multMin = 0;
int mmc = 0;
if(x == 0 || y == 0){
return 0;
} else if(x == 1){
return y;
}else if (y == 1){
return x;
}else if (x == y){
return x;
}else{
mult = x * y;
int indiceMax = mult / Math.max(x, y);
int indiceMin = mult / Math.min(x, y);
List<Integer> listaMax = new ArrayList<Integer>();
for (int i = 1; i <= indiceMax; i++){
multMax = multMax + Math.max(x, y);
listaMax.add(multMax);
}
for (int i = 1; i <= indiceMin; i++){
multMin = multMin + Math.min(x, y);
if(listaMax.contains(multMin)){
mmc = multMin;
break;
}
}
return mmc;
}
}
Como pode ser visto, não usei recursividade dessa vez.
Se alguém tiver alguma “resposta” além dessa, compartilha com a galera!!!
Abraços!!!
Ainda em Álgebra I, você aprende que:
sendo
Então:
md=|ab|
Partindo disso e tendo o algoritmo de calcular MDC, não terás nenhuma dificuldade. Assim não precisa de um outro algoritmo especializado nisso.
Até!
Fazendo um cálculo rápido aqui, realmente tenho q te dar razão, a regra é válida sim… ou seja, a partir de qualquer um dos dois (MMC ou MDC) eu consigo calcular o outro…
Mas convenhamos: qual a graça (sem desmerecer a importância dessa regra)?? Afinal, o esquema é desenvolver a lógica…
Abraços!!!
Fazendo um cálculo rápido aqui, realmente tenho q te dar razão, a regra é válida sim… ou seja, a partir de qualquer um dos dois (MMC ou MDC) eu consigo calcular o outro…Mas convenhamos: qual a graça (sem desmerecer a importância dessa regra)?? Afinal, o esquema é desenvolver a lógica…
Abraços!!!
Até!
Fazendo um cálculo rápido aqui, realmente tenho q te dar razão, a regra é válida sim… ou seja, a partir de qualquer um dos dois (MMC ou MDC) eu consigo calcular o outro…Mas convenhamos: qual a graça (sem desmerecer a importância dessa regra)?? Afinal, o esquema é desenvolver a lógica…
Abraços!!!
Não tiro sua vontade, mas em questão de eficiência é bem legal usar os artifícios matemáticos que se tem. Assim não precisamos guardar várias maneiras de calcular as coisas.Até!
Não tenha dúvida, vc tem toda razão. Se fosse um sistema a ser feito, eu tb usaria, não só os recursos matemáticos, como tb eventuais métodos existentes pra facilitar e fazer um desenvolvimento mais rápido. Mas um programador que se preze tb tem q ter um “quê” de matemático, ou seja, “brincar” com lógicas como essa só tem a acrescentar… eu, pelo menos, gosto bastante de desenvolver lógicas assim…
Abraços!!