Uma Torre de Hanoi dupla contém
discos de
tamanhos diferentes, dois de cada tamanho. As regras de movimentação dos discos são as mesmas: um disco de cada vez e nunca colocar um disco sobre outro menor.
(a) Quantos movimentos são necessários para transferir a torre dupla de um eixo para outro, supondo que discos de mesmo tamanho sejam idênticos? Monte e resolva a relação de recorrência apropriada.
(b) Suponha agora que discos de mesmo tamanho são pintados com cores diferentes e o objetivo é transferir a torre mantendo a ordem de cores. (Dica: utilize os resultados do item anterior.)
(a) Quantos movimentos são necessários para transferir a torre dupla de um eixo para outro, supondo que discos de mesmo tamanho sejam idênticos? Monte e resolva a relação de recorrência apropriada.
(b) Suponha agora que discos de mesmo tamanho são pintados com cores diferentes e o objetivo é transferir a torre mantendo a ordem de cores. (Dica: utilize os resultados do item anterior.)
Passo 1
Primeiro vou deixar bem claro o que o enunciado pede e quais informações estão dadas.
- Temos uma “torre dupla” composta por
discos, com tamanhos distintos e exatamente dois discos de cada tamanho empilhados em ordem decrescente (maiores embaixo). - As regras são as usuais da Torre de Hanoi: mover um disco por vez e nunca colocar um disco maior sobre um disco menor. Discos de mesmo tamanho podem ser colocados uns sobre os outros (já que não são menores).
- O enunciado faz duas perguntas:
(a) Supondo que discos de mesmo tamanho são idênticos (indistinguíveis), quantos movimentos mínimos são necessários para transferir toda a torre de um pino a outro? Pede montar e resolver a relação de recorrência apropriada.
(b) Agora supondo que os dois discos de cada tamanho são pintados com cores diferentes (são distinguíveis) e que, além de transferir toda a torre, o objetivo é manter a ordem das cores (isto é, para cada par de mesmo tamanho a ordem relativa vertical entre as duas cores no final deve ser a mesma que havia no início). Usar o resultado do item (a).
Listei tudo o que está dado e o que é pedido. A partir do Passo 2 começo a resolver de fato.
Passo 2
Entendimento básico e ideia do método (sem ainda desenvolver contas). Vou trabalhar com uma abordagem recursiva, que é a maneira padrão de raciocinar nesses problemas:
- Para esse tipo de problema a estratégia natural é: para mover todos os discos de tamanho
(isto é, todos os discos) do pino origem para o pino destino usando como auxiliar, a manobra costuma dividir-se em: mover os discos menores (todos os discos de tamanhos ) para um pino auxiliar, depois mover os discos de maior tamanho, depois recolocar os menores sobre o destino. A diferença entre os dois itens do enunciado está em como tratamos o par de discos de cada tamanho: se são idênticos (item a) ou distinguíveis e com ordem a preservar (item b). - Vou formalizar essas ideias em uma relação de recorrência e resolver essa recorrência de maneira clara e didática.
Agora sim, começo o desenvolvimento e as contas explicadas passo a passo.
Passo 3
Resolução do item (a): montar a recorrência.
Observação sobre a configuração inicial e a operação necessária:
- Para mover a torre inteira com os
discos (dois de cada tamanho ) do pino para o pino , em todo o momento a regra vale: não se pode colocar um disco maior sobre um disco menor; porém discos de mesmo tamanho podem ser colocados sobre um igual (pois não são menores). - A estratégia recursiva natural é:
- Primeiro mover todos os discos de tamanhos
(ou seja, os discos menores) do pino para o pino . Se chamarmos o número mínimo de movimentos para transferir a torre dupla de parâmetros (isto é, discos, dois de cada tamanho até ), esse passo toma movimentos. - Depois, com os menores fora do caminho, os dois discos de tamanho
(os maiores) estão agora acessíveis no topo de . Como os discos de mesmo tamanho são idênticos, posso movê-los para o destino em dois movimentos consecutivos: mover o disco que está mais em cima (o de tamanho ) para e depois o outro disco de tamanho para . Colocar um disco de tamanho sobre outro do mesmo tamanho é permitido. Esse passo usa exatamente movimentos. - Finalmente, mover os
discos menores que estavam em para sobre os discos de tamanho ; isso custa novamente movimentos.
- Primeiro mover todos os discos de tamanhos
- Portanto a relação de recorrência é
com condição inicial (caso base) quando
: há dois discos de mesmo tamanho, empilhados; para transferi-los, basta movê-los um a um para o destino, totalizando
movimentos.
Passo 4
Resolver a recorrência do item (a) e interpretar pedagogicamente.
Temos a recorrência linear de primeira ordem não-homogênea
Vou resolver passo a passo:
- Primeiro resolvo a parte homogênea
. Isso dá (constante determinada por condição inicial). - Agora procuro uma solução particular constante
. Substituindo em obtém-se . - Assim a solução geral é
- Uso
para achar :
- Portanto
Interpretação intuitiva rápida: cresce exponencialmente com
; para
dá
, para
dá
, para
dá
etc. A forma
é explícita e fácil de memorizar.
Passo 5
Resumo didático do item (a) (como você usaria na prova):
- Monta-se a recursão pensando em “retirar” todos os discos menores para um pino auxiliar, mover os dois maiores (2 movimentos porque são iguais) e recolocar os menores. Isso motiva
. - Resolve-se a recorrência (como fiz acima) e obtém-se
. - Exemplo numérico: para
(quatro discos no total) são movimentos mínimos.
Agora vou ao item (b), explicando com calma a diferença conceitual e a solução.
Passo 6
Entendendo o item (b) e estratégia geral.
- Agora os dois discos de cada tamanho são distinguíveis (por cores) e o enunciado exige que, além de transferir toda a torre, a ordem de cores de cada par seja preservada. Isso significa: se, no pino inicial
, para um determinado tamanho o disco da cor X está acima do disco da cor Y, no pino final o disco X deverá continuar acima de Y. Em outras palavras, não se pode trocar a ordem vertical dos dois discos de mesmo tamanho. - No item (a), quando os discos do mesmo tamanho são idênticos, mover os dois discos daquele nível para o destino em dois movimentos não impõe restrição de ordem; porém agora a ordem importa: mover o disco que estava por cima primeiro para o destino e em seguida mover o de baixo para o destino inverteria a ordem relativa desses dois discos (porque o segundo viria a ficar sobre o primeiro). Para preservar a ordem, é necessário um procedimento que coloque os dois discos no destino na mesma ordem relativa em que estavam no início.
- Consequentemente, para cada par de discos de tamanho
que na origem está configurado (cima = cor A, baixo = cor B), a manobra que os coloca no destino na mesma ordem requer uma pequena sequência extra: é preciso retirar temporariamente o disco de cima para algum pino auxiliar, mover o disco de baixo para o destino e então recolocar o disco de cima sobre ele — essa sequência de recolocação do par (quando feita sem outros discos atrapalhando) leva movimentos em vez de . - Porém, na presença de todos os outros discos (os menores), ganhar espaço e peões livres exige mover esses menores várias vezes. Por isso a conta global resulta numa recorrência diferente da do item (a) e que incorpora as operações de “criar espaço” e “recolocar” os menores várias vezes.
Vou agora montar a recorrência adequada aproveitando o raciocínio acima e o resultado do item (a).
Passo 7
Montagem da recorrência para o item (b) (passo a passo explicando cada termo).
Denoto por
o número mínimo de movimentos necessários quando os discos de cada tamanho são distinguíveis e a ordem das cores deve ser preservada.
Raciocínio recursivo (idéia central):
- Para lidar com o par de tamanho
(os dois maiores) mantendo a ordem, não basta simplesmente mover os dois discos em 2 movimentos como no item (a); é preciso, na prática, efetuar uma operação que equivale a “trocar” a ordem de colocação ou então usar um pino auxiliar para temporariamente armazenar um dos dois discos de tamanho enquanto se posiciona o outro. Essa manobra, por si só, exige 3 movimentos diretos para os próprios dois discos de tamanho (quando não há menores no meio): retirar o de cima para um pino auxiliar (1), mover o de baixo para o destino (1), recolocar o de cima sobre ele no destino (1) — total 3. - Porém, para poder armazenar temporariamente o disco superior de tamanho
num pino auxiliar, é necessário que esse pino auxiliar esteja livre de discos menores; por isso os discos menores precisam ser deslocados várias vezes durante o processo de ordenação do par de tamanho . - Um método eficiente (que se mostra ótimo por raciocínio recursivo) é o seguinte procedimento para mover todos os
discos preservando todas as ordens de cor: - Mover os
discos menores de para um pino (digamos ) obedecendo à regra de preservação de ordem — isso custa . - Mover o disco de cima do par de tamanho
para o pino destino auxiliar (uma operação que, devido à presença dos menores em , exige que se libere espaço — a forma mais econômica de fazer isso, em recursão, equivale a movimentos adicionais de custo ou a mover os menores entre pinos; no efeito global isso equivale a incorrer em duas transferências dos menores). - Executar os 3 movimentos que colocam os dois discos de tamanho
no pino destino na ordem correta. - Recolocar os
discos sobre o destino preservando ordem — outro custo .
- Mover os
- Ao contabilizar as transferências necessárias dos menores para conseguir um pino temporário livre e depois recolocá-los, chega-se à recorrência (que é a forma “canônica” para este problema): cada nível exige basicamente três transferências completas da pilha menor (do tipo que custa
em preservação de ordem), mais 3 movimentos para arrumar o par de tamanho . Assim obtemos
Explicação dos termos:
- O termo
representa: mover a pilha menor para liberar espaço, depois movê-la novamente para fazer a manobra intermediária e, por fim, recolocá-la sobre o destino (três transferências recursivas da pilha de tamanho , cada uma custando ). - O
cobre os três movimentos estritos necessários para colocar os dois discos de maior tamanho no destino mantendo a ordem (guardar o de cima em peg auxiliar, mover o de baixo para o destino, recolocar o de cima sobre ele).
Observação pedagógica: esta recorrência pode ser entendida como uma versão “triplicada” da recorrência do caso idêntico, porque para preservar a ordem precisa-se, em essência, deslocar a pilha menor mais vezes para criar espaço de armazenagem temporária.
Passo 8
Resolver a recorrência do item (b).
A recorrência é
Resolver de forma direta:
- Parte homogênea:
tem solução . - Procuro solução particular constante
. Substituindo: dá . Para evitar frações podemos preferir outro método, mas continuarei algebraicamente. - Assim solução geral:
- Use
para achar :
- Então
- Podemos reescrever de forma concreta:
- Multiplicando por
e simplificando, outra forma útil é
Verificação rápida de pequenos
:
- Para
: , compatível com a observação direta (dois discos de mesmo tamanho, mas distinguíveis — para preservar a ordem é preciso 3 movimentos). - Para
: . (Isso dá um valor plausível entre o caso idêntico e o caso todos distintos .)
Passo 9
Interpretação e como usar isso na prova (dicas de memorização/checagem).
- Item (a): a relação simples
resolve-se diretamente e dá . Lembre-se: “duas transferências dos menores + dois movimentos dos dois maiores”. - Item (b): a necessidade de preservar a ordem entre os dois discos de cada tamanho força repetir as transferências da pilha menor mais vezes para liberar e reutilizar um pino auxiliar; isso leva à recorrência
e à solução fechada . Na prova, explique por que são três transferências da pilha menor (liberar, reorganizar, recolocar) e por que o par maior exige 3 movimentos, e então resolva a recorrência.
Resposta
(a)
(b)