Algoritmos
Exemplo de construção de um algoritmo
Definimos Algoritmo como a seqüência de passos que visam atingir um objetivo bem definido.
- Os algoritmos são utilizados no dia-a-dia para a solução dos mais diversos problemas.
- Alguns exemplos genéricos de algoritmos usados no nosso cotidiano são:
- uma coreografia,
- um manual de instruções;
- uma receita de bolo;
- a solução de uma equação do 2º grau;
- uma pesquisa na lista telefônica.
O que todas essas coisas tem em comum?
Elas podem ser vistas como uma serie finita e bem definida de passos ou regras que, quando realizadas, atingem um objetivo previamente definido.
Assim temos outra definição:
Algoritmo é a descrição de um conjunto de ações que, obedecidas, resultam numa sucessão finita de passos, atingindo um objetivo esperado.
São propriedades de algoritmos:
- Ações simples e bem definidas (não ambíguas);
- Seqüência ordenada de ações;
- Seqüência finita de passos.
Considere o seguinte problema:
- Temos três hastes.
- Uma das hastes serve de suporte para três discos de tamanhos diferentes.
- Os discos menores são sempre colocados sobre os discos maiores.
- A figura a seguir mostra uma possível situação inicial das hastes e discos.
Desejamos mover todos discos para outra
haste, porém só podemos movimentar um
disco de cada vez e um disco maior nunca
pode ser colocado sobre um disco de menor
tamanho.
Desejamos mover todos discos para outra haste,
porém só podemos movimentar um disco de cada
vez e um disco maior nunca pode ser colocado
sobre um disco de menor tamanho.
Solução: Em forma narrativa
Nomeamos as hastes como 1, 2 e 3 e os discos
como p, m e g.
Considera-se que inicialmente os discos estão na haste 1. Os passos são:
1. move o disco p para a haste 3.
2. move o disco m para a haste 2.
3. move o disco p para a haste 2.
4. move o disco g para a haste 3.
5. move o disco p para a haste 1.
6. move o disco m para a haste 3.
7. move o disco p para a haste 3.
Considera-se que inicialmente os discos estão na haste 1. Os passos são:
1. move o disco p para a haste 3.
2. move o disco m para a haste 2.
3. move o disco p para a haste 2.
4. move o disco g para a haste 3.
5. move o disco p para a haste 1.
6. move o disco m para a haste 3.
7. move o disco p para a haste 3.
Então teremos o seguinte cenário:
Podemos também representar a solução em
forma gráfica, desenhando as hastes e a
posição dos discos a cada momento (ou
passo).
A seguir veremos uma figura que descreve
os passos:
Como podemos ver, com 3 discos precisamos de,
no mínimo, 7 passos para solucionar o problema.
Quantos passos seriam necessários para se mover 4
discos?
E para n discos?
Curiosidade: Este problema foi criado m 1883 pelo
matemático francês Edouard Lucas (1842-1891),
que também criou uma lenda curiosa para enunciar
o problema. Deixo para vocês procurarem na
Internet a lenda das Torres de Hanói.
