Algoritmo da divisão euclidiana 

Entre para nossa lista e receba conteúdos exclusivos!

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.

Outros Artigos

Reprodução-das-Plantas
Biológicas

Reprodução das Plantas

Você sabe como funciona o processo de reprodução das plantas? Qual a sua importância e o porquê de acontecer? Clique aqui e saiba mais.

Legal

® 2021-2024 Meu Guru | 42.269.770/0001-84 • Todos os direitos reservados

Entre para nossa lista e receba conteúdos exclusivos!