Skip to main content
As imagens em ASCII não carregavam bem no celular, mudei para imagens
Fonte Link
Woss
  • 77,2mil
  • 15
  • 123
  • 221
   ┌──┴──┐            │               │
   └──┬──┘            │               │
  ┌───┴───┐           │               │
  └───┬───┘           │               │
 ┌────┴────┐          │               │
 └────┬────┘          │               │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

inserir a descrição da imagem aqui

   ┌──┴──┐            │               │
   └──┬──┘            │               │
  ┌───┴───┐           │               │
  └───┬───┘           │               │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

inserir a descrição da imagem aqui

      │               │               │
      │               │               │       
      │            ┌──┴──┐            │
      │            └──┬──┘            │ 
 ┌────┴────┐      ┌───┴───┐           │
 └────┬────┘      └───┬───┘           │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

inserir a descrição da imagem aqui

      │               │               │      
      │               │               │      
      │            ┌──┴──┐            │      
      │            └──┬──┘            │      
      │           ┌───┴───┐      ┌────┴────┐ 
      │           └───┬───┘      └────┬────┘ 
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

inserir a descrição da imagem aqui

      │               │            ┌──┴──┐   
      │               │            └──┬──┘   
      │               │           ┌───┴───┐  
      │               │           └───┬───┘  
      │               │          ┌────┴────┐ 
      │               │          └────┬────┘ 
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

inserir a descrição da imagem aqui

Então, assim, para resolver uma torre de 3 discos ele precisa saber resolver uma de 2 discos; para resolver a de 2 discos precisa saber resolver uma de 1 disco; ele sabe resolver de 1 disco. Isso funcionará para qualquer quantidade de discos e três torres.

Veja Determinar o n-ésimo termo de Fibonacci com recursividade para mais informações de como funciona a recursividade.

   ┌──┴──┐            │               │
   └──┬──┘            │               │
  ┌───┴───┐           │               │
  └───┬───┘           │               │
 ┌────┴────┐          │               │
 └────┬────┘          │               │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C
   ┌──┴──┐            │               │
   └──┬──┘            │               │
  ┌───┴───┐           │               │
  └───┬───┘           │               │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C
      │               │               │
      │               │               │       
      │            ┌──┴──┐            │
      │            └──┬──┘            │ 
 ┌────┴────┐      ┌───┴───┐           │
 └────┬────┘      └───┬───┘           │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C
      │               │               │      
      │               │               │      
      │            ┌──┴──┐            │      
      │            └──┬──┘            │      
      │           ┌───┴───┐      ┌────┴────┐ 
      │           └───┬───┘      └────┬────┘ 
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C
      │               │            ┌──┴──┐   
      │               │            └──┬──┘   
      │               │           ┌───┴───┐  
      │               │           └───┬───┘  
      │               │          ┌────┴────┐ 
      │               │          └────┬────┘ 
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

Então, assim, para resolver uma torre de 3 discos ele precisa saber resolver uma de 2 discos; para resolver a de 2 discos precisa saber resolver uma de 1 disco; ele sabe resolver de 1 disco. Isso funcionará para qualquer quantidade de discos e três torres.

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

inserir a descrição da imagem aqui

Então, assim, para resolver uma torre de 3 discos ele precisa saber resolver uma de 2 discos; para resolver a de 2 discos precisa saber resolver uma de 1 disco; ele sabe resolver de 1 disco. Isso funcionará para qualquer quantidade de discos e três torres.

Veja Determinar o n-ésimo termo de Fibonacci com recursividade para mais informações de como funciona a recursividade.

Fonte Link
Woss
  • 77,2mil
  • 15
  • 123
  • 221

Esse é um caso que para você entender como foi desenvolvido a função para resolver a torre de Hanoi você precisa considerar que já existe uma função para resolver a torre de Hanoi. Confuso? Não, recursivo.

   ┌──┴──┐            │               │
   └──┬──┘            │               │
  ┌───┴───┐           │               │
  └───┬───┘           │               │
 ┌────┴────┐          │               │
 └────┬────┘          │               │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

Vamos considerar que nosso objetivo é passar os discos de A para C, sendo B nosso auxiliar. Para que o resultado seja válido, o disco 3 deve ser o primeiro em C, correto? Para movermos o disco 3 para C precisaremos mover primeiro os discos 1 e 2 para B.

O problema de mover os discos 1 e 2 para B também é uma torre de Hanoi, mas agora de 2 discos:

   ┌──┴──┐            │               │
   └──┬──┘            │               │
  ┌───┴───┐           │               │
  └───┬───┘           │               │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

E nesse caso a torre C será nossa auxiliar. Lembra que eu disse no início que você precisa considerar que já existe uma função que resolve a torre de Hanoi? Então, chamamos ela para resolver a torre com 2 discos e teremos:

      │               │               │
      │               │               │       
      │            ┌──┴──┐            │
      │            └──┬──┘            │ 
 ┌────┴────┐      ┌───┴───┐           │
 └────┬────┘      └───┬───┘           │
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

Agora basta mover o disco 3 para C.

      │               │               │      
      │               │               │      
      │            ┌──┴──┐            │      
      │            └──┬──┘            │      
      │           ┌───┴───┐      ┌────┴────┐ 
      │           └───┬───┘      └────┬────┘ 
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

Para mover os discos 1 e 2 para C teremos outra torre de Hanoi com 2 discos para resolver, agora com a origem em B, destino em C, com a torre A como auxiliar. Por sorte já temos uma função que resolve isso.

Feito isso, teremos a torre completamente resolvida.

      │               │            ┌──┴──┐   
      │               │            └──┬──┘   
      │               │           ┌───┴───┐  
      │               │           └───┬───┘  
      │               │          ┌────┴────┐ 
      │               │          └────┬────┘ 
╔═════╧═════╗   ╔═════╧═════╗   ╔═════╧═════╗
      A               B               C

Ou seja, para resolver a torre para 3 discos, mudando de A para C, com B auxiliar, fizemos:

  1. Resolvemos a torre de Hanoi com 2 discos de A para B, com C auxiliar;
  2. Movemos o disco 3 de A para C;
  3. Resolvemos a torre de Hanoi com 2 discos de B para C, com A auxiliar;

Correto? Agora reveja o código (simplificado):

def tower_of_hanoi(disc, orig, dest, aux):

    # 1. Resolve a torre de Hanoi para n-1 discos, movendo para o disco auxiliar:
    tower_of_hanoi(disc-1, orig, aux, dest)

    # 2. Move o maior disco para a torre destino:
    print('Move disc {} from tower {} to the tower {}'.format(disc, orig, dest))

    # 3. Resolve a torre de Hanoi para n-1 discos, movendo da torre auxiliar para a destino:
    tower_of_hanoi(disc - 1, aux, ori, dest)

Pronto, a mágica foi feita.

Mas aí você pensa: "Ok, mas como resolver a torre de Hanoi para 2 discos?". Simples, é a mesma lógica (por isso é recursivo). Quando for resolver a torre para 2 discos você antes resolve para 1 disco (n-1), porém, quando você possui apenas 1 disco não tem muito segredo, você pode movê-lo livremente. Com isso criamos a nossa condição de parada da recursividade: se a torre possuir apenas 1 disco, move-o e finaliza a função.

Isso é implementado pelo if:

# Se possuir apenas 1 disco:
if disc == 1:
    # Move o disco e finaliza a função
    print('Move disc {} from tower {} to the tower{}'.format(disc, ori, dest))
    return

Então, assim, para resolver uma torre de 3 discos ele precisa saber resolver uma de 2 discos; para resolver a de 2 discos precisa saber resolver uma de 1 disco; ele sabe resolver de 1 disco. Isso funcionará para qualquer quantidade de discos e três torres.