Torres de Hanoi

Se você tiver lido o tutorial sobre recursividade, então você está pronto para ver outro problema em que a recursividade múltipla realmente ajuda. Ele é chamado de Torres de Hanói. Você tem um conjunto de três pinos e $n$‍ discos, cada um de um tamanho diferente. Vamos chamar os pinos de A, B, e C, e vamos numerar os discos de 1, o menor disco, até $n$‍, o maior disco. No fim, todos os $n$‍ discos estarão no pino A, em ordem decrescente de tamanho de baixo para cima, de forma que o disco $n$‍ esteja no fundo e o disco 1 esteja no topo. É assim que as Torres de Hanói ficam para $n=5$‍ discos:

O objetivo é mover todos os $n$‍ discos do pino A para o pino B:

Parece fácil, não? Mas não é tão simples, porque você deve obedecer a duas regras:

Você pode achar que esse problema não é terrivelmente importante. Au contraire! A lenda diz que, em algum lugar da Ásia (Tibete, Vietnã, Índia — escolha na internet a lenda que preferir), monges estão solucionando esse problema com um conjunto de 64 discos, e — é o que a história diz — os monges acreditam que quando terminarem de mover todos os 64 discos do pino A para o pino B de acordo com as duas regras, o mundo vai acabar. Se os monges tiverem razão, deveríamos estar correndo pelas ruas em pânico?

Primeiro, vamos ver como solucionar esse problema recursivamente. Vamos começar com um caso realmente fácil: um disco, ou seja, $n=1$‍. O caso $n=1$‍ será nosso caso base. Você sempre pode mover o disco 1 do pino A para o pino B, porque sabe que quaisquer discos abaixo dele devem ser maiores. E não há nada especial sobre os pinos A e B. Você pode mover o disco 1 do pino B para o pino C se quiser, do pino C para o pino A, ou de qualquer pino para qualquer outro pino. Solucionar o problema das Torres de Hanói com um disco é trivial, e requer mover apenas um disco uma única vez.

E quanto a dois discos? Como você pode solucionar o problema quando $n=2$‍? Você pode fazer isso em três etapas. É assim que as torres ficam no começo:

Primeiro, movemos o disco 1 do pino A para o pino C:

Note que estamos usando o pino C como um pino extra, um local para colocar o disco 1 de forma que possamos chegar ao disco 2. Agora que o disco 2 — o disco mais no fundo — está exposto, mova-o para o pino B:

Finalmente, mova o disco 1 do pino C para o pino B:

Essa solução demora três etapas, e novamente não há nada especial em mover os dois discos do pino A para o pino B. Você pode movê-los do pino B para o pino C usando o pino A como pino extra: mova o disco 1 do pino B para o pino A, então mova o disco 2 do pino B para o pino C, e termine movendo o disco 1 do pino A para o pino C. Você concorda que pode mover os discos 1 e 2 de qualquer pino para qualquer outro pino em três etapas? (Diga "sim").

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.