关于汉诺塔问题,这里有一个传说:
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。——(来源于百度百科)
果真,只有数学家才会提出这样会让人初步抓狂的事情。
重要的事情是,这个事情还有预言,天知道,当初玛雅预言12月21日的时候,当初我紧张的要死,生怕第二天看不到隔壁家的小妹妹了。
本次的预言如果实现的话,估计是没有痛苦的:这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。
下面进入分析阶段,着急的小伙伴请直接看后面代码
很多人初步一看,这就是个预言,能有啥?可是你要看前面,这是一个数学家提出的问题,数学家一般不会讲故事,他一旦讲故事,多半会让人崩溃。比如,在没有数学模型之前,你是不是和我一样,有些发懵,什么宝石针,为什么是64片,为什么每一次只能移动一个,还得小的必须在上面,究竟是什么样的呢?
别怕,来看一下图片,缓解一下你有些发懵的大脑:
看完图,是不是好一些呢,其实就是这样的有三根柱子,我们分别命名为ABC,原来是在A柱上有64颗圆盘,现在是要把这些圆盘移动到C上,中间可以临时把圆盘放在C上,B柱为过渡用的。
其实,我们在分析任何问题的时候都可以借助模型,因为人脑对于图画的感受要远远强于对文字的感悟
我们先不管他有 多少个圆盘(假设为n个)
第一:假设只有一个圆盘(n=1):
那是不是就一步就可以了,也就是直接把圆盘从A挪到C上,就可以了,表示为 A --> C;
第二:假设只有两个圆盘(n=2):
我们先把小圆盘从A移动到B,表示为A --> B,
其次把大圆盘从A移动到C,表示为 A --> C,
最后把小圆盘从B移动到C,表示为 B --> C;
第三:假设有三个圆盘(n=3):
先把最小的圆盘移动到C,表示为 A --> C,
第二次把中间的圆盘移动到B,表示为A --> B,
第三次把小圆盘从C移动到B,表示为C --> B,
第四次把大圆盘从A移动到C,表示为A --> C,
第五次把小圆盘从B移动到A,表示为B --> A,
第六次把中间的圆盘从B移动到C,表示为B --> C,
最后把小圆盘从A移动到C,表示为A --> C;
提前看一下代码演示:
第四:假设有n个圆盘呢(n=n):
我们该怎么办呢?
别急,来一杯82年的可乐丫丫筋
请欣赏:
我们可以把n个圆盘,分成两部分:第n个,和剩下的n-1个
接下来把n-1个通过C移动到B上
再把A上的第n个移动到C上,
最后把n-1个移动到C上
大家,不用管中间是怎么移动的,就把他看成是两个部分,这里涉及到了递归的思想,程序调用自身的编程技巧称为递归( recursion),这些都交给计算机去办,比如在上述问题中计算机会把n-1个圆经过C移动到B上,再把第n个移动到C上,然后他接着会回去处理剩下的n-2个,经由C移动到A上,把第n-1个移动到C上,也就是如下图所示的样子:
大家发现了没有,是不是又回到我们最初的样子了,依次是把n-3个经由C移动到B上,再把剩下的第n-2个移动到C上,然后再把第n-4个移动经由C移动到A上,把第n-3个移动到C上...依次类推,直到最后一个完整的移动到C上,我们可以看出在移动的过程中可以不断的重复之前的动作,放到数学和编程里面来说,就是他在不断的调用自身,直到完成要求。
Python代码演示:
def hanoi(n,a,b,c):'''n:圆盘的个数,a:汉诺塔的A柱,b:汉诺塔的B柱,c:汉诺塔的C柱'''if n == 1:print(a,"-->",c)return Noneif n == 2:print(a,"-->",b)print(a,"-->",c)print(b,"-->",c)return Nonehanoi(n-1,a,c,b)#把n-1个盘子从A,由C,移动到B上print(a,"-->",c)hanoi(n-1,b,a,c)#把n-1个盘子从B,经由A,移动到C上a = "A"b = "B"c = "C"
n = 1hanoi(n,a,b,c)A --> Cn = 2 hanoi(n,a,b,c)A --> BA --> CB --> Cn = 3hanoi(n,a,b,c)A --> CA --> BC --> BA --> CB --> AB --> CA --> C