Torre de Hanói

Torre de Han´i. o Realizado a luz da Prof.a: Edite Taufer.
´
BRUNO K Samaniego.
71666
D. Hans A. Montcho.
65834

´
DEBORA Lima.
65659
L. Henrique S. Pereira.
72567

10 de Janeiro de 2014.

Sum´rio a 0.1
0.2
0.3
0.4
0.5

Introdu¸ao a historia da Torre c˜ Objetivo. . . . . . . . . . . . .
Desenvolvimento. . . . . . . .
Conclus˜o. . . . . . . . . . . . a Anexo. . . . . . . . . . . . . .

1

de Hanoi
. . . . . .
. . . . . .
. . . . . .
. . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2
2
2
4
5

Introdu¸˜o ca 0.1

Introdu¸˜o a historia da Torre de Hanoi ca Reza a lenda que em um templo na china, um monge para melhorar o esp´ ırito de trabalho dos seus sacerdotes, lhes deu uma tarefa que consiste em deslocar
64 discos de um pino A para um pino C tendo um B como intermedi´rio e a seguindo essas regras: So devem deslocar um disco por vez. Nunca um disco maior deve ficar por cima de um menor. Porem o que isso tem a ver com matem´tica? Pois bem, em 1883 o matem´tico francˆs Edouard Lucas, a a e oficializou o jogo que hoje ´ conhecido como jogo da Torre de Han´i, tendo e o o objetivo de determinar o menor n´mero de movimentos para completar o u jogo, usando a matem´tica. a 0.2

Objetivo.

Encotrar o menor n´mero de movimento para completar o jogo. u 0.3

Desenvolvimento.

Seja n o n´mero de disco e f (n) o menor n´mero de movimentos. Repetindo u u v´rias vezes o jogo chegamos a esse algoritmo para realizar-lo. a 1) Mover os (n − 1) primeiros discos do pino A para B, isso resultar´ em a f (n − 1) movimento.
2) Mover o ultimo disco de A para o C ⇒ 1 movimento.
´
3) Mover os (n − 1) discos de B para C ⇒ f (n − 1) movimentos.

2

Logo;

f(n)=f(n-1)+1+f(n-1)

f (n) = 2(n − 1) + 1

 f (n) + 1 = 2(n − 1) +