Torre de Hanoi, N pinos

Assuntos Gerais
#1

Boa tarde pessoal.

Problema Hanoi.

Todo mundo tá cansado de saber como é…

O lance é que estou com esse problema e travei.

Montar Torres onde a quantidade de pinos seja M>=3.

Estou com dificuldades de solucionar.

Alguém pra ajudar?

#2

Por favor:

a) Quando postar tópicos, não dê os títulos usando apenas letras maiúsculas;
b) Diga quais são essas dificuldades, e o que você já fez.

#3

Eu não lembro como eu fiz o cálculo, mas eu cheguei a conclusão de que são necessários no mínimo 2^N - 1 movimentos para resolver a torre de Hanoi com N pinos. Vou tentar refazer a conta e posto aqui. Uma coisa interessante que eu descobri quando pesquisei sobre o assunto é que a Torre de Hanoi é um problema do tipo NP-completo, ou seja, não pode ser resolvido em tempo polinomial.

#4

A wikipedia tem um artigo interessante sobre a Torre de Hanoi.

#5

isso NUNCA foi provado. O que se sabe é que caso exista uma solução polinomial para algum problema NP, poderia-se também resolver todos outros problemas NP em tempo polinomial.

#6

Que eu me lembre esse foi um dos trabalhos que chegou mais perto. Mas ainda está sendo verificado pela academia (desde agosto de 2010).

#7

isso NUNCA foi provado. O que se sabe é que caso exista uma solução polinomial para algum problema NP, poderia-se também resolver todos outros problemas NP em tempo polinomial.[/quote]

Hum… é mesmo, me expressei de maneira errada.

#8

O interessante é que se alguém conseguir provar que P = NP, muita coisa no curso de ciência da computação perde utilidade (falo da parte de otimização de algoritmos), já que muitas teoria se baseiam no fato de que P != NP.

#9

Quanto ao CAPS, ok!

No mais, esse é um exercício proposto no livro do Jayme Luiz Szwarcfiter, no seu capítulo 1.

Essa provas, melhores caminhos, quantidade de passos, sempre são uns problemas pra mim.

É uma disciplina obrigatória, que é um soco no estômago.

Sei como trabalhar com algortimos, e da wikipedia, valeu a dica, mas já passei dessa fase de procurar no google. =D

Não estou conseguindo fazer o pseudo código, algo do tipo, faço com 3 pinos, ou 4 tal como:

Pra m sendo pinos…

m=4

procedimento Hanoi4(n, A,B,C, D) // respectivamente origem, aux, aux, dest

se n>0 então

hanoi(n-2, A,D, B,C)
mover A->C
mover A->B
mover C->B
hanoi (n-2, D, B, A,C)

m =3
procedimento Hanoi3(n, A, B, C) ) // respectivamente origem, aux, aux, dest
se n>0
hanoi(n-1, A, C, B)
mover A->B
hanoi(n-1, C,B, A)

m sendo x… não sei

#10