Aluno(s):_______________________________________________________________________________Postar a soluo no SGA at a prxima segunda-feira, dia 13/abr, s 13h30.Torre de Hani (Enunciado extrado de Deitel, em C, como programar 6ed)Todo cientista da computao iniciante precisa lutar contra certos problemas clssicos, e as Torres de Hani um dos problemas mais famosos. A lenda diz que, em um templo no Extremo Oriente, sacerdotes esto tentando mover uma pilha de discos de um pino para outro. A pilha inicial tinha 64 discos dispostos em um pino e arrumados de baixo para cima por tamanho decrescente. Os sacerdotes esto tentando mover a pilha desse pino para um segundo pino sob as restries de que apenas um disco movido de cada vez, e em momento algum um disco maior pode ser colocado sobre um disco menor. Um terceiro pino est disponvel para apoioar os discos temporariamente. Supostamente, o mundo terminar quando os sacerdotes completarem sua tarefa, de modo que no temos muito incentivo para facilitar seus esforos.

Vamos supor que os sacerdotes estejam tentando mover os discos do pino 1 ao pino 3. Queremos desenvolver um algoritmo que imprimir a sequncia exata de transferncias de pino, disco a disco.

Se tivssemos que resolver esse problema com a ajuda de mtodos convencionais, ficaramos presos na administrao dos discos repetidamente. Em vez disso, se atacarmos o problema com a recurso em mente, ele imediatamente se tornar mais resolvel. Mover n discos pode ser visto em termos de mover apenas n1 discos (e da a recurso) da seguinte forma:a) Mova n1 discos do pino 1 para o pino 2, usando o pino 3 como rea de manuteno temporria.b) Mova o ltimo disco (o maior) do pino 1 para o pino 3.

c) Mova os n1 discos do pino 2 para o pino 3, usando o pino 1 como rea de manuteno temporria.O processo termina quando a ltima tarefa envolver mover n = 1 disco, ou seja, o caso bsico. Isso feito movendo o disco de modo trivial, sem a necessidade de uma rea de manuteno temporria.

Escreva um programa que resolva o problema das Torres de Hani. Use uma funo recursiva com quatro parmetros:

a) O nmero de discos a serem movidos

b) O pino no qual esses discos esto empilhados inicialmente.

c) O pino para o qual a pilha de discos deve ser movida.d) O pino a ser usado como rea de manuteno temporria.Seu programa dever imprimir as instrues exatas que ele usar para mover os discos do pino inicial para o pino de destino. Por exemplo, para mover uma pilha de trs discos do pino 1 ao pino 3, seu programa dever imprimir a seguinte sria de movimentos:

1 3 (isso significa mover um disco do pino 1 ao pino 3)1 2

3 2

1 3

2 1

2 3

1 3

Pontifcia Universidade Catlica de Minas Gerais

ICEI Instituto de Cincias Exatas e Informtica

DCC Depto de Cincia da Computao

Campus Belo Horizonte Unidade Corao Eucarstico

Bacharelado em Cincia da Computao

Algoritmos e Estruturas de Dados I

Professor: Lcio Mauro Pereira

09 de abril de 2015

Exerccios

MAIOR UNIVERSIDADE CATLICA DO MUNDO - Fonte: Vaticano

MELHOR UNIVERSIDADE PRIVADA DO BRASIL - Guia do Estudante, 2014

COMPUTAO PUC MINAS: 1 LUGAR DO BRASIL (Pref. Mercado) Folha de So Paulo, 2014

CINCIA DA COMPUTAO PUC MINAS: 4 ESTRELAS - Guia do Estudante, 2014