Torre de Hanói

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Torre de Hanoi)
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes fiáveis e independentes, mas que não cobrem todo o conteúdo. Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Trechos sem fontes poderão ser removidos.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing.
Um Modelo das Torres de Hanoi

Torre de Hanói é um "quebra-cabeça" que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação. O número de discos pode variar sendo que o mais simples contém apenas três.

A Torre de Hanói tem sido tradicionalmente considerada como um procedimento para avaliação da capacidade de memória de trabalho, e principalmente de planejamento e solução de problemas.

Origens[editar | editar código-fonte]

O quebra-cabeça foi divulgado pela primeira vez no Ocidente pelo matemático francês Édouard Lucas. Ele teve inspiração de uma lenda para construir o jogo das Torres de Hanói em 1883[1] . Já seu nome foi inspirado na torre símbolo da cidade de Hanói, no Vietnã[2] .

Existem várias lendas a respeito da origem do jogo, a mais conhecida diz respeito a um templo Hindu, situado no centro do universo. Diz-se que Brahma supostamente havia criado uma torre com 64 discos de ouro e mais duas estacas equilibradas sobre uma plataforma. Brahma ordenara-lhes que movessem todos os discos de uma estaca para outra segundo as suas instruções. As regras eram simples: apenas um disco poderia ser movido por vez e nunca um disco maior deveria ficar por cima de um disco menor. Segundo a lenda, quando todos os discos fossem transferidos de uma estaca para a outra, o templo desmoronar-se-ia e o mundo desapareceria. Não é claro se Lucas inventou essa lenda ou foi inspirado por ele.

Existem muitas variações sobre esta lenda. Por exemplo, em algumas narrativas, o templo é um mosteiro e os sacerdotes são monges. O templo ou mosteiro pode estar em diferentes partes do mundo - incluindo Hanói, Vietnã, e pode ser associado a qualquer religião. Em algumas versões, são introduzidos outros elementos, tais como o facto de a torre foi criado no início do mundo, ou que os padres ou monges podem fazer apenas uma mudança por dia.

Soluções[editar | editar código-fonte]

Solução do problema com uma torre de quatro discos.

É interessante observar que o número mínimo de "movimentos" para conseguir transferir todos os discos da primeira estaca à terceira é 2n-1, sendo n o número de discos. Logo:

Para solucionar um Hanói de 4 discos, são necessários 15 movimentos

Para solucionar um Hanói de 7 discos, são necessários 127 movimentos

Para solucionar um Hanói de 15 discos, são necessários 32.767 movimentos

Para solucionar um Hanói de 64 discos, como diz a lenda, são necessários 18.446.744.073.709.551.615 movimentos.

Para mover o primeiro disco da torre original, 1 movimento é gasto. Para mover o segundo da torre original, sendo que o primeiro já foi movido e será construída uma torre com os 2 menores discos, são gastos 2 movimentos. Para deslocar o terceiro disco formando nova torre com os três menores discos, tendo a torre com os dois menores já formada, são gastos 7 movimentos.

Assim se sucede com os próximos discos até que o enésimo disco (o último) seja deslocado compondo uma torre com os outros discos tendo uma torre com o penúltimo disco e os demais juntos já formada. A sucessão formada pela soma dos movimentos é uma sucessão (1,2,4,8...2^n)

A fórmula 2^n-1 é provinda da soma de uma progressão geométrica.

Sabe-se que em uma progressão geométrica a soma de seus termos equivale a [a*(q^n-1)]/q-1, onde "a" é o primeiro termo e "q" é a razão.

Já que a razão é 2 e o primeiro termo é 1 temos que [a*(q^n-1)]/q-1 = [1*(2^n-1)]/2-1 = 2^n-1

Uma solução 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 último pino para o qual todos os Disco devem estar no final do algoritmo.

JAVA[editar | editar código-fonte]

import java.util.ArrayList;  
import java.util.Collections;  
import java.util.InputMismatchException;  
import java.util.List;  
import java.util.Scanner;  
 
class Disco implements Comparable<Disco>{  
      Integer index;  
      String movimento;  
      Disco(int index,String movimento){  
         this.index=index;  
         this.movimento=movimento;  
      }  
    public int compareTo(Disco o) {  
        return index.compareTo(o.index);  
    }
}  
public class HanoiIterativo {     
    private int qtDiscos;    
    private String sequenciaImpares[] =   {"A-->C", "C-->B", "B-->A"};//para impares   
    private String sequenciaPares  [] =   {"A-->B", "B-->C", "C-->A"};//para pares    
    private List<Disco> arrayDiscos = new ArrayList<Disco>();  
    public void lerDados() {    
        System.out.println("Digite a quantidade de  discos");    
        Scanner rc = new Scanner(System.in);    
        try{    
         qtDiscos = rc.nextInt();    
        }catch(InputMismatchException e){    
            System.out.println("Amigão! É fácil! Digite o número de discos por favor!");    
            lerDados();    
        }     
    }    
    public void hanoi() {         
            int maxP=(int) Math.pow(2, qtDiscos);  
            int y  = 1;  
            int pos =1;  
            while(y <= qtDiscos ){     
                 int ctPulos = (int) Math.pow(2, y);  
                 pos*=2;  
                 if(y==1){  
                     pos=1;  
                 }  
                 if(qtDiscos%2==0){  
                  populaArrayPares(pos,ctPulos,maxP,y);  
                 }else{  
                  populaArrayImpares(pos,ctPulos,maxP,y);  
                 }  
                 y++;  
           }  
    }  
    private void populaArrayPares(int pos,int intervalos, int maxP,int y){  
           int index = 0;  
           if(y%2==0){  
               for (int i = pos; i <= maxP; i+=intervalos) {  
                   Disco d = new Disco(i, sequenciaPares[index]);  
                   arrayDiscos.add(d);  
                   index++;  
                   if(index>2){  
                      index=0;   
                   }  
               }  
           }else{  
               for (int i = pos; i < maxP; i+=intervalos) {  
                   Disco d = new Disco(i, sequenciaImpares[index]);  
                   arrayDiscos.add(d);  
                   index++;  
                   if(index>2){  
                      index=0;   
                   }  
               }  
           }          
        }  
    private void populaArrayImpares(int pos,int intervalos, int maxP,int y){  
       int index = 0;  
       if(y%2==0){  
           for (int i = pos; i < maxP; i+=intervalos) {  
               Disco d = new Disco(i, sequenciaImpares[index]);  
                   arrayDiscos.add(d);  
                   index++;  
                   if(index>2){  
                      index=0;   
                   }  
               }                 
       }else{  
          for (int i = pos; i <= maxP; i+=intervalos) {  
               Disco d = new Disco(i, sequenciaPares[index]);  
               arrayDiscos.add(d);  
           index++;  
           if(index>2){  
              index=0;   
           }  
           }  
       }          
        }    
    public static void main(String[] args) {    
        HanoiIterativo h = new HanoiIterativo();    
        h.lerDados();    
        h.hanoi();    
        Collections.sort(h.arrayDiscos);  
        for (Disco d : h.arrayDiscos) {  
             System.out.println("execute: "+d.index+"  "+d.movimento);  
        }      
    }    
}

C[editar | editar código-fonte]

Implementação do Algorítimo Iterativo[editar | editar código-fonte]

/**
 * Resolução do problema clássico das Torres de Hanói via algorítimo iterativo.
 *
 * Exemplo de compilação e execução no Linux:
 *
 *    prompt> gcc hanoi.c -o hanoi
 *    prompt> ./hanoi QUANTIDADE_DE_DISCOS
 *
 * Nota: Imprime (2^QUANTIDADE_DE_DISCOS)-1 linhas de texto na saída padrão.
*/
 
#include <stdio.h>
#include <stdlib.h>
 
/**
 * Core da resolução com impressão da sequência ótima de movimentos.
 *
 * @param QTD_DISCOS Quantidade de discos a movimentar entre as 3 pilhas.
*/
void solve(const int QTD_DISCOS)
{
  /*
   * array dos arrays de duplas, isto é; movimentos, para acesso conforme
   * paridade (vide código) tal que o primeiro componente de cada dupla é o
   * número de uma torre origem e o segundo é o número de uma torre destino
  */
  const int ALPHA[2][3][2] = {
      { { 1, 3 }, { 3, 2 }, { 2, 1 } },   /* PARES */
      { { 1, 2 }, { 2, 3 }, { 3, 1 } }    /* ÍMPARES */
    };
 
  /* calcula o limitante do número de iterações = 2 ^ QTD_DISCOS */
  const int MAX_ITER = 1 << QTD_DISCOS;
 
  /* lista de movimentos com capacidade ótima */
  int **lista = malloc( (MAX_ITER - 1) * sizeof(*lista) );
 
  int start, gap, disco, k, rank;
 
  /*
   * loop de preenchimento "não sequencial" da lista de movimentos
  */
  for (start = 1, gap = 2, disco = 1;
       disco <= QTD_DISCOS; ++disco, start <<= 1, gap <<= 1)
  {
    /* valor ajustado do limitante */
    int R = MAX_ITER + (disco % 2);
 
    /* estabelece acesso direto a um dos arrays de duplas */
    int **duplas = (int **) &ALPHA[(QTD_DISCOS + disco) % 2];
 
    for (k = 0, rank = start; rank < R; rank += gap, ++k)
    {
      lista[rank - 1] = (int *) &duplas[k % 3];
    }
  }
 
  /* imprime a sequência ótima de movimentos que resolvem o problema */
  for (rank = 0; rank < (MAX_ITER - 1); ++rank)
  {
    char origem  = lista[rank][0] + 64;
    char destino = lista[rank][1] + 64;
    printf("%4d ) %c --> %c\n", (rank + 1), origem, destino);
  }
 
  free(lista);
}
 
/**
 * Invoca o core da resolução com o parâmetro fornecido na linha de comando.
 *
 * @param Quantidade de discos a movimentar entre as 3 pilhas.
*/
int main(int argc, char **argv)
{
  int d = atoi(argv[1]);
 
  solve(d);
 
  return 0;
}

Implementação do Algorítimo Recursivo[editar | editar código-fonte]

/**
 * Resolução do problema clássico das Torres de Saigon via algorítimo recursivo.
 *
 * Exemplo de compilação e execução no Linux:
 *
 *    prompt> gcc saigon.c -o saigon
 *    prompt> ./saigon QUANTIDADE_DE_DISCOS
 *
 * Nota: Imprime (2^QUANTIDADE_DE_DISCOS)-1 linhas de texto na saída padrão.
*/
 
#include <stdio.h>
#include <stdlib.h>
 
/**
 * Core da resolução com impressão da sequência ótima de movimentos.
 *
 * @param QTD_DISCOS Quantidade de discos a movimentar.
 * @param origem Número da torre origem.
 * @param destino Número da torre destino.
 * @param temp Número da torre temporária.
*/
void solve(int QTD_DISCOS, int origem, int destino, int temp)
{
  /** Número de ordem de cada movimento na sequência de resolução. */
  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 resolução com o parâmetro fornecido na linha de comando e
 * constantes que caracterizam o problema.
 *
 * @param Quantidade de discos a movimentar entre as 3 pilhas.
*/
int main(int argc, char **argv)
{
  int d = atoi(argv[1]);
 
  solve(d, 1, 3, 2);
 
  return 0;
}

Aplicação[editar | editar código-fonte]

A Torre de Hanói pode ser trabalhada em níveis de desenvolvimento com crianças. Na pré-escola, com regras simples de separação de cores e tamanhos, a torre de Hanói ajuda em questões de coordenação motora, identificação de formas, ordem crescente e decrescente, entre outras formas de aprendizado.

De uma maneira mais ampla, o jogo pode ser usado para o estabelecimento de estratégias de transferência das peças, como a contagem dos movimentos e raciocínio.

Iniciando com um número menor de peças, ou seja, resolvendo problemas mais simples, teremos oportunidade de experimentar uma das mais importantes formas de raciocínio matemático.

O jogo trabalha o desenvolvimento da lógica e do raciocínio matemático.É usado para desenvolver as crianças.

Conclusão[editar | editar código-fonte]

A Torre de Hanói consiste em passar todos os discos de uma extremidade a outra sem que um disco maior fique em cima de um menor.

As suas aplicações são basicamente usadas em escolas para que os professores possam melhorar e desenvolver o cognitivo das crianças, além do trabalho em grupo. Sendo este aplicado em pequenos grupos ou individualmente.

A Torre de Hanói possui várias formas de resolução. Uma delas é a resolução recursiva a qual podemos dizer que é a mais limitada quanto ao tempo de realização, já que sua execução dependerá de alguns fatores para tornar-se mais eficaz.

A resolução Iterativa utiliza alguns ciclos (estruturas) de repetição (for, whiles) que podem ser chamados de laços, existe ainda a possibilidade de algumas estruturas adicionais (mais complexas) as quais tornam o algoritmo mais rápido.

É fato que todo algoritmo recursivo possui um algoritmo interativo equivalente; Dependendo apenas da sua complexidade de construção.

Referências

  1. [1] www.realidadevirtual.com.br, acesso em 28-08-2011.
  2. Jogos de Desafio, Vol. 1. Editorial Salvat, Barcelona, 2005.

Ligações externas[editar | editar código-fonte]