Questão FC626413
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 5 discos:
Sendo assim, a sequência que determina a movimentação de 4 pinos é:
- ABACABADABACABA.
- ABACABADABACABAEABACABA.
- ABACABAFABACABAC.
- ABACABABACABA.
- ABACABACD.
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
A sequência para 4 discos é obtida por recursão: se \(S_{n-1}\) é a sequência para \(n-1\) discos, então a sequência para \(n\) discos é \(S_n = S_{n-1}\,X\,S_{n-1}\), onde \(X\) representa o disco de maior tamanho.
No caso de 4 discos, já temos para 3 discos \(S_3 =\) ABACABA. Inserindo o quarto disco D no meio, obtemos \(S_4 = S_3\,D\,S_3\), isto é: ABACABADABACABA.
O comprimento dessa sequência confirma-se pela fórmula do problema: o número de movimentos é \(2^n-1\). Para \(n=4\) temos \(2^4-1=15\) movimentos, compatíveis com os 15 termos da sequência apresentada.
Conteúdo do catálogo FC Concursos · Atualizado em