Quando aprendemos a famosa operação de divisão ainda nas séries iniciais estamos aprendendo a divisão chamada euclidiana, que ocorre entre dois números naturais e que pode deixar um resto. Neste texto você vai aprender um pouco mais sobre o algoritmo da divisão euclidiana.
Conceitos iniciais.
A primeira observação que vamos fazer é que estamos considerando a divisão entre dois números naturais a e b, para ser mais específico, o a>0, pois não podemos dividir por 0.
É interessante observar que, quando tomamos o a dessa forma podemos dividir os números naturais em blocos assim.
(0, 1, 2, 3, …., a-1), (a, a+1, …, 2a-1), (2a, 2a+1, …, 3a-1), (3a, …), …
E, assim o número b vai ter que pertencer a um desses blocos, que sempre iniciam da forma qa, onde q é um natural.
Esse pensamento nos leva a afirmação a seguir:
Dados a, b naturais, com a>0, existe únicos q e r naturais tais que b=qa+r e 0≤r<a.
Neste caso, o chamamos o b de dividendo, o a de divisor, o q de quociente e o r de resto.
O leitor pode se atentar que esses nomes que acabamos de dar aos números coincidem com a ideia que temos na divisão que já sabemos, pois esses números comprem justamente a função que se espera deles.
Algoritmo da divisão euclidiana
A partir desse pensamento, é possível elaborar um algoritmo, chamado algoritmo da divisão euclidiana, que dados dois números naturais, a e b, com a>0, nos permite encontrar q e r.
O algoritmo consiste em subtrair de b o número a o máximo de vezes que conseguimos, até que o resultado dessa subtração seja menor que a. Quando estivermos nesse estágio a quantidade de vezes que subtraímos o a será igual ao quociente, e o resultado da última subtração será o resto.
Vamos a um exemplo. Dados os número 17 e 3.
Vamos subtrair a primeira vez: 17-3=14
O número 14 é ainda maior que 3, logo podemos repetir a subtração: 14-3=11.
11 ainda é maior que 3, repetindo novamente: 11-3=8.
Vamos repetir até que o resultado seja menor que 3:
8-3=5
5-3=2
O número 2 já é menor que 3, e nesse processo fizemos 5 subtrações. Portanto q=5 e r=2. E, de fato 17=5·3+2.
Fácil, né? Vamos dar mais um exemplo. Agora com os números 130 e 15.
Segue o algoritmo:
1) 130-15=115
2) 115-15=100
3) 100-15=85
4) 85-15=70
5) 70-15=55
6) 55-15=40
7) 40-15=25
8) 25-15=10
Logo, q=8 e r=10.
Algoritmo em C
Agora segue um algoritmo em C que recebe a e b e imprime o quociente e resto da divisão.
void divisaoEuclidiana(int a, int b){
int q=0, r=b;
while(1==1){
if(r<a) break;
q+=1;
r=r-a;
}
printf(“Quociente: %d\nResto: %d\n”, q, r);
}
Agora, que você já entende como funciona o algoritmo da divisão continua aqui no blog que vamos ter um texto só de exercícios que envolvem esse algoritmo.
