汉诺塔是神马东西？ 什么叫汉诺塔问题？
\u6c49\u8bfa\u5854\u662f\u4ec0\u4e48?\u6709A\u3001B\u3001C\u4e09\u6839\u67f1\u5b50\uff0c\u5728A\u67f1\u5b50\u4e0a\u6709m\u4e2a\u5927\u5c0f\u4e0d\u7b49\u7684\u76d8\u5b50\uff0c\u4e14A\u67f1\u5b50\u4e0b\u9762\u7684\u76d8\u5b50\u6bd4\u4e0a\u9762\u7684\u76d8\u5b50\u5927\u3002\u501f\u52a9B\u67f1\u5b50\uff0c\u5c06A\u67f1\u5b50\u4e0a\u7684\u76d8\u5b50\u79fb\u52a8\u5230C\u67f1\u5b50\u4e0a\uff0c\u79fb\u52a8\u540eC\u67f1\u5b50\u4e0a\u7684\u76d8\u5b50\u4ece\u4e0a\u5230\u4e0b\u4f9d\u6b21\u589e\u5927\uff1b\u5728\u79fb\u52a8\u4e2d\uff0c\u4e0a\u9762\u7684\u76d8\u5b50\u5fc5\u987b\u6bd4\u4e0b\u9762\u7684\u76d8\u5b50\u5c0f\u3002
\u6c49\u8bfa\u5854\uff08\u53c8\u79f0\u6cb3\u5185\u5854\uff09\u95ee\u9898\u662f\u5370\u5ea6\u7684\u4e00\u4e2a\u53e4\u8001\u7684\u4f20\u8bf4\u3002\u5f00\u5929\u8f9f\u5730\u7684\u795e\u52c3\u62c9\u739b\u5728\u4e00\u4e2a\u5e99\u91cc\u7559\u4e0b\u4e86\u4e09\u6839\u91d1\u521a\u77f3\u7684\u68d2\uff0c\u7b2c\u4e00\u6839\u4e0a\u9762\u5957\u774064\u4e2a\u5706\u7684\u91d1\u7247\uff0c\u6700\u5927\u7684\u4e00\u4e2a\u5728\u5e95\u4e0b\uff0c\u5176\u4f59\u4e00\u4e2a\u6bd4\u4e00\u4e2a\u5c0f\uff0c\u4f9d\u6b21\u53e0\u4e0a\u53bb\uff0c\u5e99\u91cc\u7684\u4f17\u50e7\u4e0d\u5026\u5730\u628a\u5b83\u4eec\u4e00\u4e2a\u4e2a\u5730\u4ece\u8fd9\u6839\u68d2\u642c\u5230\u53e6\u4e00\u6839\u68d2\u4e0a\uff0c\u89c4\u5b9a\u53ef\u5229\u7528\u4e2d\u95f4\u7684\u4e00\u6839\u68d2\u4f5c\u4e3a\u5e2e\u52a9\uff0c\u4f46\u6bcf\u6b21\u53ea\u80fd\u642c\u4e00\u4e2a\uff0c\u800c\u4e14\u5927\u7684\u4e0d\u80fd\u653e\u5728\u5c0f\u7684\u4e0a\u9762\u3002\u89e3\u7b54\u7ed3\u679c\u8bf7\u81ea\u5df1\u8fd0\u884c\u8ba1\u7b97\uff0c\u7a0b\u5e8f\u89c1\u5c3e\u90e8\u3002\u9762\u5bf9\u5e9e\u5927\u7684\u6570\u5b57(\u79fb\u52a8\u5706\u7247\u7684\u6b21\u6570)18446744073709551615\uff0c\u770b\u6765\uff0c\u4f17\u50e7\u4eec\u8017\u5c3d\u6bd5\u751f\u7cbe\u529b\u4e5f\u4e0d\u53ef\u80fd\u5b8c\u6210\u91d1\u7247\u7684\u79fb\u52a8\u3002
\u540e\u6765\uff0c\u8fd9\u4e2a\u4f20\u8bf4\u5c31\u6f14\u53d8\u4e3a\u6c49\u8bfa\u5854\u6e38\u620f:
1.\u6709\u4e09\u6839\u6746\u5b50A,B,C\u3002A\u6746\u4e0a\u6709\u82e5\u5e72\u789f\u5b50
2.\u6bcf\u6b21\u79fb\u52a8\u4e00\u5757\u789f\u5b50,\u5c0f\u7684\u53ea\u80fd\u53e0\u5728\u5927\u7684\u4e0a\u9762
3.\u628a\u6240\u6709\u789f\u5b50\u4eceA\u6746\u5168\u90e8\u79fb\u5230C\u6746\u4e0a
\u7ecf\u8fc7\u7814\u7a76\u53d1\u73b0\uff0c\u6c49\u8bfa\u5854\u7684\u7834\u89e3\u5f88\u7b80\u5355\uff0c\u5c31\u662f\u6309\u7167\u79fb\u52a8\u89c4\u5219\u5411\u4e00\u4e2a\u65b9\u5411\u79fb\u52a8\u91d1\u7247\uff1a
\u59823\u9636\u6c49\u8bfa\u5854\u7684\u79fb\u52a8\uff1aA\u2192C,A\u2192B,C\u2192B,A\u2192C,B\u2192A,B\u2192C,A\u2192C
\u6b64\u5916\uff0c\u6c49\u8bfa\u5854\u95ee\u9898\u4e5f\u662f\u7a0b\u5e8f\u8bbe\u8ba1\u4e2d\u7684\u7ecf\u5178\u9012\u5f52\u95ee\u9898\u3002
来源
汉诺塔是源自印度神话里的玩具。 上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。 上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
传说
在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下， 18446744073709551615/31556952=584554049253.855年 这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。 和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人——宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。 那么，宰相要求得到的麦粒到底有多少呢？总数为 1+2+2^2 + … +2^63 =2^64-1 和移完汉诺塔的次数一样。我们已经知道这个数字有多么大了。 人们估计，全世界两千年也难以生产这么多麦子！
预言
有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。
编辑本段汉诺塔与宇宙寿命
如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，宇宙被毁灭是什么时候呢？ 让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次......这实在是太累了 因此让我们逻辑性的思考一下吧。 4个的时候能够移动最大的4盘时如图所示。 到此为止用了7次。 接下来如下图时用1次，在上面再放上3个圆盘时还要用7次（把3个圆盘重新放在一起需要的次数）。 因此，4个的时候是 “3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数” =2x“3个圆盘重新摞在一起的次数”+1次 =15次。 那么，n个的时候是 2x“（n-1）个圆盘重新摞在一起的次数”+1次。 由于1 个的时候是1次，结果n个的时候为（2的n次方减1）次。 1个圆盘的时候 2的1次方减1 2个圆盘的时候 2的2次方减1 3个圆盘的时候 2的3次方减1 4个圆盘的时候 2的4次方减1 5个圆盘的时候 2的5次方减1 ........ n个圆盘的时候 2的n次方减1 也就是说，n=64的时候是（2的64次方减1）次。 因此，如果移动一个圆盘需要1秒的话， 宇宙的寿命=2的64次方减1（秒） 2的64次方减1到底有多大呢？动动计算器，答案是一个二十位的数字： 18446744073709551615 用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。 据说，现在的宇宙年龄大约是150亿年，还差得远呢。 汉诺塔问题在数学界有很高的研究价值， 而且至今还在被一些数学家们所研究， 也是我们所喜欢玩的一种益智游戏， 它可以帮助开发智力，激发我们的思维。
编辑本段concreteHAM：
现在有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n)。 首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式： H(1) = 1 H(n) = 2*H(n-1)+1 (n>1) 那么我们很快就能得到H(n)的一般式： H(n) = 2^n - 1 (n>0) 并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。 进一步加深问题(解法原创*_*)： 假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：(1)假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n)；(2)只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n)。 (1)中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是： J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2
在分析(2)之前
，我们来说明一个现象，假如A柱子上有两个大小相同的盘子，上面一个是黑色的，下面一个是白色的，我们把两个盘子移动到B上，需要两次，盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次，盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒。 现在回到最开始的问题，n个盘子移动，上方的n-1个盘子总移动次数为2*H(n-1)，所以上方n-1个盘子的移动次数必定为偶数次，最后一个盘子移动次数为1次。
讨论问题(2)，
综上两点，可以得出，要把A上2n个盘子移动到B上，首先可以得出上方的2n-2个盘子必定移动偶数次，所以顺序不变，移动次数为： J(n-1) = 2^n-2 然后再移动倒数第二个盘子，移动次数为2*J(n-1)+1 = 2^(n+1)-3， 最后移动最底下一个盘子，所以总的移动次数为： K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5 开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍：
绛旓細姹夎濉闂瀹為檯涓婂氨鏄灏嗘煴瀛怉涓婄敱灏忓埌澶ф帓鍒楃殑鍦嗙幆鎸夌収鐩稿悓鐨勫ぇ灏忛『搴忕Щ鍔ㄥ埌鏌卞瓙C锛屼箣闂寸殑杩囩▼鍙互浣跨敤鏌卞瓙B銆傚叾閫掑綊鐨勫綊绾虫濇兂鏄繖鏍风殑锛氾紙1锛夐鍏堬紝褰撳彧鏈変竴涓洏瀛愮殑鏃跺欏彧闇瑕佸皢A涓婄殑1鍙风洏瀛愮Щ鍔ㄥ埌C涓婂氨琛屼簡 锛2锛夊綋鏈2涓洏瀛愬湪A涓婄殑鏃跺欙紝闇瑕佸皢A涓婄殑1鍙风洏瀛愶紙鐢变笂寰涓嬫暟锛夌Щ鍔ㄥ埌B涓婏紝鍐...
绛旓細姹夎濉瑙勫緥鎬荤粨鍙ｈ瘈鏄崟宸﹀弻鍙筹紝鍏堝皬鍚庡ぇ锛屼竴姝ヤ袱姝ワ紝寰幆寰澶嶃傝3涓煴瀛愬垎鍒槸鐢诧紝涔欙紝涓欙紝鎶3鏍规煴瀛愮湅鎴愪竴涓惊鐜紝涔熷氨鏄锛岀敳鐨勫彸杈规槸涔欙紝涔欑殑鍙宠竟鏄笝锛岃屼笝鐨勫彸杈瑰垯鍥炲埌鐢诧紝鍚岀悊锛岀敳鐨勫乏杈瑰氨鏄笝銆傜畝鍗曠偣锛岃浣忎笝鐨勫彸杈规槸鐢诧紝鍜岀敳鐨勫乏杈规槸涓欏氨琛屼簡銆傜洏瀛愬垎鍒槸鐩1锛岀洏2锛岀洏3锛岀洏4...
绛旓細娓告垙瑙勫垯:1銆佹瘡娆″彧鑳界敱涓涓汉绉诲姩鐩樺瓙锛屼笖姣忔鍙厑璁哥Щ鍔ㄤ竴涓洏瀛愮殑浣嶇疆锛2銆佹瘡涓洟闃熺殑鎵鏈夋垚鍛樺繀椤讳緷娆＄Щ鍔ㄧ洏瀛愶紱3銆佸湪浠绘剰涓娆＄Щ鍔ㄤ腑锛岃緝灏忕殑鐩樺瓙涓嶅彲浠ヨ鏀惧湪杈冨ぇ鐨勭洏瀛愪笅闈紱4銆佹寮忓紑濮嬩互鍚庯紝闄ょЩ鍔ㄧ洏瀛愮殑闃熷憳澶栵紝鍏朵粬闃熷憳蹇呴』绔欏湪鍩硅甯堣瀹氱殑璺濈浠ュ锛5銆佹寮忓紑濮嬩互鍚庡洟闃熸墍鏈夋垚鍛樹笉寰楄璇濓紝浜...
绛旓細姹夎濉旀槸涓涓凯浠ｉ棶棰橈紝鎴戜滑鍏堝亣璁緓灞傛眽璇哄浠庣涓鏍规煴瀛愮Щ鍔ㄥ埌鏈鍚庝竴鏍规煴瀛愶紙鐩爣鏌卞瓙锛夌殑鏈蹇鏁版槸f(x)娆 鏄剧劧f(1)=1 f(2)=3 鐒跺悗鐪3灞傜殑锛屾垜浠彲浠ユ妸鏁翠釜杩囩▼鍒嗚В涓轰笁涓儴鍒 涓锛屾妸绗竴绗簩灞傜Щ鍔ㄥ埌涓棿鐨勬煴瀛愶紙杩囨浮鏌卞瓙锛夛紝鏈蹇玣(2)姝 浜岋紝鎶婄涓夊眰绉诲姩鍒版渶鍚庝竴鏍规煴瀛愶紙鐩爣鏌卞瓙锛夛紝鏈...
绛旓細1銆佸皢濉擜涓婄殑n-1涓瀛愬熷姪濉擟鍏堢Щ鍒板B涓娿2銆佹妸濉擜涓婂墿涓嬬殑涓涓瀛愮Щ鍒板C涓娿3銆佸皢n-1涓瀛愪粠濉擝鍊熷姪濉擜绉诲埌濉擟涓娿姹夎濉鐜╂硶濡備笅锛氭父鎴忛噷鏈変笁鏍规煴瀛愶紝宸﹁竟鐨勬煴瀛愪笂浠庝笅寰涓婃寜鐓уぇ灏忛『搴忔憺鐫N鐗囧渾鐩樸傜帺瀹堕渶瑕佸仛鐨勬槸鎶婂渾鐩樹粠涓嬮潰寮濮嬫寜浠庡ぇ椤哄簭閲嶆柊鎽嗘斁鍦ㄥ彸杈圭殑鏌卞瓙涓娿傚苟涓旇瀹氾紝...
绛旓細姹夎濉5灞31姝ュ彛璇锛1.灏嗘渶宸﹁竟鐨勫渾鏌辩殑绗竴涓洏鏀惧埌鏈鍙宠竟鐨勫渾鏌变笂銆2.灏嗘渶宸﹁竟鐨勫渾鏌辩殑绗簩涓洏鏀惧埌涓棿鐨勫渾鏌变笂銆3.鍐嶅皢鏈鍙宠竟鐨勫渾鐩樻斁鍒颁腑闂寸殑鍦嗘煴涓娿4.灏嗘渶宸﹁竟鐨勭涓涓洏鏀惧埌鏈鍙宠竟鐨勫渾鏌变笂銆5.鎵惧埌涓変釜鍦嗙洏鐨勭Щ鍔ㄨ寰嬶紝鎶婂乏闈㈠渾鏌辩殑绗竴涓洏鏀惧埌涓棿锛屽氨鍙互绉诲姩绗簲涓洏銆6.鍐嶅皢鏈...
绛旓細鍗曞乏鍙屽彸锛屽厛灏忓悗澶э紝涓姝ヤ袱姝ワ紝寰幆寰澶嶃傝3涓煴瀛愬垎鍒槸鐢诧紝涔欙紝涓欙紝鎶3鏍规煴瀛愮湅鎴愪竴涓惊鐜紝涔熷氨鏄锛岀敳鐨勫彸杈规槸涔欙紝涔欑殑鍙宠竟鏄笝锛岃屼笝鐨勫彸杈瑰垯鍥炲埌鐢诧紝鍚岀悊锛岀敳鐨勫乏杈瑰氨鏄笝銆傜畝鍗曠偣锛岃浣忎笝鐨勫彸杈规槸鐢诧紝鍜岀敳鐨勫乏杈规槸涓欏氨琛屼簡銆傜洏瀛愬垎鍒槸鐩1锛岀洏2锛岀洏3锛岀洏4鈥︹︾洏1鏈灏忋傛寜鐓...
绛旓細hanot (n-1,b,a,c);锛堣В閲婏細鍦ㄦ妸B濉涓婄殑(n-1))涓熷姪A濉旂Щ鍔ㄥ埌C濉旓級涓轰簡瀹炵幇 n涓洏浠 鍊熷姪c 浠巃 绉诲姩鍒 b 鎬濊矾濡備笅锛氶鍏堣冭檻鏋侀檺褰撳彧鏈変竴涓洏鐨勬椂鍊欙紝鐩樼洿鎺ヤ粠 a -> b鍗冲彲銆傚綋鏈2涓洏鐨勬椂鍊欙紝鎶1鍙风洏浠巃 -> c 鐒跺悗 鎶2鍙风洏 a->b 鍐 鎶 2濂界洏浠 c - > b銆傚綋鏈塶涓...
绛旓細涓夐樁姹夎濉闂瑙ｉ姝ラ 鍏遍渶7姝ャ傚洓闃舵眽璇哄闂瑙ｉ姝ラ 鍏遍渶15姝 浜旈樁姹夎濉旈棶棰樿В棰樻楠 绠楁硶閲囩敤浜嗗垎娌荤殑鎬濇兂锛屽埄鐢ㄩ掑綊鐨勬柟寮忥紝瀹屾垚n灞傛眽璇哄鐨勭Щ鍔ㄣ傛眽璇哄闂鐨勯潪閫掑綊绠楁硶 姹夎濉旈棶棰樹篃鍙互鍊熷姪闈為掑綊绠楁硶鏉ヨВ鍐筹紝鏈夎澶氱闈為掑綊绠楁硶鍙互瑙ｅ喅姹夎濉旈棶棰橈紝鍗氫富璁や负鏈甯歌鐨勬槸鍒╃敤閫掑綊浜屽弶鏍戯紝涓嬮潰鍒椾妇...
绛旓細濡傛灉鏈塶涓洏鐨勮瘽锛岄偅涔堢Щ鍔ㄦ鏁颁负2鐨刵娆℃柟-1鍏蜂綋璇佹槑濡備笅瀵逛簬涓涓崟鐙殑濉锛屽彲浠ヨ繘琛屼互涓嬫搷浣滐細1锛氬皢鏈涓嬫柟鐨勫鐨勪笂鏂圭殑鎵鏈夊绉诲姩鍒拌繃娓℃煴瀛2锛氬皢搴曞绉诲姩鍒扮洰鏍囨煴瀛3锛氬皢杩囨浮鏌卞瓙涓婄殑鍏朵粬濉旂Щ鍔ㄥ埌鐩爣鏌卞瓙鍙互褰掔撼鍑虹涓姝ヤ笌绗笁姝ョ殑姝ユ暟鏄竴鏍风殑锛岃涓篴鍒欐绘鏁颁负2a+1鍙互寰楀埌鏁板垪An=2A(n-1...
