Questão FC626417
A torre de Hanói é um “quebra-cabeça” constituído por uma base contendo três pinos, num dos quais são dispostos de 2 a 7 discos em ordem crescente de tamanho. O problema consiste e
Sequências de Números, Figuras, Letras e Palavras
NC UFPR (FUNPAR) · 2015
A torre de Hanói é um “quebra-cabeça” constituído por uma base contendo três pinos, num dos quais são dispostos de 2 a 7 discos em ordem crescente de tamanho. O problema consiste em passar todos os discos de um pino para outro qualquer, de acordo com determinadas regras. O jogo pode ser modelado matematicamente, por meio de letras indicando os discos e a ordem de sua movimentação. A sequência ABA indica que devemos mover o disco A, depois o disco B e novamente o disco A. Abaixo estão descritas as sequências de movimentos no caso de termos 2, 3 e 4 discos:
O número mínimo de movimentos necessários para resolver o quebra-cabeças com 6 discos é:
- 31.
- 32.
- 48.
- 63.
- 85.
Mostrar resposta e comentário
Gabarito
D
Comentário do professor
Alternativa D: 63.
O quebra-cabeça obedece à relação de recorrência \(T(n)=2T(n-1)+1\), porque para mover \(n\) discos é preciso mover os \(n-1\) superiores para o pino auxiliar, deslocar o maior disco e então mover os \(n-1\) novamente.
Essa recorrência gera a expressão fechada \(T(n)=2^n-1\). Observando os casos pequenos (por exemplo, \(T(2)=2^2-1=3\), \(T(3)=2^3-1=7\)) confirma-se o padrão.
Para 6 discos, aplicamos a fórmula: \(T(6)=2^6-1=64-1=63\). Portanto, o número mínimo de movimentos é 63.
Conteúdo do catálogo FC Concursos · Atualizado em