Aeae ae
1010 palavras
5 páginas
Departamento de Ciência da Computação – IME-USPMAC2166 Introdução à Computação para Engenharia
Escola Politécnica – Primeiro Semestre de 2012
Primeiro Exercício-Programa (EP1)
Data máxima para entrega: 24/03/2012 versão 1.2
12 de março de 2012
1
Introdução
Os dois primeiros exercícios-programa, EP1 e EP2, estão relacionados com o quebracabeça Torre de Hanói. Este enunciado apresenta o quebra-cabeça e descreve o que deve ser feito no EP1.
2
Torre de Hanói
A Torre de Hanói é um quebra-cabeça popular1 , no qual existem n discos de tamanhos diferentes, numerados de 1 a n, e três pinos identificados pelas letras A, B e C. O disco 1 é menor que o disco 2 que é menor que o disco 3 . . . que é menor que o disco n. Inicialmente os discos estão ordenados pelos seus tamanhos empilhados em um dos pinos, sendo que o disco n (maior) está na base e o disco 1 (menor) está no topo. Abaixo pode ser vista a configuração inicial do quebra-cabeça com n = 8 discos.
Figura obtida de Wikipedia, the free encyclopedia
(http://en.wikipedia.org/wiki/Tower_of_Hanoi)
1
Até os macacos do filme Planeta dos Macacos: A Origem (Rise of the Planet of the Apes ) conseguem resolver o quebra-cabeça Torre de Hanói!
Introdução
2
O objetivo do quebra-cabeça é transferir os n discos de um pino origem para outro pino destino, um por vez, usando eventualmente o terceiro pino como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor.
3
Uma possível solução
Suponha que os pinos são representados pelas letras A, B, e C e que inicialmente todos os n discos estão no pino origem A. Uma maneira conhecida para resolver o quebra-cabeça é repetir a seguinte sequência de três movimentos até que a solução seja obtida:
• se n é par
– realizar o movimento válido entre os pinos A e B
– realizar o movimento válido entre os pinos A e C
– realizar o movimento válido entre os pinos B e C
• se n é impar
– realizar o movimento válido entre os