{"id":293,"date":"2022-03-05T23:08:17","date_gmt":"2022-03-05T23:08:17","guid":{"rendered":"https:\/\/2022.robocupjunior.eu\/rcj\/?page_id=293"},"modified":"2022-05-31T17:45:01","modified_gmt":"2022-05-31T17:45:01","slug":"ofi-52-tower-of-hanoi","status":"publish","type":"page","link":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/workshops\/electronics-and-algorithms\/ofi-52-tower-of-hanoi\/","title":{"rendered":"Tower of 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_5269d6e57053f0c69_ecclevel\" value=\"L\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_5269d6e57053f0c69_size\" value=\"\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_5269d6e57053f0c69_color\" value=\"\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_5269d6e57053f0c69_bgcolor\" value=\"\" \/><input type=\"hidden\" id=\"wpkqcg_qrcode_outputimg_5269d6e57053f0c69_content\" value=\"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/293\" \/><img decoding=\"async\" src=\"\" id=\"wpkqcg_qrcode_outputimg_5269d6e57053f0c69\" 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\">Tower of Hanoi<\/h2>\n\n\n<p>The Tower of Hanoi (also known as The Problem of Benares Temple, Tower of Brahma, Lucas&#8217; Tower, or simply pyramid puzzle) is a mathematical game or puzzle made up of three rods and a number of discs of various sizes that can slide onto any rod.<\/p>\n\n\n\n<p>An number of discs (made of wood) is stacked on one of the rods, which will determine the complexity of the solution;<\/p>\n\n\n\n<p>The discs are placed on one rod in decreasing size order, with the smallest at the top, to approximate a conical shape. The goal of the puzzle is to get the full stack to another rod while following the instructions below:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>At any given time, only one disc can be transferred.<\/li><li>Each move entails removing the top disc from one of the stacks and placing it on top of another stack or an empty rod.<\/li><li>A larger disc cannot be placed on top of a smaller one.<\/li><\/ul>\n\n\n\n<p><strong>Components:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Three rods<\/li><li>Set of discs with different sizes<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Working-Principle:\">Working Principle:<\/h2>\n\n\n\n<p>The Hanoi Tower is an excellent example of a Recursive problem.<\/p>\n\n\n\n<p>Let&#8217;s see how to solve it.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 1<\/span><\/p>\n\n\n\n<p>If we have just 1 disc that\u2019s very easy as you just move it once and it\u2019s over.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 2<\/span><\/p>\n\n\n\n<p>If you have 2 discs, then you need to move the top one to rod 2, then the bottom one to rod 3 and only then move the small one from rod 2 to rod 3. That takes 3 moves in total.<\/p>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"342\" data-id=\"295\" 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<\/figure>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 3<\/span><\/p>\n\n\n\n<p>If you apply the same logic as before you\u2019ll notice that for you to move the bottom disc to rod 2 you first have to move the other two to rod 3, move the 3rd disc to rod 2 and then move both the discs in rod 3 to rod 2 repeating the process for n= 2, meaning you had to move the 2 pieces twice repeating the exact same procedure.<\/p>\n\n\n\n<p>The puzzle may be solved in 7 steps with 3 discs.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">n = 4<\/span><\/p>\n\n\n\n<p>Again by repeating the logic, you\u2019ll find that for 4 pieces you have to repeat every step necessary for step 3 twice. This means that for every disc you add you have to double all the necessary steps.<\/p>\n\n\n\n<p>The puzzle may be solved in 15 steps with 4 discs.<\/p>\n\n\n\n<p><span style=\"text-decoration: underline;\">For n discs:<\/span><\/p>\n\n\n\n<p>2<sup>n<\/sup>-1 is the smallest number of moves required to solve a Tower of Hanoi puzzle, with n being the total number of discs.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Instructions:\">Instructions:<\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Start with 5 discs in rod 1 correctly placed from the largest to the smallest so that the largest is at the bottom and the smallest at the top.<\/li><li>Move one piece at a time to another rod making sure you never place a larger disc on top of a smaller one.<\/li><li>Move all discs from rod 1 to rod 2.<\/li><li>How many moves did you take?<\/li><li>What\u2019s the minimum number of moves necessary to solve the puzzle with 5 discs?<\/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>The Tower of Hanoi (also known as The Problem of Benares Temple, Tower of Brahma, Lucas&#8217; Tower, or simply pyramid puzzle) is a mathematical game or puzzle made up of three rods and a number of discs of various sizes that can slide onto any rod. An number of discs (made of wood) is stacked [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":294,"parent":243,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-293","page","type-page","status-publish","has-post-thumbnail","hentry"],"_links":{"self":[{"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/293","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=293"}],"version-history":[{"count":4,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/293\/revisions"}],"predecessor-version":[{"id":943,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/293\/revisions\/943"}],"up":[{"embeddable":true,"href":"https:\/\/2022.robocupjunior.eu\/rcj\/index.php\/wp-json\/wp\/v2\/pages\/243"}],"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=293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}