Segunda-feira, 6 de Outubro de 2008

Os algoritmos - algoritmo de Euclides

Comecemos por fazer uma pergunta: o que é um algoritmo?


Se falarmos de computadores um algoritmo é uma sequência de instruções que é executada numa determinada ordem até que uma condição se verifique.

Mas, matematicamente, é um conjunto de processos e de símbolos utilizados para efectuar um cálculo.


Quer isto dizer que antes de haver computadores já existiam algoritmos e eram as maneiras práticas que os matemáticos descobriram e utilizavam para fazer cálculos.

É assim que temos algoritmos para as diferentes operações aritméticas, adição, subtracção, multiplicação e divisão, que todos nós utilizamos no dia a dia, embora, por exemplo, a mesma multiplicação se possa efectuar de várias maneiras diferentes e apesar dos computadores ainda são utilizados(voltaremos a este assunto).


Há, no entanto alguns algoritmos, já bem antigos que deixaram de ser utilizados, mas que facilitavam muito os cálculos. De entre esses, destacamos dois: o algoritmo de Euclides e o algoritmo da raiz quadrada.


Vejamos um exemplo para cada um dos casos.

 

Problema A

 

Um fabricante de enfeites de Natal tem em armazém dois tipos de bolas, 11466 vermelhas e 7128 prateadas. Para controlar os custos das embalagens quer embalar as bolas em caixas todas iguais e pretende saber qual o número máximo de bolas da mesma cor que deve levar cada embalagem de modo que não sobre nenhuma. E quantas embalagens vai fazer com as bolas de cada cor?

 

Para resolver o problema tem de calcular um número que simultaneamente seja divisor do número (11466) que representa as bolas vermelhas e do número (7128) que representa as bolas prateadas. E como deve ser divisor e ser o número máximo de bolas que divide os dois números, então só pode ser o máximo divisor comum dos dois.

 

Uma das formas de resolver o problema é utilizar a decomposição em factores primos.

 

A outra, que é a que nos interessa é utilizar o algoritmo de Euclides ou método das divisões sucessivas para o calcular o

 

m.d.c (11466, 7128) =

 

Vamos então utilizar as divisões sucessivas, começando por dividir o número maior pelo menor

 

 

  • Fomos fazendo divisões em que o divisor passa a ser o dividendo seguinte e o resto passa a ser divisor até que atingimos uma última divisão que dá resto zero.
  • O último divisor, neste caso 18 é o maior divisor comum de 11466 e 7128.
  • Este resultado permite-nos afirmar que as caixas para embalar as bolas de Natal devem conter 18 bolas cada uma.
  • E quantas caixas?
  • Basta fazer duas divisões:

             11466 : 18 = 637                              7128 : 18 = 396

 

Em conclusão:

 

As bolas vermelhas são embaladas em 637 caixas de 18 bolas e as prateadas em 396 caixas de 18 bolas.

 

Duas questões:

 

Que relação existe entre o m.d.c 18 e os restos que foram sendo obtidos ao longo das divisões efectuadas? 

 

Como fazer para calcular o m.m.c (11466, 7128)?

publicado por Frantuco às 19:34
link do post | comentar | favorito

.mais sobre mim

.pesquisar

 

.Janeiro 2010

Dom
Seg
Ter
Qua
Qui
Sex
Sab
1
2
3
4
5
6
7
8
9
10
12
13
14
15
17
18
19
20
21
22
23
25
26
27
28
29
30
31

.posts recentes

. Os algoritmos - algoritmo...

.arquivos

. Janeiro 2010

. Dezembro 2009

. Novembro 2009

. Outubro 2009

. Agosto 2009

. Julho 2009

. Junho 2009

. Maio 2009

. Abril 2009

. Março 2009

. Fevereiro 2009

. Janeiro 2009

. Dezembro 2008

. Novembro 2008

. Outubro 2008

. Setembro 2008

. Agosto 2008

. Julho 2008

.palavras-chave

. todas as tags

.links

blogs SAPO