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.
ENQUANTO (b <> 0) FAÇA
r <- a MOD b
a <- b
b <- r
mdc <- a
FIM ENQUANTO
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
. A cada iteração, substituímos
por
e
por
até que
; quando isso acontece,
contém o
. 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 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;
}
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;
}