Introdução
Bem-vindos ao sétimo artigo da nossa série “Preparação para a Entrevista“, onde exploramos diferentes desafios e problemas comuns em entrevistas técnicas. Hoje, vamos mergulhar no problema da Torre de Hanoi.
O problema da Torre de Hanoi é frequentemente abordado em entrevistas de emprego para posições em desenvolvimento de software. Durante minha experiência em uma empresa de consultoria, testemunhei colegas e amigos se deparando com este desafio em diversas entrevistas.
Neste artigo, vamos abordar duas maneiras distintas de resolver o problema da Torre de Hanoi: uma utilizando o conceito de pilhas e outra sem o seu uso. Além disso, faremos uma análise detalhada da complexidade de cada solução, tanto em termos de tempo quanto de espaço, fornecendo uma boa compreensão que pode ser crucial em uma entrevista de emprego.
Como Funciona o Jogo da Torre de Hanoi
O jogo da Torre de Hanoi é um clássico quebra-cabeça de lógica e estratégia. No exemplo abaixo, utilizamos três discos para demonstrar o funcionamento do jogo.
Configuração Inicial:
Como mostrado na ilustração, no início do jogo, todos os três discos estão na torre de origem, empilhados com o maior disco(3) na base e o menor(1) no topo. As torres de destino e auxiliar estão vazias. O objetivo é mover todos os discos da torre de origem para a torre de destino, obedecendo às regras do jogo.
Regras do Jogo
- Movimento de Um Disco por Vez: Apenas um disco pode ser movido de cada vez.
- Disco Maior Sobre um Menor: Um disco maior não pode ser colocado sobre um disco menor.
- Uso de Torre Auxiliar: A torre auxiliar pode ser usada para movimentar os discos temporariamente.
Etapas para Resolver com Três Discos
- Movimento Inicial: Mova o menor disco (disco 1) da torre de origem para a torre de destino.
- Movimento Intermediário: Mova o disco médio (disco 2) da torre de origem para a torre auxiliar.
- Reposicionamento: Mova o disco 1 da torre de destino para a torre auxiliar, colocando-o sobre o disco 2.
- Movimento Principal: Mova o maior disco (disco 3) da torre de origem para a torre de destino.
- Movimentos Finais: Mova o disco 1 da torre auxiliar para a torre de origem, e em seguida, mova o disco 2 da torre auxiliar para a torre de destino. Por fim, mova o disco 1 da torre de origem para a torre de destino.
Esta sequência de movimentos, respeitando as regras do jogo, resolve o problema da Torre de Hanoi com três discos de forma eficiente.
Número Mínimo de Movimentos na Torre de Hanoi
O número mínimo de movimentos necessários para resolver a Torre de Hanoi é dado pela fórmula
2n−1, onde n é o número de discos.
Para o nosso exemplo com três discos, aplicamos a fórmula: 23 – 1 = 7
Solução Utilizando Pilhas
Ao abordar o problema da Torre de Hanoi, uma das soluções que prefiro é a que utiliza pilhas. Esta abordagem facilita a visualização das movimentações dos discos, um aspecto importante quando se trata de algoritmo s recursivos.
A recursividade, pode às vezes ser um conceito difícil de visualizar e entender, especialmente em problemas como a Torre de Hanoi. O uso de pilhas traz uma representação mais concreta e tangível na minha opinião.
import java.util.Stack;
public class TorreHanoi {
// Variável para contar o número de chamadas recursivas
private static int chamadasRecursivas = 0;
// Método para resolver o problema da Torre de Hanoi
public static void torreHanoi(final int n,
final Stack<Integer> original,
final Stack<Integer> destino,
final Stack<Integer> auxiliar) {
if (n > 0) {
chamadasRecursivas++;
// Movendo n-1 discos da torre original para a auxiliar, usando a de destino como auxiliar
torreHanoi(n - 1, original, auxiliar, destino);
// Movendo o disco de cima da torre original para a torre de destino
destino.push(original.pop());
// Imprimindo o estado atual das torres após cada movimento
System.out.println("----");
System.out.println("Original: " + original);
System.out.println("Destino: " + destino);
System.out.println("Auxiliar: " + auxiliar);
// Movendo os n-1 discos da torre auxiliar para a de destino, usando a original como auxiliar
torreHanoi(n - 1, auxiliar, destino, original);
}
}
public static void main(String[] args) {
// Criando as três pilhas representando as torres
Stack<Integer> original = new Stack<>();
Stack<Integer> destino = new Stack<>();
Stack<Integer> auxiliar = new Stack<>();
// Adicionando discos à torre original
original.push(3);
original.push(2);
original.push(1);
torreHanoi(original.size(), original, destino, auxiliar);
// Imprimindo o número total de chamadas recursivas
System.out.println("Número de chamadas recursivas: " + chamadasRecursivas);
}
}
Explicação do Código
Estrutura de Dados:
- Utilizamos pilhas para representar as três torres (original, destino, auxiliar). Cada pilha armazena números inteiros representando os discos, com números menores representando discos menores.
Método torreHanoi:
- Este é um método recursivo que move
ndiscos da torre original para a torre de destino. - A torre auxiliar é utilizada para mover os discos intermediários.
- A condição de parada da recursão ocorre quando
nse torna 0, significando que não há mais discos para mover.
Movimentação de Discos:
- O disco no topo da pilha original é movido para o topo da pilha de destino. Isso é feito através da operação
destino.push(original.pop()).
Impressão do Estado das Torres:
- Após cada movimento de disco, o estado atual das três torres é impresso, permitindo visualizar o processo de resolução.
Contagem de Chamadas Recursivas:
- A variável
chamadasRecursivascontabiliza o número total de chamadas ao métodotorreHanoi, fornecendo uma medida de quantas etapas recursivas foram necessárias para resolver o problema.
Método main:
- Inicializa as torres e coloca os discos na torre original em ordem decrescente (maior para menor).
- Inicia o processo de resolução chamando
torreHanoie imprime o número total de chamadas recursivas no final.
Análise de Complexidade do Algoritmo
Complexidade de Tempo
A cada chamada recursiva de torreHanoi, o problema é dividido em duas chamadas recursivas com n-1 discos. Isso resulta em uma complexidade de tempo exponencial, mais especificamente O(2n), onde n é o número de discos.
Veja que a complexidade é o número mínimo de movimentos necessários.
Complexidade de Espaço
O espaço utilizado pelo algoritmo é principalmente devido à pilha de chamadas de recursão e ao armazenamento das três pilhas de discos.
A profundidade máxima da pilha de chamadas de recursão é n, resultando em uma complexidade de espaço O(n).
Cada pilha armazena até n discos, mas isso é constante em relação à entrada do problema, pois os discos são apenas movidos entre as pilhas.
Solução Sem Uso de Pilhas
Nesta solução, também utilizaremos a recursão para mover os discos entre as torres, mas sem a necessidade de pilhas. Em vez disso, representaremos as torres e os movimentos através de parâmetros e chamadas de método. Vamos implementar isso em Java:
public class TorreHanoiSemPilha {
// Método para imprimir o movimento dos discos
private static void moverDisco(int disco, char origem, char destino) {
System.out.println("Movendo disco " + disco + " da torre " + origem + " para a torre " + destino);
}
// Método recursivo para resolver a Torre de Hanoi
private static void torreHanoi(int n, char origem, char destino, char auxiliar) {
if (n > 0) {
torreHanoi(n - 1, origem, auxiliar, destino);
moverDisco(n, origem, destino);
torreHanoi(n - 1, auxiliar, destino, origem);
}
}
public static void main(String[] args) {
int numeroDeDiscos = 3; // Número de discos
torreHanoi(numeroDeDiscos, 'A', 'B', 'C');
}
}Explicação do Código
moverDisco(int disco, char origem, char destino): Este método simula a movimentação de um disco de uma torre para outra, funcionando como uma operação de ‘empilhar’ ou ‘desempilhar’ um disco em uma pilha.resolverTorreHanoi(int n, char origem, char destino, char auxiliar): Este método implementa a lógica recursiva. Embora não utilize pilhas explicitamente, a maneira como os discos são movimentados entre as torres segue a mesma lógica da solução que usa pilhas. A recursividade aqui desempenha um papel semelhante ao de manipular os discos nas pilhas, mantendo a ordem e as regras do jogo.
Análise de Complexidade do Algoritmo
Complexidade de Tempo
Como na solução com pilhas, a complexidade de tempo é determinada pela quantidade total de movimentos de discos necessários. Portanto, a complexidade de tempo é O(2n)
Complexidade de Espaço
Similarmente, a complexidade de espaço é ditada pela profundidade da pilha de chamadas de recursão. No pior caso, a profundidade da pilha de chamadas é proporcional ao número de discos n, resultando em uma complexidade de espaço .
Comparação com a Solução que Utiliza Pilhas
- Tanto a solução recursiva sem pilhas quanto a solução que utiliza pilhas para o problema da Torre de Hanoi têm a mesma complexidade de tempo e espaço.
- Isso se deve ao fato de que, em ambas as soluções, a estrutura lógica e o número de operações necessárias para resolver o problema são essencialmente os mesmos.
- A principal diferença entre as duas abordagens é a representação dos discos e torres (pilhas explícitas versus parâmetros e chamadas de método), mas isso não afeta a complexidade geral do algoritmo.
Portanto, independente da abordagem escolhida (com ou sem o uso explícito de pilhas), a solução do problema da Torre de Hanoi mantém a mesma complexidade de tempo e espaço, refletindo a natureza intrínseca do problema.
Conclusão
Neste artigo, exploramos o problema da Torre de Hanoi, um clássico desafio de lógica em ciência da computação. Analisamos duas abordagens principais para resolver este problema: uma utilizando pilhas e outra sem o uso de pilhas, ambas com suas versões recursivas.
Soluções Recursivas:
- Demonstramos como a solução com pilhas oferece uma maneira intuitiva de visualizar o movimento dos discos, especialmente útil para entender o funcionamento da recursividade.
- A solução sem pilhas, embora tenha a mesma complexidade de tempo e espaço, apresenta uma abordagem alternativa, explorando a recursividade de uma maneira diferente.
Análise de Complexidade:
- Em ambas as soluções, observamos que a complexidade de tempo é exponencial O(2n), e a de espaço é linear ).
Relevância Prática:
- Além de ser um problema teórico interessante, a Torre de Hanoi é frequentemente utilizada em entrevistas de emprego para avaliar habilidades de resolução de problemas e compreensão de algoritmos.
E agora, um desafio para você! Tente implementar sua própria versão da Torre de Hanoi. Seja com pilhas, sem pilhas, ou uma abordagem totalmente nova, encorajo você a compartilhar suas soluções e descobertas. Participe da discussão deixando um comentário, postando suas ideias ou perguntas. Vamos aprender e crescer juntos nessa jornada!
Lembre-se, a prática é a chave para o domínio em programação e resolução de problemas. Então, agarre seu editor de código e comece a experimentar!
Explore Mais da Série “Preparação Para Entrevistas”
Encorajo você a mergulhar nos outros artigos da série “Preparação para Entrevistas“. Cada artigo desta série é elaborado para oferecer insights e dicas práticas sobre diferentes tópicos em programação e resolução de problemas, essenciais na sua preparação para entrevistas técnicas.
Referências
Cracking the Coding Interview’ é um best-seller renomado e um favorito pessoal – um livro indispensável na preparação para entrevistas técnicas!
Designing Data-Intensive Applications: é uma referência para criar aplicações escaláveis, robustas e de alto desempenho!