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:
  1. Apenas um disco pode ser movido por vez.
  2. Cada movimento consiste em pegar o disco mais no topo de uma das pilastras e deslizá-lo para outra pilastra.
  3. 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:
  1. Mover os n-1 discos superiores para uma haste auxiliar. Isso pode ser feito recursivamente.
  2. Mover o disco maior (o disco número n) para a haste de destino.
  3. 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 é:

Exercícios relacionados