Torre de Hanoi, N pinos

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.

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.

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

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.

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

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.

Hum… é mesmo, me expressei de maneira errada.

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.

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