Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar uma solução para a o problema conhecido como Torre de Hanoi?

0 votos
296 visitas
perguntada Mar 20, 2016 em Programação Computacional por danielcajueiro (5,711 pontos)  
Compartilhe

2 Respostas

0 votos
respondida Mar 20, 2016 por danielcajueiro (5,711 pontos)  

Um implementação simples em python é

i=0;

def move_disk(begin,end):
    global i
    i=i+1
    print( i,":",begin,"-->",end)

def move_tower(n,begin,end,aux):
    #print "n:",n,"begin:",begin,"end:",end,"aux:",aux
    if(n==1):
        move_disk(begin,end);
    else:
        move_tower(n-1,begin,aux,end)
        move_disk(begin,end)
        move_tower(n-1,aux,end,begin)    


if __name__ == '__main__':

    n=4;
    move_tower(n,'A','B','C')
0 votos
respondida Abr 7, 2016 por danielcajueiro (5,711 pontos)  

Essas implementações em R foram feitas por um estudante (se não me engano foi o Carlos Cinelli em uma versão preliminar do curso de Métodos Computacionais em Economia da UNB) em R:

simula_hanui <- function(n){

  #### funções de índice para mover peças ####
  # encontra a primeira linha que é diferente de zero para retirar o disco
  imin <- function(m, c) min(row(m[,c,drop=F])[m[,c,drop=F]!=0])

  # encontra a última linha igual a zero para colocar o disco retirado
  imax <- function(m, c) max(row(m[,c,drop=F])[m[,c,drop=F]==0])

  #### função para mover o disco ####
  moverDisco <- function(origem, alvo){
    matriz[imax(matriz, alvo),alvo] <<- matriz[imin(matriz, origem), origem]
    matriz[imin(matriz, origem), origem] <<- 0
    matriz
  }

  #### função recursiva de mover a pilha ####
  moverPilha <- function(n, origem, alvo, aux){

    if(n==1){
      moverDisco(origem, alvo)
    }else{
      # move pilha com discos 1 a n-1 da origem para o auxiliar
      moverPilha(n-1, origem, aux, alvo)

      # guarda a transição para conferência
      transicao[[length(transicao)+1]] <<- matriz 

      # move disco n que sobrou da origem para o alvo
      moverDisco(origem, alvo)

      # guarda a transição para conferência
      transicao[[length(transicao)+1]] <<- matriz 

      # move pilha de 1 a n-1 do auxiliar para o alvo, em cima do n
      moverPilha(n-1, aux, alvo, origem)
    }
  }

  #### gera a matriz inicial ####
  matriz <- matrix(0, nrow=n, ncol=3)
  colnames(matriz) <- c("A","B","C")
  matriz[,1] <- 1:n


  #### cria o vetor para guardar transições ####
  transicao <- list()
  transicao[[1]] <- matriz 

  #### chama a função moverPilha ####
  moverPilha(n, "A","B","C")

  #### guarda a transição final ####
  transicao[[length(transicao)+1]] <- matriz 

  #### retorna o vetor com todos os movimentos ####
  return(transicao)
}
...