Um algoritmo para determinar o máximo divisor comum (MDC) entre dois números inteiros a eb (com a > b) pode ser descrito como:
ENQUANTO (b <> 0) FAÇA
    r <- a MOD b
    a <- b
    b <- r
    mdc <- a
FIM ENQUANTO
Escreva uma função int MDC que execute esse algoritmo e um programa para testar o uso dessa função para quaisquer valores possíveis de a e b.

Passo 1

O enunciado pede para implementar em C a função int MDC que calcula o máximo divisor comum de dois inteiros usando o algoritmo de Euclides por restos sucessivos e, em seguida, criar um programa que teste essa função com quaisquer valores de a e b.

Passo 2

O conteúdo teórico é o algoritmo de Euclides, que se baseia na propriedade gcd(a,b)=gcd(b,abmod b). A cada iteração, substituímos a por b e b por abmod b até que b=0; quando isso acontece, a contém o gcd. Vamos traduzir isso em código na função int MDC.

Passo 3

Para a função MDC, declaramos os parâmetros int a e int b, criamos uma variável local int r para o resto, e usamos um laço while enquanto b for diferente de zero. A cada volta do laço, calculamos r = a % b, depois ajustamos a = b e b = r. Quando o laço termina, retornamos a.

Passo 4

Para o programa de teste (função main), declaramos duas variáveis a e b, usamos um loop que lê repetidamente dois inteiros do usuário até EOF (retorno de scanf diferente de 2 interrompe). Garantimos que a ≥ b trocando os valores se necessário, chamamos MDC(a,b) e imprimimos o resultado. Assim podemos testar para quaisquer pares de inteiros.

Passo 5

Segue abaixo o código completo em C com comentários explicativos.

Resposta

#include <stdio.h>
// Função que retorna o máximo divisor comum de a e b pelo algoritmo de Euclides
int MDC(int a, int b) {
int r;
// enquanto o segundo número não for zero, continua trocando restos
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a; // quando b chegar a zero, a é o MDC
}
int main() {
int a, b;
printf(“Digite dois inteiros (a e b), ou Ctrl+D para sair:\n”);
// lê pares de inteiros até o usuário interromper (EOF)
while (scanf("%d %d", &a, &b) == 2) {
// garante que a >= b trocando se necessário
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
printf(“MDC(%d, %d) = %d\n”, a, b, MDC(a, b));
printf(“Digite dois inteiros (a e b), ou Ctrl+D para sair:\n”);
}
return 0;
}

Exercícios relacionados