Exercício:
A Torre de Hanói é um jogo
formado por três pinos (também chamadas de torres) e um conjunto de N discos de
diferentes tamanhos, que, inicialmente, estão dispostos em ordem crescente no
pino I. A figura 1 representa essa situação:
Figura 1 - Pinos e discos na posição original
O desafio do jogo consiste
em deslocar todos os discos para o pino III, observando as seguintes
regras:
þ
Devemos deslocar um
disco por vez;
þ
Um disco maior não pode
ser colocado em cima de um disco menor.
A partir dessas
informações, vamos ao nosso desafio.
-
Qual o número mínimo de
movimentos, Q(N), necessário para deslocar os N discos?
-
Para qual pino deveremos
deslocar o primeiro disco (primeiro movimento) para obtermos um número
mínimo de movimentos?
-
É possível apresentar um
algoritmo para o deslocamento destes N discos com um número mínimo de
movimentos? |
Passo-a-passo
- Entre neste link.
- Defina o número de discos igual a
três.
- Observe a definição do número mínimo
de movimentos.
- Movimente os discos da torre 1 para
a torre 3, seguindo as regras do jogo.
- Repita o processo para diferentes
quantidades de discos, anotando seus resultados, de forma a ter subsídios para
responder as três questões do nosso desafio.
- Responda as questões de nosso
desafio.
- Compare os seus resultados com o
nosso gabarito.