-
Torre de Hani
Um Modelo das Torres de Hanoi
Torre de Hani um "quebra-cabea" que consiste emuma base contendo
trs pinos, em um dos quais so dis-postos alguns discos uns sobre os
outros, em ordem cres-cente de dimetro, de cima para baixo. O
problema con-siste em passar todos os discos de um pino para
outroqualquer, usando um dos pinos como auxiliar, de maneiraque um
disco maior nunca que em cima de outro menorem nenhuma situao. O
nmero de discos pode variarsendo que o mais simples contm apenas
trs.A Torre de Hani tem sido tradicionalmente consideradacomo um
procedimento para avaliao da capacidade dememria de trabalho, e
principalmente de planejamentoe soluo de problemas.
1 OrigensO quebra-cabea foi inventado pelo matemtico
francsdouard Lucas. Ele teve inspirao de uma lenda paraconstruir o
jogo das Torres de Hani em 1883[1]. J seunome foi inspirado na
torre smbolo da cidade de Hani,no Vietn[2].Existem vrias lendas a
respeito da origem do jogo, amais conhecida diz respeito a um
templo Hindu, situ-ado no centro do universo. Diz-se que Brahma
supos-tamente havia criado uma torre com 64 discos de ouroe mais
duas estacas equilibradas sobre uma plataforma.Brahma ordenara-lhes
que movessem todos os discos deuma estaca para outra segundo as
suas instrues. As re-gras eram simples: apenas um disco poderia ser
movidopor vez e nunca um disco maior deveria car por cimade um
disco menor. Segundo a lenda, quando todos osdiscos fossem
transferidos de uma estaca para a outra, otemplo desmoronar-se-ia e
o mundo desapareceria. No claro se Lucas inventou essa lenda ou foi
inspirado porele.Existem muitas variaes sobre esta lenda. Por
exemplo,em algumas narrativas, o templo um mosteiro e os sa-
cerdotes so monges. O templo ou mosteiro pode estarem diferentes
partes do mundo - incluindo Hani, Vietn,e pode ser associado a
qualquer religio. Em algumasverses, so introduzidos outros
elementos, tais como ofacto de a torre foi criado no incio do
mundo, ou que ospadres ou monges podem fazer apenas uma mudana
pordia.
2 Solues
Soluo do problema com uma torre de quatro discos.
interessante observar que o nmero mnimo de movi-mentos para
conseguir transferir todos os discos da pri-meira estaca terceira
2n1, sendo n o nmero de dis-cos. Logo:Para solucionar um Hani de 4
discos, so necessrios 15movimentosPara solucionar um Hani de 7
discos, so necessrios127 movimentosPara solucionar um Hani de 15
discos, so necessrios32.767 movimentosPara solucionar umHani de 64
discos, como diz a lenda,so necessrios 18.446.744.073.709.551.615
movimen-tos.Para mover o primeiro disco da torre original, 1
movi-mento gasto. Para mover o segundo da torre original,sendo que
o primeiro j foi movido e ser construda umatorre com os 2 menores
discos, so gastos 2 movimentos.Para deslocar o terceiro disco
formando nova torre comos trs menores discos, tendo a torre com os
dois menoresj formada, so gastos 7 movimentos.Assim se sucede com
os prximos discos at que o en-simo disco (o ltimo) seja deslocado
compondo umatorre com os outros discos tendo uma torre com o
pe-nltimo disco e os demais juntos j formada. A suces-so formada
pela soma dos movimentos uma sucesso(1; 2; 4; 8:::2n)
1
-
2 2 SOLUES
A frmula 2n 1 provinda da soma de uma progressogeomtrica.Sabe-se
que em uma progresso geomtrica a soma deseus termos equivale a [a
(qn 1)]/q 1 , onde a o primeiro termo e q a razo.J que a razo 2 e o
primeiro termo 1 temos que [a (qn 1)]/q 1 = [1 (2n 1)]/2 1 = 2n
1Uma soluo iterativa em Java para as Torres de Hanoi.A letra A
representa o primeiro pino mais esquerda,a letra C o pino central e
a letra B representa o ltimopino para o qual todos os Disco devem
estar no nal doalgoritmo.
2.1 JAVA
import java.util.ArrayList; import java.util.Collections;import
java.util.InputMismatchException; importjava.util.List; import
java.util.Scanner; class Discoimplements Comparable{ Integer
index;String movimento; Disco(int index,String movi-mento){
this.index=index; this.movimento=movimento;} public int
compareTo(Disco o) { return in-dex.compareTo(o.index); } } public
class HanoiIterativo{ private int qtDiscos; private String
sequenciaImpa-res[] = {"A-->C, C-->B, B-->A"};//para
imparesprivate String sequenciaPares [] = {"A-->B,
B-->C,C-->A"};//para pares private List arrayDiscos= new
ArrayList(); public void lerDados() {System.out.println(Digite a
quantidade de discos);Scanner rc = new Scanner(System.in); try{
qtDis-cos = rc.nextInt(); }catch(InputMismatchExceptione){
System.out.println(Amigo! fcil! Digiteo nmero de discos por
favor!"); lerDados(); } }public void hanoi() { int maxP=(int)
Math.pow(2,qtDiscos); int y = 1; int pos =1; while(y 2){ index=0; }
} } } private void populaAr-rayImpares(int pos,int intervalos, int
maxP,int y){ intindex = 0; if(y%2==0){ for (int i = pos; i <
maxP;i+=intervalos) { Disco d = new Disco(i,
sequenciaImpa-res[index]); arrayDiscos.add(d); index++;
if(index>2){index=0; } } }else{ for (int i = pos; i 2){index=0;
} } } } public static void main(String[] args) {HanoiIterativo h =
new HanoiIterativo(); h.lerDados();
h.hanoi(); Collections.sort(h.arrayDiscos); for (Discod :
h.arrayDiscos) { System.out.println(execute:"+d.index+"
"+d.movimento); } } }
2.2 C2.2.1 Implementao do Algortimo Iterativo
/** * Resoluo do problema clssico das Torres de Ha-ni via
algortimo iterativo. * * Exemplo de compilaoe execuo no Linux: * *
prompt> gcc hanoi.c -o hanoi* prompt> ./hanoi
QUANTIDADE_DE_DISCOS * *Nota: Imprime
(2^QUANTIDADE_DE_DISCOS)1linhas de texto na sada padro. */ #include
#include /** * Core da resoluo com im-presso da sequncia tima de
movimentos. * * @paramQTD_DISCOS Quantidade de discos a
movimentarentre as 3 pilhas. */ void solve(const int QTD_DISCOS){
/* * array dos arrays de duplas, isto ; movimentos,para acesso
conforme * paridade (vide cdigo) tal queo primeiro componente de
cada dupla o * nmerode uma torre origem e o segundo o nmero de
umatorre destino */ const int ALPHA[2][3][2] = { { { 1, 3}, { 3, 2
}, { 2, 1 } }, /* PARES */ { { 1, 2 }, { 2, 3}, { 3, 1 } } /*
MPARES */ }; /* calcula o limitantedo nmero de iteraes = 2 ^
QTD_DISCOS */ constint MAX_ITER = 1
-
3linhas de texto na sada padro. */ #include #include /** * Core
da resoluo comimpresso da sequncia tima de movimentos. * *@param
QTD_DISCOS Quantidade de discos a movi-mentar. * @param origem
Nmero da torre origem. *@param destino Nmero da torre destino. *
@paramtemp Nmero da torre temporria. */ void solve(intQTD_DISCOS,
int origem, int destino, int temp) { /**Nmero de ordem de cada
movimento na sequncia deresoluo. */ static int rank = 0; if
(QTD_DISCOS >0) { solve(QTD_DISCOS-1, origem, temp,
destino);printf("%4d ) %c --> %c\n, ++rank, '@' + origem,'@' +
destino); solve(QTD_DISCOS-1, temp, destino,origem); } } /** *
Invoca o core da resoluo com oparmetro fornecido na linha de
comando e * constantesque caracterizam o problema. * * @param
Quantidadede discos a movimentar entre as 3 pilhas. */ int
main(intargc, char **argv) { int d = atoi(argv[1]); solve(d, 1,
3,2); return 0; }
3 AplicaoA Torre de Hani pode ser trabalhada em nveis de
de-senvolvimento com crianas. Na pr-escola, com regrassimples de
separao de cores e tamanhos, a torre de Ha-ni ajuda em questes de
coordenao motora, identi-cao de formas, ordem crescente e
decrescente, entreoutras formas de aprendizado.De uma maneira mais
ampla, o jogo pode ser usado parao estabelecimento de estratgias de
transferncia das pe-as, como a contagem dos movimentos e
raciocnio.Iniciando com um nmero menor de peas, ou seja,
re-solvendo problemas mais simples, teremos oportunidadede
experimentar uma das mais importantes formas de ra-ciocnio
matemtico.O jogo trabalha o desenvolvimento da lgica e do
racio-cnio matemtico. usado para desenvolver as crianas.
4 ConclusoA Torre de Hani consiste em passar todos os discos
deuma extremidade a outra sem que um disco maior queem cima de um
menor.As suas aplicaes so basicamente usadas em escolaspara que os
professores possam melhorar e desenvolver ocognitivo das crianas,
alm do trabalho em grupo. Sendoeste aplicado em pequenos grupos ou
individualmente.A Torre deHani possui vrias formas de resoluo.
Umadelas a resoluo recursiva a qual podemos dizer que a mais
limitada quanto ao tempo de realizao, j que suaexecuo depender de
alguns fatores para tornar-se maisecaz.
A resoluo Iterativa utiliza alguns ciclos (estruturas) derepetio
(for, whiles) que podem ser chamados de laos,existe ainda a
possibilidade de algumas estruturas adici-onais (mais complexas) as
quais tornam o algoritmo maisrpido. fato que todo algoritmo
recursivo possui um algoritmoiterativo equivalente; Dependendo
apenas da sua comple-xidade de construo.
5 Referncias[1] www.realidadevirtual.com.br, acesso em
28-08-2011.
[2] Jogos de Desao, Vol. 1. Editorial Salvat,
Barcelona,2005.
6 Ligaes externas Veja torre de Hanoi implementada em java. Veja
torre de Hani implementada em C# ou Csharp.
Verso eletrnica do jogo A Torre de Hanoi torres de hani com
licena GPL, com capaci-dade de auto-resolucao, em C++, usando
wxWid-gets como gui
-
4 7 FONTES, CONTRIBUIDORES E LICENAS DE TEXTO E IMAGEM
7 Fontes, contribuidores e licenas de texto e imagem7.1
Texto
Torre de Hani Fonte:
http://pt.wikipedia.org/wiki/Torre%20de%20Han%C3%B3i?oldid=40423106
Contribuidores: Paul Beppler, Ms-chlindwein, Juntas, Nuno Tavares,
Rei-artur, Leslie, Jcmo, 333, YurikBot, Luisf silva, Fernando S.
Aldado, SallesNeto BR, Ciacchi, Bigs,Leonardo.stabile, LijeBot,
Mastermorfeu, RodrigoSampaioPrimo, Rodrigozanatta, Refry, Horacio
pizzolante, Shogun Luis, Thijs!bot,Rei-bot, Joozinho, Delemon,
CommonsDelinker, Jack Bauer00, Bot-Schafter, Luckas Blade,
Carlos28, TXiKiBoT, Tumnus, Volkov-Bot, SieBot, Lechatjaune, Slomp,
BotMultichill, AlleborgoBot, Zdtrlik, GOE, Crazyaboutlost,
PequijanFAP, Fabiogomesdelimalho,Beria, Elcio9708, BOTarate, Ruy
Pugliesi, Pietro Roveri, !Silent, Vitor Mazuco, Luckas-bot,
LinkFA-Bot, Andressamistica, Alysson-Milanez, MystBot, Nallimbot,
CasperBraske, Salebot, XZeroBot, Xqbot, Lpton, Jlfreimam, RibotBOT,
HVL, Capito Pirata Bruxo,EmausBot, HRoestBot, rico Jnior Wouters,
Stuckkey, WikiGT, MerlIwBot, Ademar Brasil, DARIO SEVERI,
FabioEduardoMoreira,Prima.philosophia, Legobot, Peralta2305 e
Annimo: 97
7.2 Imagens Ficheiro:NoFonti.svg Fonte:
http://upload.wikimedia.org/wikipedia/commons/b/b5/NoFonti.svg
Licena: CC BY-SA 2.5 Contribuido-
res: Image:Emblem-important.svg Artista original: RaminusFalcon
Ficheiro:Tower_of_Hanoi.jpeg Fonte:
http://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg
Licena: CC-BY-
SA-3.0 Contribuidores: ? Artista original: ?
Ficheiro:Tower_of_Hanoi_4.gif Fonte:
http://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif
Licena: CC
BY-SA 2.5 Contribuidores: Obra do prprio Artista original: Andr
Karwath aka Aka
7.3 Licena Creative Commons Attribution-Share Alike 3.0
Origens Solues JAVA C Implementao do Algortimo Iterativo
Implementao do Algortimo Recursivo
Aplicao Concluso RefernciasLigaes externas Fontes,
contribuidores e licenas de texto e imagemTextoImagensLicena
