olá pessoal estamos de volta concurso de estrutura de dados e algoritmos com jada essa é a hora de correção de exercícios sob pilhas e hoje nós vamos corrigir o exercício número 8 que é o desafio da torre de hanói o exercício número 8 pede para utilizar uma pilha e desenvolver um algoritmo que resolva o quebra-cabeça torre de hanói a torre de hanói é um problema matemático e pra gente conseguir resolver esse problema com o mínimo de movimentos possíveis nós podemos utilizar uma pilha para resolver esse pequeno probleminha se você não conhece que a torre de
hanói então torre de hanói você pode vir aqui é claro no lugo e fazer uma pesquisa uma pequena pesquisa se a gente for ver aqui nas imagens o problema da torre de hanói é o que você tem vários discos os discos tente diferentes tamanhos e note que aqui tem um disco maior ou menor menor e menor até chegar no menor zinho esses discos estão numa espécie aqui de uma pilha né esses discos estão empilhados e nós temos outras duas pilhas aqui outros dois pauzinhos que vão auxiliar a gente resolver o problema qual que é o
objetivo desse problema aqui é passar toda essa pilha de discos pra um outro pauzinho só que tem uma regra somente você não pode em pilhar um disco maior em cima de um disco menor o disco menor center tem que estar por cima se você quiser testar isso aqui por exemplo tem esse quando você coloca torre de hanói tem esse link aqui que você pode brincar então por exemplo aqui tem três disquinhos você pode escolher quantos discos você quiser até o número 8 ele também fala o mínimo de movimentos então por exemplo para resolver esses três
discos aqui como fazer vou pegar esse passar pra cá vou pegar esse passar pra cá como eu quero pegar esse aqui passar a torre 2 agora eu vou pegar um e passa pra cá agora sim eu posso pegar passar o maior para a torre 2 eu quero pegar esse disco rosa colocar em cima de si diz roxo só não posso potter é esse aqui passa pra cá esse aqui agora assim passo pra cá e esse aqui eu faço pra cá e eu tenho o problema resolvido se vocês tentarem resolver esses exercícios vocês vão ver que
existe um comportamento da gente passa esse aqui pra torre 2 e se equipar torre 3 depois passa de carro para indicar pra lá de lá pra cá etc então existe um comportamento na hora de fazer a movimentação dos discos que é o que nós vamos utilizar para resolver o nosso problema aqui tava criar a classe exercício 08 com o público e estética e void bem e vou criar que também olha pra poder ajudar a gente eu vou criar vou utilizar stec tá nos outros exercícios e outros recipientes utilizando stec agora então do pacote java o
chan que como a gente vai tratar os discos 123 60 então vai ser uma stec de inteiros filha não está aqui aqui nós estamos utilizando três filhas tá então vou chamar uma pilha de original ou chamar a outra pilha de destino e vou chamar a outra filha de auxiliar que uma pilha aa gente utiliza de auxiliar só pra ajudar na movimentação dos discos na pilha original eu vou empilhar então não é verdade bush né eu vou ampliar o número 3 vão ampliar o número 2 e vão ampliar o número 1 afinal número 3 quem está
por baixo da pilha já que 32 e um fica por cima e aí sim a gente vai resolver o nosso exercício gozar que então um público em estética e voith vou passar as três filhas primeiro preciso dizer que o exercício quantos discos eu tô trabalhando então vou chamar de n e aí sim é uma stec inter que é a original a steck auxiliar que botar aqui aí eu quebro aqui pra ficar melhor pra gente ver a eztec destino e eztec auxiliar e aí sim eu consigo resolver o meu problema que não tem essa vírgula vamos
começar então a resolver que a gente vai fazer o enem e ele tem que ser maior quiseram primeiro né esse é o ritmo ele é um algoritmo recursivo ou seja ele vai chamar ele mesmo se você não sabe que é recursividade deu uma olhada se eu não me engano é na aula 35 do curso de java básico lá você vai aprender exatamente o que queria recursividade basicamente em algoritmos recursivos a gente precisa de um ponto de parada o nosso ponto de parada é o enem vai ser menor quiser então enquanto ele for maior quiser o
algoritmo vai continuar sendo executado e para ser o bonitinho recursivo ele precisa chamar ele mesmo então torre de roni aqui também só que quando a gente movimento primeiro disquinho a gente vai sempre chamar aqui com ele - 1 vai passar original só que o destino aqui vai ser a torre auxiliar e ator e auxiliar vai ser o destino o que é que isso vai fazer aqui você tá vendo aqui tal tô a torre a torre original a torre destina ea torre auxiliar quando eu faço daqui o meu n passa cn - um então eu tenho
apenas 22 de que disquinhos na minha na minha filha é essa filha aqui na verdade está sendo como a pilha auxiliar e depois eu mudo para a pilha de da ap auxiliar passa a ser a pilha de textinho quando faço isso aqui novamente eu faço isso aqui é essa e auxiliar aqui quando eu vou fazer essa movimentação que foi a chamada que a gente fez até agora vai passar essa é a pior ciliar vai passar a ser a pilha de destino então auxiliar se torna o destino e aí sim a gente vai fazer a movimentação
que é o que a pilha de destino eu vou fazer o coxim dela aqui da pele original ou seja o original ponto pop já que o está chegando passando um disquinho pra outra pilha e aí você quiser pode fazer algumas alguns ao tipo jeans por exemplo aqui vou fazer só 1-1 aqui você pode pegar o sis out a pilha original e aqui a gente tem original pois a gente tem a pilha de destino ea pilha auxiliar o destino depois disso nós vamos chamar logo o algoritmo novamente só que novamente passando o enem - um só
que dessa vez o que vai ser o original vai ser a pilha auxiliar o que vai ser o destino continua sendo o destino eo que era auxiliar passa ser a original o que exatamente a gente está fazendo aqui nesse algoritmo a torre 1 é a torre original a torre 2 é a torre de destino ea torre 3 é a torre auxiliar quando eu faço isso daqui olha eu estou transformando a pilha nessa primeira chamada kim cadeia nessa primeira chamada aqui eu tô transformando a pilha de destino empilha auxiliar que é exatamente isso daqui olha eu
vim aqui de novo transformei a torre de destino em torre auxiliar para eu poder fazer essa jogada aqui exatamente na segunda vez que eu faço a minha jogada é essa torre aqui que auxilie a ela passa a ser torre original por que que eu vou fazer aqui eu vou atrás vou pegar minha torre de original que na verdade agora é a torre auxiliar vou jogar na torre de destino vou usar original como auxiliar e aí sim eu consigo fazer a jogada e resolver o problema vamos ver como é que se comporta que esse algoritmo então
olha o stec nem aqui eu vou chamar a vou chamar a de torre de hanói o eniac vai ser quantidade de discos que eu tenho então vou pegar o tamanho da minha filha original de china auxiliar vou executar e tá aqui todas as jogadas eu posso fazer aqui também olha com quatro e aí você pode ver exatamente como é que fica o algoritmo com quatro discos em enfim com quantos discos foi necessários e você pode usar esse passo a passo aqui para brincar lá no joguinho do browser e tentar resolver o problema esse é um
problema que lhe dão um pouquinho de nós na cabeça quando a gente vai resolver justamente porque ele utiliza um algoritmo recursivo e vocês vão ver que em estruturas de dados e algoritmos de java principalmente algoritmos de ordenação a gente utiliza bastante recursividade algoritmos de árvores a gente utiliza muita recursividade então essa pode ser uma forma muito legal a gente introduzir a recurso idade no nosso curso com essa a gente finaliza a lista de exercícios sobre pilhas e na próxima aula a gente inicia o nosso módulo sobre filas e é isso pessoal espero que estão curtindo
mais uma correção de exercícios vão ficar esperando pelo feedback de vocês e por favor não esqueça de dar um jovem aqui no youtube para poder estar com a divulgação do curso até a próxima