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

O que é a Torre de Hanói?

A Torre de Hanói é um quebra-cabeça matemático composto por três hastes e vários discos colocados uns sobre os outros. Também é conhecida como Torre de Brahma ou Torre de Lucas, como o matemático francês Edouard Lucas a introduziu em 1883. Este 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. Essas hastes são projetadas como torres cíclicas. Assim, os discos maiores em diâmetro são empilhados na parte inferior e os discos menores são empilhados na parte superior.

Inicialmente, recebemos três estacas ou hastes. E um deles (A, mostrado no exemplo) tem todos os discos empilhados. Nosso objetivo é mover uma pilha inteira de discos de uma haste (A) para outra (C) obedecendo a algumas regras específicas.

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

E este é o objetivo final-

Regras da Torre de Hanói

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

• No estado inicial deste quebra-cabeça, todos os discos serão empilhados na haste um.
• O estado final é que todos os discos da barra um serão empilhados na barra dois ou na barra três.
• Podemos mover um disco de uma haste para outra a qualquer momento.
• Só podemos mover o disco superior da haste.
• Um disco não pode ser colocado sobre outro disco, que é menor.

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

Portanto, se os sacerdotes precisassem de 1 segundo para mover os discos, o tempo total necessário para resolver o quebra-cabeça seria 2 ^ 64 – 1 segundo ou 584,942,417,356 anos, 26 dias, 7 horas e 15 segundos.

Algoritmo para Torre de Hanói

Uma maneira geral de resolver a Torre de Hanói é um algoritmo recursivo. Primeiro, precisamos decidir sobre duas hastes ou estacas como origem e destino, e a estaca sobressalente seria auxiliar ou 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.
• Depois, mova o enésimo disco do pino de origem para o pino de destino.
• Finalmente, mova os n-1 discos restantes do pino auxiliar para o pino de destino.

Note: Se tivermos um único disco, podemos movê-lo diretamente da origem ao destino.

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

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

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

Nesta fase:

Fonte = Peg A
Destino = Peg C
Ajudante = Peg B

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

Nota: Embora só possamos mover um disco por vez, isso divide nosso problema de um problema de 3 discos para um problema de 2 discos, que é uma chamada recursiva.

Passo 2) Como chamamos uma chamada recursiva do pino A e o destino é o pino B, usaremos o pino C como auxiliar.

Observe que estamos novamente no estágio um para o mesmo problema da torre de Hanói para dois discos.

Agora precisamos mover n-1 ou um disco da origem para o auxiliar, movendo o menor disco do pino A para o pino C.

Nesta fase:

Fonte = pino A
Destino = pino B
Auxiliar = pino C

Passo 3) Então, de acordo com nosso algoritmo, o enésimo ou segundo disco necessário deve ser transferido para o destino ou pino B.

Nesta fase:

Fonte = pino A
Destino = pino B
Auxiliar = pino C

Passo 4) Agora, moveremos os n-1 discos ou disco um do auxiliar ou pino C para o destino ou pino B de acordo com o terceiro estágio de nosso algoritmo.

Nesta fase:

Fonte = pino A
Destino = pino B
Auxiliar = pino C

Passo 5) Após concluir a chamada recursiva, retornaremos à nossa configuração anterior no primeiro estágio do algoritmo.

Passo 6) Agora, no segundo estágio, moveremos nossa origem para nosso destino, que é mover o disco 3 do pino A para o pino C.

Nesta fase:

Fonte = pino A
Destino = pino C
Auxiliar = pino B

Passo 7) Agora podemos ver isso

d é mover os discos restantes do auxiliar (ponto B) para o destino (ponto C). Usaremos a fonte inicial ou pino A como auxiliar neste caso.

Passo 8) Como não podemos mover dois discos simultaneamente, chamaremos uma chamada recursiva para o disco 1. De acordo com o último passo e nosso algoritmo, um destino nesta etapa é o pino A.

Nesta fase:

Fonte = pino B
Destino = pino A
Auxiliar = pino C

Passo 9) Nossa chamada recursiva está concluída agora. Em seguida, movemos o disco 2 da origem para o destino.

Nesta fase:

Fonte = pino B
Destino = pino C
Auxiliar = pino A

Passo 10) Em seguida, movemos nosso n-1 ou disco 1 restante do auxiliar para o destino.

Nesta fase:

Fonte = pino A
Destino = pino C
Auxiliar = pino B

Pseudocódigo da 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 de tempo e espaço da Torre de Hanói:

1) Complexidade de tempo:

Se olharmos novamente para o nosso algoritmo, podemos ver que estamos introduzindo uma chamada recursiva para (n-1) discos duas vezes. Essas chamadas recursivas para (n-1) discos podem ser divididas em outros ((n-1)-1) e assim por diante até conseguirmos mover apenas um disco.

Para três discos-

• O disco 3 chama uma função recursiva para o disco dois duas vezes.
• O disco 2 chama uma função recursiva para o disco um duas vezes.
• O disco 1 pode se mover dentro de um tempo constante e um tempo para resolver três discos.

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

= 2*(2*tempo para resolver 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, pode ser escrito como –

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

Esta progressão geométrica resultará em O(2^n-1) ou O (2ⁿ), que é exponencial.

2) Complexidade espacial

A complexidade espacial da Torre de Hanói é 0(n). Isso porque precisamos armazenar a sequência das placas. Quando usamos a recursão, estamos usando a pilha. E o tamanho máximo da pilha pode ser “n”. É por isso que a complexidade do espaço se torna O(n).