Aeae ae

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1010 palavras )
  • Download(s) : 0
  • Publicado : 2 de maio de 2012
Ler documento completo
Amostra do texto
Departamento de Ciência da Computação – IME-USP

MAC2166 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 enunciadoapresenta 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 seustamanhos 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 resolvero 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 inicialmentetodos
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 ospinos A e C
– realizar o movimento válido entre os pinos A e B
– realizar o movimento válido entre os pinos B e C
Por exemplo, se tivermos n = 3 discos, inicialmente no pino A, e desejarmos transferílos para o pino C, teremos a seguinte sequência de configurações.
1
2
3
----------A
B
C
1
3
2
----------A
B
C
2
1
3
----------A
B
C

---->

---->

---->

2
3
1
----------AB
C
1
2
3
----------A
B
C

---->

---->

3
2
1
----------A
B
C
1
2
3
----------A
B
C

---->

---->

1
2
3
----------A
B
C

Uma animação da solução para 4 discos pode ser vista em https://en.wikipedia.
org/wiki/File:Tower_of_Hanoi_4.gif.

Introdução

4

3

Configurações e movimentos válidos

Uma configuração de um pino será representada por umasequência de n inteiros
entre 0 e n. Os inteiros entre 1 e n representam os discos e as posições vazias no topo são
representadas pelo número 0. Por exemplo, para
1
3
2
----------A
B
C
a configuração do pino A é 3 0 0, a do pino B é 2 1 0 e a do pino C é 0 0 0.
Um movimento de um disco de um pino para outro, digamos, de A para B, é válido
se o disco no topo de A é menor que o do topo de B.Nesta situação pode-se transferir o
disco do topo de A para o topo de B.

5

O quê você deve fazer

No EP1 serão considerados apenas dois pinos A e B e 4 discos. Você deverá fazer um
programa em linguagem C que:
• lê as configurações do pino A;
• lê as configurações do pino B;
• imprime as torres com as configuração dos dois pinos, imprimindo um hífen (’-’) no
lugar dos zeros;
• imprime umamensagem indicando se o movimento do pino A para o pino B é válido
ou não (apenas o movimento do pino A para o pino B deve ser verificado); e
• caso o movimento seja válido, imprime as torres com a configuração dos dois pinos
após o movimento.
Uma vez que neste EP só poderão ser utilizados os recursos de programação vistos em
sala de aula até a P1, restringiremos o número máximo de discos a...
tracking img