Algoritmo da Torre de Hanói: Python, C++ Code

⚡ Resumo Inteligente

O algoritmo da Torre de Hanói é um quebra-cabeça recursivo clássico que move uma pilha de discos entre três pinos, sem nunca colocar um disco maior sobre um menor, ilustrando claramente o princípio de dividir para conquistar.

🗼 Configuração do quebra-cabeça: Três pinos e n discos empilhados em ordem decrescente de tamanho no pino de origem, aguardando para serem movidos para o pino de destino através de um pino auxiliar.
📜 Regras: Apenas um disco se move por vez, somente o disco superior de cada pino pode se mover, e um disco maior não pode repousar sobre um disco menor.
🔁 Ideia recursiva: Mova n-1 discos para o pino auxiliar, mova o disco maior para o pino de destino e, em seguida, mova os n-1 discos restantes do pino auxiliar para o pino de destino.
⏱️ Complexidade de tempo: Resolver n discos requer 2^n – 1 movimentos, resultando em uma complexidade de tempo exponencial O(2^n) que cresce muito rapidamente à medida que n aumenta.
🧠 Complexidade do espaço: A pilha de recursão comporta até n quadros de uma só vez, portanto a complexidade de espaço da solução recursiva é O(n).
🛠️ Aplicações: Ensinar recursão, esquemas de rotação de backup, movimentação de dados baseada em pilha, sequenciamento em robótica e compreender o projeto de algoritmos de divisão e conquista.

Saiba Mais

O que é a Torre de Hanói?

A Torre de Hanói é um quebra-cabeça matemático composto por três hastes e uma pilha de discos de tamanho decrescente, dispostos uns sobre os outros. Também é conhecida como Torre de Brahma ou Torre de Lucas, nome que foi proposto pelo matemático francês Édouard Lucas em 1883. O quebra-cabeça é baseado em lendas sobre o movimento de discos de ouro entre três hastes.

Este quebra-cabeça possui três hastes e um número variável de discos empilhados. As hastes estão dispostas como torres cíclicas, de modo que os discos maiores ficam na base e os menores no topo.

Inicialmente, temos três pinos ou hastes. Um deles (pino A no exemplo) contém todos os discos empilhados. O objetivo é mover toda a pilha de uma haste (A) para outra (C), obedecendo a algumas regras específicas.

Aqui está a configuração inicial do quebra-cabeça:

Problema da Torre de Hanói

E este é o objetivo final:

Regras da Torre de Hanói

Aqui estão as regras essenciais para a Torre de Hanói:

No estado inicial do quebra-cabeça, todos os discos estão empilhados na haste um.
Na etapa final, todos os discos da haste um são empilhados na haste dois ou na haste três.
Apenas um disco pode se mover de uma haste para outra em um dado momento.
Apenas o disco mais superior em uma haste pode ser movido.
Um disco não pode ser colocado em cima de um disco menor.

A lenda original falava sobre mover 64 discos. Os sacerdotes podiam mover um disco de cada vez, seguindo as regras. Segundo a lenda, havia uma profecia de que o mundo acabaria se eles conseguissem completar o feito. Na seção sobre complexidade de tempo, mostraremos que uma configuração da Torre de Hanói com n discos requer 2^n – 1 movimentos.

Assim, se os sacerdotes precisassem de 1 segundo para mover um disco, o tempo total para resolver o enigma seria de 2^64 – 1 segundos, ou aproximadamente 584,942,417,356 anos, 26 dias, 7 horas e 15 segundos.

Algoritmo para Torre de Hanói

A maneira mais comum de resolver o problema da Torre de Hanói é por meio de um algoritmo recursivo. Primeiro, escolhemos duas hastes como origem e destino; a haste extra atua como auxiliar.

Aqui estão as etapas para resolver o quebra-cabeça da Torre de Hanói:

Mova os discos n-1 superiores do pino de origem para o pino auxiliar.
Mova o enésimo disco do pino de origem para o pino de destino.
Mova os n-1 discos restantes do pino auxiliar para o pino de destino.

Observação: Se tivermos um único disco, podemos movê-lo diretamente da origem para o destino.

Como resolver o quebra-cabeça da Torre de Hanói

Vamos ilustrar o algoritmo para três discos. Considere o pino A como a origem, o pino B como o auxiliar e o pino C como o destino.

Passo 1) Inicialmente, todos os discos estão empilhados no pino A.

Nesta etapa: Origem = Pino A, Destino = Pino C, Auxiliar = Pino B.

Agora, precisamos mover os n-1 discos superiores da origem para o auxiliar.

Observação: Embora só possamos mover um disco por vez, essa etapa reduz nosso problema de 3 discos para um problema de 2 discos, que é resolvido por uma chamada recursiva.

Passo 2) Ao fazermos uma chamada recursiva do pino A com o pino B como destino, usamos o pino C como auxiliar.

Observe que retornamos ao estágio um do mesmo problema da Torre de Hanói, mas agora com dois discos. Movemos n-1 (ou seja, um) disco da origem para o auxiliar, o que move o menor disco do pino A para o pino C.

Nesta etapa: Origem = pino A, Destino = pino B, Auxiliar = pino C.

Passo 3) De acordo com o algoritmo, o n-ésimo (2º) disco é agora transferido para o destino, pino B.

Nesta etapa: Origem = pino A, Destino = pino B, Auxiliar = pino C.

Passo 4) Agora, movemos o disco n-1 (disco um) do pino auxiliar C para o pino de destino B, seguindo a terceira etapa do algoritmo.

Nesta etapa: Origem = pino A, Destino = pino B, Auxiliar = pino C.

Passo 5) Após concluir a chamada recursiva, retornamos à configuração anterior, na primeira etapa do algoritmo.

Passo 6) Na segunda etapa, movemos o disco 3 do pino de origem A para o pino de destino C.

Nesta etapa: Origem = pino A, Destino = pino C, Auxiliar = pino B.

Passo 7) A próxima tarefa é mover os discos restantes do dispositivo auxiliar (pino B) para o destino (pino C). Desta vez, usaremos a origem original (pino A) como dispositivo auxiliar.

Passo 8) Como não podemos mover dois discos ao mesmo tempo, fazemos uma chamada recursiva para o disco 1. De acordo com o nosso algoritmo, o destino nesta etapa é o pino A.

Nesta etapa: Origem = pino B, Destino = pino A, Auxiliar = pino C.

Passo 9) Nossa chamada recursiva foi concluída. Agora movemos o disco 2 de sua origem para seu destino.

Nesta etapa: Origem = pino B, Destino = pino C, Auxiliar = pino A.

Passo 10) Finalizamos movendo o disco restante (disco 1), que é n-1, do auxiliar para o destino.

Nesta etapa: Origem = pino A, Destino = pino C, Auxiliar = pino B.

Apelido Code para a Torre de Hanói

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

Código do programa em C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

Saída:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Código do programa em Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

Saída:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Complexidade da Torre de Hanói

Aqui está a complexidade temporal e espacial da Torre de Hanói:

1) Complexidade de tempo:

Analisando o algoritmo, fazemos uma chamada recursiva para (n-1) discos duas vezes por chamada. Cada recursão de (n-1) se divide em ((n-1)-1) recursões, e assim por diante, até chegarmos ao caso base de disco único.

Para três discos:

O disco 3 chama a função recursiva do disco 2 duas vezes.
O disco 2 chama a função recursiva do disco 1 duas vezes.
O disco 1 se move em tempo constante, dando tempo suficiente para calcular o valor para três discos.

Expressa-se como uma recorrência:

= 2 × (Tempo para resolver para dois discos) + tempo constante para mover o disco 3

= 2 × (2 × tempo para resolver para um disco + tempo constante para mover o disco 2) + tempo constante para mover o disco 3

= (2 × 2) × tempo constante para mover o disco 1 + 2 × tempo constante para mover o disco 2 + tempo constante para mover o disco 3

Para n discos, isso se torna:

2^n-1 × tempo constante para mover o disco 1 + 2^n-2 × tempo constante para mover o disco 2 + ….

Essa progressão geométrica soma O(2ⁿ – 1), que se simplifica para O (2ⁿ), uma complexidade de tempo exponencial.

2) Complexidade espacial:

A complexidade espacial da Torre de Hanói é O(n). A recursão utiliza a pilha de chamadas, e a profundidade máxima da pilha é igual a n, o número de discos. É por isso que a complexidade espacial é O(n).

Perguntas Frequentes

O algoritmo da Torre de Hanói é um procedimento recursivo que move n discos de um pino de origem para um pino de destino usando um pino auxiliar, sem nunca colocar um disco maior sobre um menor.

O número mínimo de movimentos para n discos é 2^n – 1. Três discos precisam de 7 movimentos, quatro discos precisam de 15 movimentos e dez discos precisam de 1,023 movimentos.

A complexidade de tempo é O(2^n) porque cada disco adicional dobra o trabalho. A recorrência T(n) = 2T(n-1) + 1 resulta em 2^n – 1, que é exponencial.

A complexidade espacial é O(n) porque a pilha de chamadas de recursão comporta um quadro para cada disco sendo processado. A profundidade máxima de recursão atinge n, portanto a memória auxiliar necessária é linear em relação ao número de discos.

Sim. Uma solução iterativa usa um loop com um padrão fixo: em movimentos ímpares, o disco menor é trocado ciclicamente entre os pinos, e em movimentos pares, o único movimento válido que não seja o menor é realizado.

O algoritmo ensina recursão, modela esquemas de rotação de backup para armazenamento, orienta o sequenciamento de braços robóticos e aparece em testes neuropsicológicos que medem a capacidade de planejamento.

Agentes de aprendizado por reforço resolvem o problema das Torres de Hanói tratando cada configuração de disco como um estado e cada movimento como uma ação. É um benchmark comum para planejamento e aprendizado de políticas hierárquicas.

Sim. GitHub Copilot, ChatGPT e Gemini gerar soluções recursivas para a Torre de Hanói em Python, C++ e JavaOs desenvolvedores ainda devem verificar os casos base e a ordem dos argumentos.

Algoritmo da Torre de Hanói: Python, C++ Code

O que é a Torre de Hanói?

Regras da Torre de Hanói

Algoritmo para Torre de Hanói

Como resolver o quebra-cabeça da Torre de Hanói

Apelido Code para a Torre de Hanói

Código do programa em C++

Código do programa em Python

Complexidade da Torre de Hanói

Perguntas Frequentes

Resuma esta postagem com:

Assine a newsletter

O que é a Torre de Hanói?

Regras da Torre de Hanói

Algoritmo para Torre de Hanói

Como resolver o quebra-cabeça da Torre de Hanói

ARTIGOS RELACIONADOS

Apelido Code para a Torre de Hanói

Código do programa em C++

Código do programa em Python

Complexidade da Torre de Hanói

Perguntas Frequentes

Resuma esta postagem com:

Assine a newsletter