Torre de Hanoi em C++: Como resolver sem recursão

 Neste tutorial de C++, vamos te mostrar como resolver o clássico problema da Torre de Hanoi, que sempre explicam por aí usando funções recursivas.

Algoritmo da Torre de Hanoi

Muitas das respostas fornecem uma solução direta que converte um algoritmo recursivo em um usando uma pilha.

Porém, existem algoritmos disponíveis que são livres de pilha e podem resolver o problema a partir do estado inicial ou de um estado intermediário.

No livro “The Tower of Hanoi — Myths and Maths” de Andreas Hinz , no capítulo 2, os autores introduzem o “Algoritmo 3: algoritmo Idle Peg” que opera com base na seguinte ideia:

1. Introduza um dedal começando no pino da fonte. A cada volta, pegue o dedal com a mão esquerda e mova-o pelos pinos em ordem, formando um ciclo.
2. Em seguida, com a mão direita, faça o único movimento legal evitando a cavilha que está bloqueada pelo dedal.
   
   
   

Nenhuma recursão necessária e nenhuma pilha de rastreamento de volta é necessária. É apenas um loop simples. Mas você precisa rastrear quais discos estão em qual pino para fazer a parte do “movimento legal”. Você pode fazer isso com uma matriz (uma localização para cada disco) ou com três pilhas, uma para cada pino.

Algoritmo 3 em pseudocódigo, do livro:

1. Parameter n: number of disks
2. Parameter i: source peg
3. Parameter j: goal peg
4.  
5. idle <- i
6. dir <- (-1)^n (j-i)
7. while not all discs are on peg j:
8. idle <- (idle + dir) mod 3
9. make legal move between pegs different from idle
10. end while

Código C++ da Torre de Hanoi

Para fazer isso em C++, simplificarei assumindo que o pino de origem é 0 e o pino de destino é 1 para eliminar a variável de direção. (Isso significa que minha implementação só funcionará corretamente para até n!) .

Usaremos pilha para cada um dos pinos para que encontrar o disco superior seja um tempo constante (e assim não preciso escrever um loop extra).

Veja o código da Torre de Hanoi em C++:

1. void tower_of_hanoi( int n ) {
2. int idle = 0;
3. std::stack<int> pegs[3];
4.  
5. // Disco numérico de 1 a n, n é o maior
6. for (int i = 0; i < n; i++ ) {
7. pegs[0].push( n - i );
8. }
9.  
10. while ( pegs[1].size() < n ) {
11. idle = (idle + 1) % 3;
12. int from, to;
13. switch (idle) {
14. case 0: from = 1; to = 2; break;
15. case 1: from = 0; to = 2; break;
16. case 2: from = 0; to = 1; break;
17. }
18. // Deve mover o disco menor para o disco maior
19. if ( pegs[from].empty() ||
20. (!pegs[to].empty() && pegs[from].top() > pegs[to].top()) ) {
21. std::swap( from, to );
22. }
23. int disc = pegs[from].top();
24. std::cout << "Mover disco " << disc << " de " << from << " para " << to << "\n";
25. pegs[from].pop();
26. pegs[to].push( disc );
27. }
28. }

O livro contém muitos outros algoritmos. Por exemplo, aqui está aquele que encontra o melhor movimento para um estado perfeito, dado qualquer estado regular arbitrário (ou seja, legal). É o algoritmo 10 no mesmo capítulo:

1. Parameter n: number of disks
2. Parameter s[1..n]: regular state, given as an array
3. Parameter j: goal peg
4.  
5. mu <- 0 // length of path
6. delta <- n+1 // active disc
7. k <- j // "state of the P1-automaton",
8. for d = n down to 1
9. if s[d] <> k then
10. mu <- mu + 2^(d-1)
11. delta <- d
12. k <- 3 - k - s[d]
13. end if
14. end for

Nenhuma pilha ou recursão é necessária! O algoritmo fornece o disco para mover e o comprimento do caminho para o estado final de nosso objetivo.