{"id":786,"date":"2015-01-01T18:45:31","date_gmt":"2015-01-01T17:45:31","guid":{"rendered":"http:\/\/www.valcon.it\/pascal\/?p=786"},"modified":"2015-07-03T11:41:54","modified_gmt":"2015-07-03T09:41:54","slug":"la-torre-di-hanoi","status":"publish","type":"post","link":"https:\/\/www.valcon.it\/pascal\/la-torre-di-hanoi\/","title":{"rendered":"La torre di Hanoi"},"content":{"rendered":"<p>Il problema<\/p>\n<blockquote><p>Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.<br \/>\nSul primo di tali perni sono infilati 64 dischi d&#8217;oro, di dimensioni decrescenti, che formano una torre.<br \/>\nSi deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore.<br \/>\nPer risolvere la questione si pu\u00f2 utilizzare il secondo perno come perno di servizio.<\/p>\n<p>Quando i monaci termineranno l&#8217;opera il mondo sar\u00e0 finito!<\/p><\/blockquote>\n<h3 id=\"hn_59ca4f8bbb_1\">Analisi<\/h3>\n<p>Siano D<sub>1<\/sub>, D<sub>2<\/sub>, &#8230;, D<sub>n<\/sub> le etichette dei dischi di una torre di Hanoi con <tt>n<\/tt> dischi.<\/p>\n<table>\n<tbody>\n<tr valign=\"top\">\n<td>1<\/td>\n<td>Il problema con un solo disco \u00e8 banale<\/p>\n<ol type=\"1\">\n<li>il disco \u00e8 sinistra<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 1\u00b0 alla 3\u00b0 torre<\/li>\n<\/ol>\n<\/td>\n<td><img decoding=\"async\" name=\"animazione1\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_11.png\"><\/p>\n<p><input type=\"button\" value=\"1\u00b0\" onClick=\"cambia1(1)\"> <input type=\"button\" value=\"2\u00b0\" onClick=\"cambia1(2)\"><script language=\"JavaScript\">var frame=1; function cambia1(f){frame=f;document.animazione1.src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_1\"+frame+\".png\"}<\/script><\/td>\n<\/tr>\n<tr valign=\"top\">\n<td>2<\/td>\n<td>Se i dischi sono 2 le mosse sono 3<\/p>\n<ol type=\"1\">\n<li>i dischi sono a sinistra<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 1\u00b0 alla 2\u00b0 torre<\/li>\n<li>sposta il disco D<sub>2<\/sub> dalla 1\u00b0 alla 3\u00b0 torre<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 2\u00b0 alla 3\u00b0 torre<\/li>\n<\/ol>\n<\/td>\n<td><img decoding=\"async\" name=\"animazione2\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_21.png\"><\/p>\n<p><input type=\"button\" value=\"1\u00b0\" onClick=\"cambia2(1)\"> <input type=\"button\" value=\"2\u00b0\" onClick=\"cambia2(2)\"> <input type=\"button\" value=\"3\u00b0\" onClick=\"cambia2(3)\"> <input type=\"button\" value=\"4\u00b0\" onClick=\"cambia2(4)\"><script language=\"JavaScript\">var frame=1;function cambia2(f){frame=f;document.animazione2.src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_2\"+frame+\".png\"}<\/script><\/td>\n<\/tr>\n<tr valign=\"top\">\n<td>3<\/td>\n<td>Se i dischi sono 3 le mosse sono 7<\/p>\n<ol type=\"1\">\n<li>i dischi sono a sinistra<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 1\u00b0 alla 3\u00b0 torre<\/li>\n<li>sposta il disco D<sub>2<\/sub> dalla 1\u00b0 alla 2\u00b0 torre<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 3\u00b0 alla 2\u00b0 torre<\/li>\n<li>sposta il disco D<sub>3<\/sub> dalla 1\u00b0 alla 3\u00b0 torre<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 2\u00b0 alla 1\u00b0 torre<\/li>\n<li>sposta il disco D<sub>2<\/sub> dalla 2\u00b0 alla 3\u00b0 torre<\/li>\n<li>sposta il disco D<sub>1<\/sub> dalla 1\u00b0 alla 3\u00b0 torre<\/li>\n<\/ol>\n<\/td>\n<td><img decoding=\"async\" name=\"animazione3\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_31.png\"><\/p>\n<p><input type=\"button\" value=\"1\u00b0\" onClick=\"cambia3(1)\"> <input type=\"button\" value=\"2\u00b0\" onClick=\"cambia3(2)\"> <input type=\"button\" value=\"3\u00b0\" onClick=\"cambia3(3)\"> <input type=\"button\" value=\"4\u00b0\" onClick=\"cambia3(4)\"> <input type=\"button\" value=\"5\u00b0\" onClick=\"cambia3(5)\"> <input type=\"button\" value=\"6\u00b0\" onClick=\"cambia3(6)\"> <input type=\"button\" value=\"7\u00b0\" onClick=\"cambia3(7)\"> <input type=\"button\" value=\"8\u00b0\" onClick=\"cambia3(8)\"><script language=\"JavaScript\">var frame=1;function cambia3(f){frame=f;document.animazione3.src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_3\"+frame+\".png\"}<\/script><\/td>\n<\/tr>\n<tr valign=\"top\">\n<td>&#8230;<\/td>\n<td>Se i dischi sono 4, 5, &#8230; si pu\u00f2 riconoscere lo schema risolutivo<\/p>\n<ol type=\"1\">\n<li>i dischi sono a sinistra<\/li>\n<li>sposta i dischi D<sub>1<\/sub>&#8230;D<sub>n-1<\/sub> dalla 1\u00b0 alla 2\u00b0 torre (usando la 3\u00b0 come appoggio) in modo da liberare D<sub>n<\/sub><\/li>\n<li>sposta il disco D<sub>n<\/sub> dalla 1\u00b0 alla 3\u00b0 torre<\/li>\n<li>sposta i dischi D<sub>1<\/sub>&#8230;D<sub>n-1<\/sub> dalla 2\u00b0 alla 3\u00b0 torre (usando la 1\u00b0 come appoggio) sopra D<sub>n<\/sub><\/li>\n<\/ol>\n<\/td>\n<td><img decoding=\"async\" name=\"animazionen\" src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_n1.png\"><\/p>\n<p><input type=\"button\" value=\"1\u00b0\" onClick=\"cambian(1)\"> <input type=\"button\" value=\"2\u00b0\" onClick=\"cambian(2)\"> <input type=\"button\" value=\"3\u00b0\" onClick=\"cambian(3)\"> <input type=\"button\" value=\"4\u00b0\" onClick=\"cambian(4)\"><script language=\"JavaScript\">var frame=1;function cambian(f){frame=f;document.animazionen.src=\"http:\/\/www.valcon.it\/pascal\/wp-content\/uploads\/hanoi_n\"+frame+\".png\"}<\/script><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3>Algoritmo<\/h3>\n<div class=\"floatr\">\n<div class=\"center\">\n<p>\u00a0Ad ogni passo \u00e8 sufficiente specificare<\/p>\n<\/div>\n<\/div>\n<ul>\n<li>il <em>numero<\/em> di dischi coinvolti, perch\u00e9 si parla sempre dei dischi in cima a una torre<\/li>\n<li>il nome della torre di <em>origine<\/em><\/li>\n<li>il nome della torre di <em>appoggio<\/em><\/li>\n<li>il nome della torre di <em>destinazione<\/em><\/li>\n<\/ul>\n<p>allora l&#8217;algoritmo risolutivo per il problema<\/p>\n<div style=\"padding-left: 30px;\"><tt>Hanoi(n, origine, appoggio, destinazione)<\/tt><\/div>\n<p>diventa<\/p>\n<ol type=\"1\">\n<li><tt>Hanoi(n-1, origine , arrivo \u00a0, appoggio \u00a0 \u00a0)<\/tt><\/li>\n<li><tt>Hanoi( \u00a01, origine , appoggio, destinazione)<\/tt><\/li>\n<li><tt>Hanoi(n-1, appoggio, origine , destinazione)<\/tt><\/li>\n<\/ol>\n<p>con l&#8217;accortezza che nel caso di torre con un solo disco \u00e8 sufficiente comunicare di spostare il disco dalla torre origine alla torre destinazione.<\/p>\n<pre class=\"\">Procedure Hanoi(n, origine, appoggio, destinazione: Byte);\r\nBegin\r\n   If(n = 1) Then\r\n      WriteLn(origine, ' - ', destinazione)\r\n   Else\r\n      Begin\r\n         Hanoi(n-1, origine , destinazione, appoggio    );\r\n         Hanoi(  1, origine , appoggio    , destinazione);\r\n         Hanoi(n-1, appoggio, origine     , destinazione);\r\n      End;\r\nEnd;\r\n\r\nVar num: Byte:\r\nBegin\r\n    Write('Numero dischi? ');\r\n    Readln(num);\r\n    Hanoi(num, 1, 2, 3);\r\n    Readln;\r\nEnd.<\/pre>\n<hr\/>\n<p>Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell&#8217;algoritmo \u00e8 proporzionale al numero di spostamenti di dischi<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>T(1) = 1<br \/>\nT(2) = T(1)+T(1)+T(1) = 1+1+1 = 3<br \/>\nT(3) = T(2)+T(1)+T(2) = 3+1+3 = 7<br \/>\nT(4) = T(3)+T(1)+T(3) = 7+1+7 = 15<br \/>\n...<br \/>\nT(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1<\/tt><\/div>\n<div class=\"indent\" style=\"padding-left: 30px;\">&#8230;<\/div>\n<p>Numericamente si tratta della successione<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>1, 3, 7, 15, 31, 63, 127, ...<\/tt><\/div>\n<p>cio\u00e8<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>2<sup>1<\/sup>-1, 2<sup>2<\/sup>-1, 2<sup>3<\/sup>-1, 2<sup>4<\/sup>-1, 2<sup>5<\/sup>-1, 2<sup>6<\/sup>-1, 2<sup>7<\/sup>-1, ...<\/tt><\/div>\n<p>quindi<\/p>\n<div class=\"indent\" style=\"padding-left: 30px;\"><tt>T(n) = 2<sup>n<\/sup>-1<\/tt><\/div>\n<p>I tempi necessari per risolvere il problema sono<\/p>\n<table class=\"data\">\n<tbody>\n<tr align=\"center\">\n<td><strong><em>n<\/em><\/strong><\/td>\n<td><em>T(n) = <strong>2<sup>n<\/sup>-1<\/strong><\/em><\/td>\n<td><em><strong>1 Hz<\/strong>\u00a0<\/em><em>(uomo)<\/em><\/td>\n<td><em><strong>1 GHz<\/strong>\u00a0<\/em><em>(PC)<\/em><\/td>\n<\/tr>\n<tr align=\"right\">\n<td>1<\/td>\n<td>2<sup>1<\/sup>-1 = 1<\/td>\n<td>un secondo<\/td>\n<td>10<sup>-9<\/sup> s<\/td>\n<\/tr>\n<tr align=\"right\">\n<td>2<\/td>\n<td>2<sup>2<\/sup>-1 = 3<\/td>\n<td>3 secondi<\/td>\n<td>3*10<sup>-9<\/sup> s<\/td>\n<\/tr>\n<tr align=\"right\">\n<td>10<\/td>\n<td>2<sup>10<\/sup>-1 = 1023<\/td>\n<td>~17 minuti<\/td>\n<td>~10<sup>-6<\/sup> s<\/td>\n<\/tr>\n<tr align=\"right\">\n<td>20<\/td>\n<td>2<sup>20<\/sup>-1 = 1.048.575<\/td>\n<td>~12 giorni<\/td>\n<td>~10<sup>-3<\/sup> s<\/td>\n<\/tr>\n<tr align=\"right\">\n<td>30<\/td>\n<td>2<sup>30<\/sup>-1 = 1.073.741.823<\/td>\n<td>~34 anni<\/td>\n<td>~1 s<\/td>\n<\/tr>\n<tr align=\"right\">\n<td>64<\/td>\n<td>2<sup>64<\/sup>-1 = 18.446.744.073.709.551.615<\/td>\n<td>~5*10<sup>11<\/sup> anni<\/td>\n<td>~500 anni<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3 id=\"hn_59ca4f8bbb_1\">Conclusioni<\/h3>\n<ul>\n<li>L&#8217;<strong>algoritmo<\/strong> per il problema della torre di Hanoi ha complessit\u00e0 in tempo asintotica esponenziale, <strong>O(2<sup>n<\/sup>)<\/strong><\/li>\n<li>Non pu\u00f2 esistere un algoritmo con complessit\u00e0 minore<\/li>\n<li>Il <strong>problema<\/strong> della torre di Hanoi \u00e8 un problema <em>intrinsecamente esponenziale<\/em><\/li>\n<li>Il <strong>problema<\/strong> della torre di Hanoi \u00e8 un problema <em>intrattabile<\/em>!<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Il problema Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti. Sul primo di tali perni sono infilati 64 dischi d&#8217;oro, di dimensioni decrescenti, che formano una torre. Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco &#8230; <a title=\"La torre di Hanoi\" class=\"read-more\" href=\"https:\/\/www.valcon.it\/pascal\/la-torre-di-hanoi\/\" aria-label=\"Leggi di pi\u00f9 su La torre di Hanoi\">Leggi tutto<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/786"}],"collection":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/comments?post=786"}],"version-history":[{"count":17,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/786\/revisions"}],"predecessor-version":[{"id":5647,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/posts\/786\/revisions\/5647"}],"wp:attachment":[{"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/media?parent=786"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/categories?post=786"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.valcon.it\/pascal\/wp-json\/wp\/v2\/tags?post=786"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}