Introdução
Em programação C, o MDC (Máximo Divisor Comum - Greatest Common Divisor, GCD) é frequentemente calculado. Duas formas diferentes são comumente usadas para encontrar o MDC. Podemos usar o algoritmo de Euclides e calcular o MDC por subtração repetida. Neste laboratório passo a passo, demonstraremos ambos os métodos.
Usando o Algoritmo de Euclides
O algoritmo de Euclides, no qual o numerador é substituído pelo resto da operação de divisão, é usado para calcular o MDC (GCD). Quando o resto se torna zero, o MDC é o numerador.
1.1 Comece a solução declarando uma variável inteira chamada a e b.
int a, b;
1.2 Em seguida, peça ao usuário para inserir os valores de a e b.
printf("Enter two numbers: \n");
scanf("%d %d", &a, &b);
1.3 Então, crie um loop while que roda até que o resto de a dividido por b seja zero.
while(a!=b)
{
if(a>b)
a=a-b;
else
b=b-a;
}
1.4 Finalmente, exiba o MDC dos dois números.
printf("The GCD of two numbers is %d", a);
Usando o Método de Subtração Repetida
Neste método, o MDC (GCD) é calculado subtraindo repetidamente o valor menor do valor maior até que eles se tornem iguais. Se ambos se tornarem iguais, então o número é o MDC.
2.1 Comece com uma variável inteira chamada num inicializada com 0.
int num = 0;
2.2 Declare uma variável inteira chamada x e inicialize-a com 2.
int x = 2;
2.3 Peça ao usuário para inserir o número de inteiros para encontrar o MDC.
printf("Enter the number of integers you want to find the GCD of: ");
scanf("%d", &num);
2.4 Em seguida, peça ao usuário para inserir os números.
printf("Enter %d numbers:\n", num);
int arr[num];
for(int i = 0; i < num; i++)
{
scanf("%d", &arr[i]);
}
2.5 Agora podemos calcular o MDC pegando os valores de entrada e usando o método de subtração repetida. Chamaremos a função gcd() para calcular o MDC dos valores de entrada.
int result = arr[0];
for(int i = 1; i < num; i++)
{
result = gcd(result, arr[i]);
}
Combinando os Métodos
Nesta etapa, combinaremos os métodos para completar a implementação.
3.1 Declare uma função gcd() para usar na busca do MDC pelo método de subtração repetida.
int gcd(int a, int b)
{
if(b==0)
return a;
else if(a >= b && b > 0)
return gcd(b,a%b);
else
return gcd(b,a);
}
3.2 Declare uma nova variável chamada gcd_result e inicialize-a com zero.
int gcd_result = 0;
3.3 Criaremos um novo loop que solicita ao usuário que insira números até que um valor de entrada de 0 seja detectado.
printf("Enter numbers. To exit enter 0\n");
while(1) // infinite loop to take input
{
int num;
scanf("%d", &num);
if(num < 1)
break;
else if(gcd_result == 0)
gcd_result = num;
else if(num < gcd_result)
gcd_result = gcd(num, gcd_result);
else
gcd_result = gcd(gcd_result, num);
}
3.4 Por fim, exiba o resultado final usando a função printf.
printf("The GCD of all the entered numbers is: %d\n", gcd_result);
Resumo
Neste laboratório, aprendemos dois métodos para calcular o MDC (GCD) de um grupo de inteiros na programação C: o algoritmo de Euclides e o método de subtração repetida. Demonstramos como usar esses métodos com uma explicação detalhada e blocos de código de exemplo. Para maior compreensão, recomenda-se modificar e executar o código no arquivo main.c.
