Torre de Hanoí

por ThaisP Qui 30 Jan 2014, 14:53

A Torre de Hanói é um "quebra-cabeça" que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.

um estudante percebeu que o número mínimo de movimentos necessários para trasnferir todos os discos obedecia a uma relação matemática.
Para mover o primeiro disco da torre original, 1 movimento é gasto, construindo a torre com os 2 menores discos são gastos 2 movimentos.
Para deslocar o terceiro disco, formando uma nova torre com 3 menores discos, são gasto 4 movimentos, e assim sucessivamente.
Desse modo, ele concluiu que , para solucionar esse jogo com 4 e 7 discos , são necessários 15 e 127 movimentos respectivamente. Para solucionar o jogo com 10 torres são necessários no mínimo:
resposta: 1023

por favor me ajudem, estou tentando há bastante tempo =C

por **Elcioschin** Qui 30 Jan 2014, 15:04

1 disco -----> 2^1 - 1 = 1
2 discos ---> 2^2 - 1 = 3
3 discos ---> 2^3 - 1 = 7
4 discos ---> 2^4 - 1 = 15
7 discos ---> 2^7 - 1 = 127
........................................
10 discos ---> 2^10 - 1 = 1023

n discos -----> 2^n - 1

por ThaisP Qui 30 Jan 2014, 15:05

Nossa que legal
obrigada !!

por PedroCunha Qui 30 Jan 2014, 15:11

Veja:

4 discos - 15 movimentos - 15 = 2^4 - 1
7 discos - 127 movimentos - 127 = 2^7 - 1
10 discos - 2^{10} - 1 = 1023

Penso que seja isso.

Att.,
Pedro