Estrutura de dados e algoritmos - Torre de Hanói

Torre de Hanoi, é um quebra-cabeça matemático que consiste em três torres (pinos) e mais de um anel conforme representado -

Esses anéis são de tamanhos diferentes e empilhados em ordem crescente, ou seja, o menor fica sobre o maior. Existem outras variações do quebra-cabeça em que o número de discos aumenta, mas a contagem de torres permanece a mesma.

Regras

A missão é mover todos os discos para alguma outra torre sem violar a sequência do arranjo. Algumas regras a serem seguidas para a Torre de Hanói são -

  • Apenas um disco pode ser movido entre as torres a qualquer momento.
  • Apenas o disco "superior" pode ser removido.
  • Nenhum disco grande pode ficar sobre um disco pequeno.

A seguir está uma representação animada da resolução de um quebra-cabeça da Torre de Hanói com três discos.

O quebra-cabeça da Torre de Hanói com n discos pode ser resolvido no mínimo 2n−1passos. Esta apresentação mostra que um quebra-cabeça com 3 discos tomou23 - 1 = 7 passos.

Algoritmo

Para escrever um algoritmo para Torre de Hanoi, primeiro precisamos aprender como resolver este problema com menor quantidade de discos, digamos → 1 ou 2. Marcamos três torres com o nome, source, destination e aux(apenas para ajudar a mover os discos). Se tivermos apenas um disco, ele pode ser facilmente movido da origem para o pino de destino.

Se tivermos 2 discos -

  • Primeiro, movemos o disco menor (superior) para aux Peg.
  • Em seguida, movemos o disco maior (inferior) para o pino de destino.
  • E, finalmente, movemos o disco menor do aux para o pino de destino.

Agora, estamos em posição de projetar um algoritmo para a Torre de Hanoi com mais de dois discos. Dividimos a pilha de discos em duas partes. O maior disco (n- ésimo disco) está em uma parte e todos os outros (n-1) discos estão na segunda parte.

Nosso objetivo final é mover o disco nda origem ao destino e, em seguida, coloque todos os outros discos (n1) nele. Podemos imaginar aplicar o mesmo de forma recursiva para todos os conjuntos de discos fornecidos.

As etapas a seguir são -

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Um algoritmo recursivo para Torre de Hanói pode ser conduzido da seguinte maneira -

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Para verificar a implementação na programação C, clique aqui .