{"id":297,"date":"2022-03-05T23:09:36","date_gmt":"2022-03-05T23:09:36","guid":{"rendered":"https:\/\/2022.robocupjunior.eu\/rcj\/?page_id=297"},"modified":"2022-06-22T21:08:07","modified_gmt":"2022-06-22T21:08:07","slug":"torre-de-hanoi","status":"publish","type":"page","link":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/oficinas\/eletronica-e-algoritmos\/torre-de-hanoi\/","title":{"rendered":"Torre de Hanoi"},"content":{"rendered":"\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-28f84493 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:80%\"><figure class=\"wp-block-post-featured-image\"><img loading=\"lazy\" decoding=\"async\" width=\"1500\" height=\"1222\" src=\"https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/HanoiTower.png\" class=\"attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" style=\"object-fit:cover;\" srcset=\"https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/HanoiTower.png 1500w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/HanoiTower-300x244.png 300w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/HanoiTower-1024x834.png 1024w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/HanoiTower-768x626.png 768w\" sizes=\"auto, (max-width: 1500px) 100vw, 1500px\" \/><\/figure><\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px;flex-basis:20%\">\n<!-- START Kaya QR Code Generator --><div class=\"wpkqcg_qrcode_wrapper\"><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_3269d6e6886108a14_ecclevel\" value=\"L\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_3269d6e6886108a14_size\" value=\"\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_3269d6e6886108a14_color\" value=\"\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_3269d6e6886108a14_bgcolor\" value=\"\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_3269d6e6886108a14_content\" value=\"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/297\" \/><img decoding=\"async\" src=\"\" id=\"wpkqcg_qrcode_outputimg_3269d6e6886108a14\" alt=\"QR Code\" class=\"wpkqcg_qrcode\" style=\"width: auto; height: auto; max-width: 100%;\" ><div style=\"clear: none;\"><\/div><\/div><!-- END Kaya QR Code Generator -->\n<\/div>\n<\/div>\n\n\n<h2 class=\"wp-block-post-title\">Torre de Hanoi<\/h2>\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Torre de Hanoi\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/JbtsD7rkhjI?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>A Torre de Han\u00f3i (tamb\u00e9m conhecida como O Problema do Templo de Benares, Torre de Brahma, Torre de Lucas, ou simplesmente quebra-cabe\u00e7as de pir\u00e2mide) \u00e9 um jogo matem\u00e1tico composto por tr\u00eas hastes e discos de v\u00e1rios tamanhos que podem deslizar sobre qualquer haste.<\/p>\n\n\n\n<p>Um determinado n\u00famero de discos (feitos de madeira) \u00e9 colocado numa das hastes, o que determina a complexidade da solu\u00e7\u00e3o.<\/p>\n\n\n\n<p>Os discos s\u00e3o colocados numa haste em ordem decrescente de tamanho, com o menor no topo, para se aproximar de uma forma c\u00f3nica. O objetivo do quebra-cabe\u00e7as \u00e9 levar a pilha completa para outra haste, seguindo as instru\u00e7\u00f5es abaixo:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Num movimento, apenas um disco pode ser transferido.<\/li><li>Cada movimento envolve remover o disco superior de uma das pilhas e coloc\u00e1-lo em cima de outra pilha ou de uma haste vazia.<\/li><li>Um disco maior n\u00e3o pode ser colocado em cima de um menor.<\/li><\/ul>\n\n\n\n<p><strong>Componentes:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Tr\u00eas hastes<\/li><li>Conjunto de discos com tamanhos diferentes<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Princ\u00edpio-de-funcionamento:\">Princ\u00edpio de funcionamento:<\/h2>\n\n\n\n<p>A Torre de Han\u00f3i \u00e9 um excelente exemplo de um problema recursivo.<\/p>\n\n\n\n<p>Vamos ver como resolver.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 1<\/span><\/p>\n\n\n\n<p>Se tivermos apenas 1 disco, \u00e9 muito f\u00e1cil, basta mov\u00ea-lo uma vez e acabou.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 2<\/span><\/p>\n\n\n\n<p>Se tiver 2 discos, ent\u00e3o precisa de mover o de cima para a haste 2, depois o de baixo para a haste 3 e s\u00f3 ent\u00e3o mover o menor da haste 2 para a haste 3. Isso leva 3 movimentos no total.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"342\" src=\"https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/Hanoi3Steps-1024x342.png\" alt=\"\" class=\"wp-image-295\" srcset=\"https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/Hanoi3Steps-1024x342.png 1024w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/Hanoi3Steps-300x100.png 300w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/Hanoi3Steps-768x256.png 768w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/Hanoi3Steps-1536x512.png 1536w, https:\/\/2022.robocupjunior.eu\/rcj\/wp-content\/uploads\/2022\/03\/Hanoi3Steps-2048x683.png 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 3<\/span><\/p>\n\n\n\n<p>Se aplicar a mesma l\u00f3gica de antes, notar\u00e1 que para mover o disco inferior para a haste 2, primeiro precisa de mover os outros dois para a haste 3, mover o 3o disco para a haste 2 e s\u00f3 depois mover os dois discos da haste 3 para a haste 2, repetindo o processo para n= 2, o que significa que voc\u00ea teve que mover 2 pe\u00e7as duas vezes repetindo exatamente o mesmo procedimento.<\/p>\n\n\n\n<p>O quebra-cabe\u00e7a pode ser resolvido em 7 passos com 3 discos.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 4<\/span><\/p>\n\n\n\n<p>Novamente, repetindo a l\u00f3gica, para 4 pe\u00e7as, deve repetir todas as etapas necess\u00e1rias para a etapa 3 duas vezes. Isso significa que para cada disco que se adiciona, tem que dobrar todas as etapas necess\u00e1rias.<\/p>\n\n\n\n<p>O quebra-cabe\u00e7a pode ser resolvido em 15 etapas com 4 discos.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">Para n discos:<\/span><\/p>\n\n\n\n<p>2<sup>n<\/sup>-1 \u00e9 o menor n\u00famero de movimentos necess\u00e1rios para resolver um quebra-cabe\u00e7a da Torre de Han\u00f3i, sendo n o n\u00famero total de discos.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Instru\u00e7\u00f5es:\">Instru\u00e7\u00f5es:<\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Comece com 5 discos na haste 1 colocados corretamente do maior para o menor, de modo que o maior fique na parte inferior e o menor no topo.<\/li><li>Mova uma pe\u00e7a de cada vez para outra haste, certificando-se de nunca colocar um disco maior em cima de um menor.<\/li><li>Mova todos os discos da haste 1 para a haste 2.<\/li><li>Quantos movimentos fez?<\/li><li>Qual \u00e9 o n\u00famero m\u00ednimo de movimentos necess\u00e1rios para resolver o quebra-cabe\u00e7a com 5 discos?<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">Links:<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.geogebra.org\/m\/NqyWJVra\">Torre de Hanoi<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Tower_of_Hanoi#Applications\">Tower of Hanoi<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/en.khanacademy.org\/computing\/computer-science\/algorithms\/towers-of-hanoi\/a\/towers-of-hanoi\">Towers of Hanoi (article) | Algorithms | Khan Academy<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/www.youtube.com\/watch?v=lilBGvaOSy8\">Entendiendo la recursividad con las Torres de Hanoi<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/www.somatematica.com.br\/jogos\/hanoi\/\">Torre de Han\u00f3i<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>A Torre de Han\u00f3i (tamb\u00e9m conhecida como O Problema do Templo de Benares, Torre de Brahma, Torre de Lucas, ou simplesmente quebra-cabe\u00e7as de pir\u00e2mide) \u00e9 um jogo matem\u00e1tico composto por tr\u00eas hastes e discos de v\u00e1rios tamanhos que podem deslizar sobre qualquer haste. Um determinado n\u00famero de discos (feitos de madeira) \u00e9 colocado numa das [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":294,"parent":245,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-297","page","type-page","status-publish","has-post-thumbnail","hentry"],"_links":{"self":[{"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/297","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/comments?post=297"}],"version-history":[{"count":6,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/297\/revisions"}],"predecessor-version":[{"id":1010,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/297\/revisions\/1010"}],"up":[{"embeddable":true,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/245"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/media\/294"}],"wp:attachment":[{"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/media?parent=297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}