Conteúdo principal
Torres de Hanoi, continuação
Quando você resolveu as Torres de Hanói com três discos, você precisou expor o disco inferior, o disco 3, para poder movê-lo do pino A para o pino B. Para expor o disco 3, você precisou mover os discos 1 e 2 do pino A para o pino livre, o pino C:
Espere um minuto — parece que dois discos se moveram em uma única etapa, violando a primeira regra. Mas eles não se moveram em uma única etapa. Você concordou que você pode mover os discos 1 e 2 de qualquer pino para qualquer pino, usando três etapas. A situação acima representa o que você tem após três etapas. (Mover o disco 1 do pino A para o pino B; mover o disco 2 do pino A para o pino C; mover o disco 1 do pino B para o pino C).
Mais ao ponto, movendo os discos 1 e 2 do pino A para o pino C, você resolveu um subproblema recursivamente: mover os discos 1 através de (lembre-se que ) do pino A para o pino C. Depois que você resolveu este subproblema, você pode mover o disco 3 do pino A para o pino B:
Agora, para terminar, você precisa resolver recursivamente o subproblema de mover os discos 1 através de do pino C para o pino B. Novamente, você concordou que você pode fazer isso em três etapas. (Mover o disco 1 do pino C para o pino A; mover o disco 2 do pino C para o pino B; mover o disco 1 do pino A para o pino B.) E você terminou:
E — você sabia que esta pergunta estava chegando — há algo especial sobre para quais pinos você moveu discos 1 a 3 de e para? Você poderia ter movido de qualquer pino para qualquer pino. Por exemplo, do pino B para o pino C:
- Recursivamente resolva o subproblema de mover os discos 1 e 2 do pino B para o pino livre, pino A. ( Mova o disco 1 do pino B para o Pino C; mova o disco 2 do pino B para o pino A; mova o disco 1 do pino C para o pino A.)
- Agora que o disco 3 está exposto no pino B, mova-o para pino C.
- Recursivamente resolva o subproblema de mover os discos 1 e 2 do pino A para o pino C.(Mova o disco 1 do pino A para o pino B; mova o disco 2 do pino A para o pino C; mova o disco 1 do pino B para o pino C.)
Não importa como você o fatia, você pode mover os discos 1 ao 3 de qualquer pino para qualquer pino, movendo os discos sete vezes. Perceba que você move os discos três vezes para cada uma das duas vezes que você resolve recursivamente o subproblema de mover os discos 1 e 2, mais um movimento para o disco 3.
Que tal quando ? Porque você consegue resolver recursivamente o subproblema de mover os discos 1 ao 3 de qualquer pino para qualquer pino, você consegue resolver o problema para :
- Recursivamente, resolva o subproblema de mover os discos 1 ao 3 do pino A para o pino C, movendo os discos sete vezes.
- Mova o disco 4 do pino A para o pino B.
- Recursivamente, resolva o subproblema de mover os discos 1 ao 3 do pino C ao pino B, movendo os discos sete vezes.
Essa solução move os discos 15 vezes (7 + 1 + 7) e sim, você pode mover os discos 1 ao 4 de qualquer pino para qualquer outro pino.
Neste ponto, você pode ter percebido dois padrões. Primeiro, você pode resolver o problema das Torres de Hanói recursivamente. Se , apenas mova o disco 1. Caso contrário, quando , resolva o problema em três etapas:
- Recursivamente, resolva o subproblema de mover os discos 1 ao
de qualquer pino onde eles comecem para o pino vazio. - Mova o disco
do pino onde ele começa até o pino onde ele deve terminar. - Recursivamente, resolva o subproblema de mover os discos 1 ao
do pino sobressalente ao onde eles devem terminar.
Em segundo lugar, resolver um problema para discos requer movimentos. Já vimos que isso é verdadeiro para:
( , apenas um movimento necessário) ( , três movimentos necessários) ( , sete movimentos necessários) ( , 15 movimentos necessários).
Se você consegue resolver o problema para discos em movimentos, então você consegue resolver o problema para discos em movimentos. Você precisa de:
movimentos para resolver recursivamente o primeiro subproblema de mover os discos de 1 a movimento para mover o disco movimentos (novamente) para resolver recursivamente o segundo subproblema de mover os discos de 1 a
Somando os movimentos, você tem .
Vamos voltar aos monges. Eles estão usando discos, portanto eles vão precisar mover um disco vezes. Esses monges são ágeis e fortes. Eles conseguem mover um disco por segundo, dia e noite.
Quanto tempo é segundos? Usando a estimativa aproximada de 365,25 dias por ano, isso resulta em 584.542.046.090,6263 anos. Ou seja, mais de 584 bilhões de anos. O sol tem apenas entre cinco e sete bilhões de anos antes de se transformar em uma supernova e nos engolir. Então, sim, o mundo terminará, e não importa quão tenazes os monges sejam, isso aconteceria bem antes de eles conseguirem mover todos os 64 discos para o pino B.
Pensando em outra maneira de usar esse algoritmo, além de prever o fim do mundo? A Wikipédia lista várias aplicações interessantes.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
- Não há nada para ser feito nesta tarefa. Basta ir para o desafio.(2 votos)
- o que eu tenho que fazer(1 voto)