No problema da Torre de Hanoi é dada uma torre de n discos de diâmetro decrescente, colocada num de três pilares; o objectivo consiste em mover a torre para outro pilar, um disco de cada vez, de modo a nunca colocar um disco maior sobre um outro menor.
Uma solução para este problema é dada pelo seguinte algoritmo recursivo:
- se
então basta mover o (único) disco e terminar;
- se
então…
- mover os primeiros
discos para o pilar intermédio;
- mover o último disco para o pilar final;
- por fim, mover os
discos para o pilar final.
(a) Encontre uma fórmula de recorrência para o número
de movimentos necessários para mover uma torre com
discos.
(b) Calcule (usando a fórmula de recorrência) alguns valores de
(ex.:
). Consegue © Usando indução finita, mostre que a expressão encontrada é válida.
Uma solução para este problema é dada pelo seguinte algoritmo recursivo:
(a) Encontre uma fórmula de recorrência para o número
(b) Calcule (usando a fórmula de recorrência) alguns valores de
Passo 1
Vamos analisar o enunciado do problema das Torres de Hanoi. O conteúdo principal é recursão e prova por indução. Precisamos: (1) formular a recorrência para o número de movimentos
, (2) calcular alguns valores iniciais de
, (3) encontrar uma expressão fechada para
e (4) provar por indução que essa expressão é válida para todo
.
Passo 2
Para
temos um único disco e basta um movimento, logo
. Para
, usamos o algoritmo recursivo: mover
discos para o pilar intermédio, mover o disco maior para o pilar final e depois novamente os
discos do pilar intermédio para o final. Então cada etapa de tamanho
faz dois blocos de
movimentos mais um movimento extra, resultando em
que é a fórmula de recorrência procurada.
Passo 3
Usando a recorrência
e sabendo que
, calculamos os primeiros valores:
Isso sugere que
.
Passo 4
Para resolver a recorrência de forma algébrica, podemos “desenrolar” alguns termos e observar o padrão: ao expandir sucessivamente, obtém-se
Como geralmente definimos
, o somatório geométrico leva a
Isso coincide com os valores calculados.
Passo 5
Agora fazemos a prova por indução finita em
:
Base : Temos
e
, logo a fórmula vale para
.
Passo indutivo: suponha que para algum a fórmula valha, ou seja,
. Então, para
, usando a recorrência:
Base
Passo indutivo: suponha que para algum
Assim, a fórmula vale também para
. Pelo princípio da indução, vale para todo
.
Passo 6
Concluímos que a expressão fechada para o número mínimo de movimentos na Torre de Hanoi com
discos é