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 n=1 então basta mover o (único) disco e terminar;
  • se n>1 então…
  • mover os primeiros n-1 discos para o pilar intermédio;
  • mover o último disco para o pilar final;
  • por fim, mover os n-1 discos para o pilar final.
    (a) Encontre uma fórmula de recorrência para o número Tn de movimentos necessários para mover uma torre com n discos.
    (b) Calcule (usando a fórmula de recorrência) alguns valores de Tn (ex.: n=1,2,3,4,5 ). Consegue © Usando indução finita, mostre que a expressão encontrada é válida.

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 Tn, (2) calcular alguns valores iniciais de Tn, (3) encontrar uma expressão fechada para Tn e (4) provar por indução que essa expressão é válida para todo n.

Passo 2

Para n=1 temos um único disco e basta um movimento, logo T1 = 1. Para n > 1, usamos o algoritmo recursivo: mover n-1 discos para o pilar intermédio, mover o disco maior para o pilar final e depois novamente os n-1 discos do pilar intermédio para o final. Então cada etapa de tamanho n faz dois blocos de Tn-1 movimentos mais um movimento extra, resultando em
Tn = 2,Tn-1 + 1
que é a fórmula de recorrência procurada.

Passo 3

Usando a recorrência Tn = 2,Tn-1 + 1 e sabendo que T1 = 1, calculamos os primeiros valores:
T1 = 1
T2 = 2,T1 + 1 = 2 times 1 + 1 = 3
T3 = 2,T2 + 1 = 2 times 3 + 1 = 7
T4 = 2,T3 + 1 = 2 times 7 + 1 = 15
T5 = 2,T4 + 1 = 2 times 15 + 1 = 31
Isso sugere que Tn = 2^n - 1.

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
Tn = 2^n T0 + (2^n-1 + 2^n-2 + cdots + 2 + 1)
Como geralmente definimos T0 = 0, o somatório geométrico leva a
Tn = 2^n - 1
Isso coincide com os valores calculados.

Passo 5

Agora fazemos a prova por indução finita em n:
Base n=1: Temos T1 = 1 e 2^1 - 1 = 1, logo a fórmula vale para n=1.
Passo indutivo: suponha que para algum k >= 1 a fórmula valha, ou seja, Tk = 2^k - 1. Então, para n = k+1, usando a recorrência:
Tk+1 = 2,Tk + 1 = 2(2^k - 1) + 1 = 2^k+1 - 2 + 1 = 2^k+1 -1
Assim, a fórmula vale também para n = k+1. Pelo princípio da indução, vale para todo n>=1.

Passo 6

Concluímos que a expressão fechada para o número mínimo de movimentos na Torre de Hanoi com n discos é
Tn = 2^n - 1

Resposta

Tn = 2^n - 1

Exercícios relacionados