Obtenha uma relação de recorrência para o problema das Torres de Hanói apresentado no Exercício 1.1.20.
Passo 1
Beleza, vamos lá! O exercício pede para a gente obter uma relação de recorrência para o problema das Torres de Hanói apresentado no Exercício 1.1.20. Isso significa que vamos criar uma fórmula que relaciona o número de movimentos necessários para resolver o quebra-cabeça com o número de discos envolvidos. Para isso, vamos precisar entender o que é uma relação de recorrência e como ela se aplica ao problema das Torres de Hanói.
Passo 2
Primeiro, vamos lembrar do que são as Torres de Hanói. É um jogo de quebra-cabeça que consiste em três hastes e um número de discos de tamanhos diferentes que podem deslizar sobre qualquer haste. O objetivo é mover toda a pilha de discos para outra haste, seguindo três regras:
- Apenas um disco pode ser movido por vez.
- Cada movimento consiste em pegar o disco mais no topo de uma das pilastras e deslizá-lo para outra pilastra.
- Nenhum disco pode ser colocado sobre um disco menor.
Passo 3
Agora, vamos falar sobre a relação de recorrência. É uma maneira de definir uma sequência baseada em termos anteriores da própria sequência. No contexto das Torres de Hanói, queremos expressar o número mínimo de movimentos necessários para resolver o quebra-cabeça com n discos em termos do número de movimentos para n-1 discos.
Passo 4
Para resolver as Torres de Hanói com n discos, a estratégia é a seguinte:
- Mover os n-1 discos superiores para uma haste auxiliar. Isso pode ser feito recursivamente.
- Mover o disco maior (o disco número n) para a haste de destino.
- Mover os n-1 discos da haste auxiliar para a haste de destino, sobre o disco maior. Isso também é feito recursivamente.
Passo 5
Vamos traduzir essa estratégia em uma relação de recorrência. Se denotarmos por T(n) o número mínimo de movimentos necessários para resolver o problema com n discos, então:
- Mover os n-1 discos para a haste auxiliar requer T(n-1) movimentos.
- Mover o disco maior requer 1 movimento.
- Mover os n-1 discos para a haste de destino requer mais T(n-1) movimentos.
Então, a relação de recorrência fica:
Resposta
A relação de recorrência para o problema das Torres de Hanói é: