MDC de dois números inteiros positivos utilizando o algoritmo de Eucl

[Verônica M.]

Sou nova em Programação aqui!

Gostaria de uma ajudinha pra fazer um programa que fizesse o MDC de 2 numeros,

e tambem gostaria de ser saber como é esse algoritmo de Euclides ( nunca ouvi falar )!

Se alguém puder me ajudar, agradeço desde já! (:

[kuroi]

o algoritmo de euclides você encontra o codigo no google.

mas acho q o exercicio é você fazer o seu proprio codigo ne??

nesse caso, você pode ir tirando o resto de todos os numeros ate chegar no maior dos dois. o ultimo numero q tiver dado resto 0 é o maximo divisor comum.

mas ai você pode tentar pensar em formas de evitar divisao desnecessaria.

[Andre_Luiz]

o algoritmo de euclides você encontra o codigo no google.

mas acho q o exercicio é você fazer o seu proprio codigo ne??

nesse caso, você pode ir tirando o resto de todos os numeros ate chegar no maior dos dois. o ultimo numero q tiver dado resto 0 é o maximo divisor comum.

mas ai você pode tentar pensar em formas de evitar divisao desnecessaria.

Entendendo como funciona:

Euclides utilizou um método para o cálculo do máximo divisor comum (m.d.c.) de dois números que ficou conhecido precisamente por algoritmo de Euclides.

Este método é em muitas situações mais prático de utilizar do que o método da intersecção dos conjuntos de divisores e do método da decomposição em factores primos. Além disso, é muito mais simples de traduzir por um programa de computador.

Para cálcular o m.d.c.de 33 e 48:

1) Divide-se o maior número pelo outro.

48 ÷ 33 dá 1, resto 15

O resto não é zero.

2) O divisor passa a dividendo, o resto passa a divisor e divide-se de novo.

33 ÷ 15 dá 2, resto 3

3) Como o resto não é zero, repete-se novamente 2)

15 ÷ 3 dá 5, resto 0

Agora, finalmente, a divisão não deixou resto; e o último resto diferente de 0 é o máximo divisor comum.

Em C isso ficaria:

#include <stdio.h>
#include <stdlib.h>

main()
{
    int n1,n2,resto;
      

    printf("Digite dois numeros: ");
    scanf("%d%d", &n1, &n2);
              
              
              resto=n1%n2;
              while(resto!=0)
              {
                  n1    = n2;
                  n2    = resto;
                  resto = n1%n2;         
              }
              printf("MDC = %d\n", n2);
              system("pause");
}

Com esse código em C você calcula o MDC de qualquer número. Você poderia fazer uma função também, para calcular o MDC de quantos número você quiser.

Espero ter ajudado.

Abraços!

Editado Outubro 1, 2009 por Andre_Luiz

[lifebok]

pessoal eu preciso fazer um programa e nao entendi bulufas, fiquei o sábado todo tentando, se trata de :

 

Imagine que COMM(N,K) representa o número de diferentes comitês de k pessoas, que pode ser formados, dadas n pessoas a partir das quais escolher. por exemplo, COMM(4,3) =4, porque dadas quatro pessoas, A, B, C  e D existem quatro possíveis comitês de tres pessoas : ABC, ABD, ACD e BCD. demonstre a identidade:

COMM(N , K) = COMM(N - 1,K) + COMM(N - 1, K - 1)

ESCREVA E TESTE um programa recursivo em C para calcular COMM(N,K) para n,k >=1.