论文部分内容阅读
相信大多数人都听说过“汉诺塔”,“汉诺塔”也叫“河内塔”,来自于印度神话里的一种玩具。传说上帝创造世界的时候做了三根金刚石柱子,在其中一根柱子上从下往上按大小顺序摆着64个黄金圆盘。上帝命令婆罗门把那些圆盘从下面开始按大小的顺序重新摆到另一根柱子上,并且还规定,在小圆盘上不能摞大圆盘,在三根柱子之间,一次只能移动一个圆盘,可以想一下,如果移动一个圆盘用1秒钟,等64个圆盘移到另一边的柱子上得要多长时间呢?没有玩过“汉诺塔”的人大概会认为很简单——“不就是把64个圆盘换个位置么”,我们不妨来算一下,它所需要的次数:
3个圆盘被成功移到另一边的柱子上,最少的步数是7次。接下来,在上面再加3个圆盘又要用7次,因此,当有4个圆盘的时候就需要:“3个圆盘重新放到另一柱子上的次数+1次+3个圆盘重新放到另一个柱子上的次数”次即“2×3个圆盘重新放到另一个柱子上的次数+1”次就等于“2×7次+1”=15次。于是可推算出,第n个的时候就是2ד(n-1)个圆盘重新放到另一柱子上的次数”+1次,由此我们可以再进一步推理:由于1个圆盘时不用说是1次,结果n个的时候就是(2n-1)次。
所以,
1个圆盘的时候—2的1次方减1 (21-1) =1
2个圆盘的时候—2的2次方减1 (22-1)=3
3个圆盘的时候—2的3次方减1 (23-1)=7
4个圆盘的时候—2的4次方减1 (24-1)=15
5个圆盘的时候—2的5次方减1 (25-1)=31
……
n个圆盘的时候—2的n次方减1 ( 2n-1)
也就是说64个圆盘的时候,需要(264-1)次才行。我们知道2的64次方已经非常大了,但我们不妨化繁为简:
264=432=1616=2568=655364=42949672962=18446744073709551616所以,264-1=18446744073709551615≈1.845×1019次,这个数可不小啊。说完次数了,那现在就给大家分析一下,如何去找到“汉诺塔”移动的规律。有些人只是凭想象走一步想一步,最后走了不少冤枉步,这种游戏,一般都有规律可寻,大家不妨推理一下,这种小游戏与走迷宫是一样的,与其从头开始转悠半天转不出去,还不如从出口的地方倒着走回来,那一条路便显而易见了,这个“汉诺塔”也是同样的道理:
如上图所示,是一个简单的“汉诺塔模型“,也就是最简单的一关——三层。由前面的推算可得知:把1、2、3按顺序移动到C杆就需要7步,怎么走呢?现在倒推法可以用了,试想要1、2、3移到C杆,就必定是3在C杆的最底层,要想把3移到C杆,1、2就必须“腾出”位置。所以1、2就必须移到B杆上,按照规则大盘不能放在小盘上,则2就必定在B杆最底层,那上面的1也必须为2让路。所以,先把1移到C杆。这样,2就可以移到B杆,再把1从C杆移到B杆。则3就可以从A杆移到C杆。之后,再把1从B杆移到A杆,则2就可以摆在C杆3的上面;再把1移到C杆,就完成了,刚好用到7步。
最简单的一关明白了,再来看一下稍难的——五层:
如上图,是五层的“汉诺塔”模型,同样采用倒推法,试想,要把1、2、3、4、5放到C杆,必定5在C杆最底层,那么1、2、3、4就必须为5“腾出”位,如把1、2、3、4移到B杆,则必定4成了B杆最底层。同理1、2、3要给4让位,就必须把1、2、3移到C。再一想,这不就是前面所说的“三层模型”吗!把1、2、3移到C杆,那么4就可以移到B杆,再把C杆的1、2、3移到B杆4的上面,则5就可以移到C杆,这时就出现了下面这个情况:四个圆盘1、2、3、4在B杆上,5在C杆上。
试想,4必定在5的上面,那么1、2、3就又要给4让位,把1、2、3移到A杆,这样4就可以移到C杆5的上面,最后再利用“三层模型”中说的把1、2、3移到C杆上就可以了,并不像想象中那么麻烦,掌握了技巧,就容易得多了。其实话说白了,不管“汉诺塔”有几层,最基础的是掌握“三层”移动规律。说到这里,还有一个小规律,拿最简单的“三层”那副图说,假设就三个圆盘,都在A杆,要把它们放另两个杆中的任意一个,就把第一个圆盘先放那儿,比如,1、2、3都在A杆,你若想把它们放到B杆就先把1放到B杆,若想把1、2、3放到C杆,就先把1放到C杆。这是一个不起眼的小规律,却可帮你减少时间。这里面还有另一个小规律:圆盘个数分奇数和偶数。先说奇数,若 A杆上的圆盘数是1、3、5、7、9、11等奇数时,第1步就先把最上面的圆盘1放到C杆,记住,在圆盘个数是奇数时,C杆的最底部按规则放的全是第1、3、5、7等序号的奇数圆盘,B杆的最底层按规则放的是2、4、6、8等序号的偶数圆盘;再说个数是偶数时,就是A杆上圆盘数是2、4、6、8、10……等的偶数时,第1步,先把最上面的圆盘1放到B杆,正好和奇数个的相反,在圆盘个数是偶数时,C杆最底部放的也就是最下面的一层全是第2、4、6、8……等序号的圆盘,B杆最底的一层全是1、3、5、7、9等序号的圆盘,这个小规律可以帮你检查在挪动时有没有放错,或走冤枉路等等。
掌握倒推法以后,再多的圆盘也能顺利移动成功,只不过是时间问题了。这和平常我们学习生活是一样的,遇到困难绕个弯,换一个角度,换一种方法就把问题解决了。
3个圆盘被成功移到另一边的柱子上,最少的步数是7次。接下来,在上面再加3个圆盘又要用7次,因此,当有4个圆盘的时候就需要:“3个圆盘重新放到另一柱子上的次数+1次+3个圆盘重新放到另一个柱子上的次数”次即“2×3个圆盘重新放到另一个柱子上的次数+1”次就等于“2×7次+1”=15次。于是可推算出,第n个的时候就是2ד(n-1)个圆盘重新放到另一柱子上的次数”+1次,由此我们可以再进一步推理:由于1个圆盘时不用说是1次,结果n个的时候就是(2n-1)次。
所以,
1个圆盘的时候—2的1次方减1 (21-1) =1
2个圆盘的时候—2的2次方减1 (22-1)=3
3个圆盘的时候—2的3次方减1 (23-1)=7
4个圆盘的时候—2的4次方减1 (24-1)=15
5个圆盘的时候—2的5次方减1 (25-1)=31
……
n个圆盘的时候—2的n次方减1 ( 2n-1)
也就是说64个圆盘的时候,需要(264-1)次才行。我们知道2的64次方已经非常大了,但我们不妨化繁为简:
264=432=1616=2568=655364=42949672962=18446744073709551616所以,264-1=18446744073709551615≈1.845×1019次,这个数可不小啊。说完次数了,那现在就给大家分析一下,如何去找到“汉诺塔”移动的规律。有些人只是凭想象走一步想一步,最后走了不少冤枉步,这种游戏,一般都有规律可寻,大家不妨推理一下,这种小游戏与走迷宫是一样的,与其从头开始转悠半天转不出去,还不如从出口的地方倒着走回来,那一条路便显而易见了,这个“汉诺塔”也是同样的道理:
如上图所示,是一个简单的“汉诺塔模型“,也就是最简单的一关——三层。由前面的推算可得知:把1、2、3按顺序移动到C杆就需要7步,怎么走呢?现在倒推法可以用了,试想要1、2、3移到C杆,就必定是3在C杆的最底层,要想把3移到C杆,1、2就必须“腾出”位置。所以1、2就必须移到B杆上,按照规则大盘不能放在小盘上,则2就必定在B杆最底层,那上面的1也必须为2让路。所以,先把1移到C杆。这样,2就可以移到B杆,再把1从C杆移到B杆。则3就可以从A杆移到C杆。之后,再把1从B杆移到A杆,则2就可以摆在C杆3的上面;再把1移到C杆,就完成了,刚好用到7步。
最简单的一关明白了,再来看一下稍难的——五层:
如上图,是五层的“汉诺塔”模型,同样采用倒推法,试想,要把1、2、3、4、5放到C杆,必定5在C杆最底层,那么1、2、3、4就必须为5“腾出”位,如把1、2、3、4移到B杆,则必定4成了B杆最底层。同理1、2、3要给4让位,就必须把1、2、3移到C。再一想,这不就是前面所说的“三层模型”吗!把1、2、3移到C杆,那么4就可以移到B杆,再把C杆的1、2、3移到B杆4的上面,则5就可以移到C杆,这时就出现了下面这个情况:四个圆盘1、2、3、4在B杆上,5在C杆上。
试想,4必定在5的上面,那么1、2、3就又要给4让位,把1、2、3移到A杆,这样4就可以移到C杆5的上面,最后再利用“三层模型”中说的把1、2、3移到C杆上就可以了,并不像想象中那么麻烦,掌握了技巧,就容易得多了。其实话说白了,不管“汉诺塔”有几层,最基础的是掌握“三层”移动规律。说到这里,还有一个小规律,拿最简单的“三层”那副图说,假设就三个圆盘,都在A杆,要把它们放另两个杆中的任意一个,就把第一个圆盘先放那儿,比如,1、2、3都在A杆,你若想把它们放到B杆就先把1放到B杆,若想把1、2、3放到C杆,就先把1放到C杆。这是一个不起眼的小规律,却可帮你减少时间。这里面还有另一个小规律:圆盘个数分奇数和偶数。先说奇数,若 A杆上的圆盘数是1、3、5、7、9、11等奇数时,第1步就先把最上面的圆盘1放到C杆,记住,在圆盘个数是奇数时,C杆的最底部按规则放的全是第1、3、5、7等序号的奇数圆盘,B杆的最底层按规则放的是2、4、6、8等序号的偶数圆盘;再说个数是偶数时,就是A杆上圆盘数是2、4、6、8、10……等的偶数时,第1步,先把最上面的圆盘1放到B杆,正好和奇数个的相反,在圆盘个数是偶数时,C杆最底部放的也就是最下面的一层全是第2、4、6、8……等序号的圆盘,B杆最底的一层全是1、3、5、7、9等序号的圆盘,这个小规律可以帮你检查在挪动时有没有放错,或走冤枉路等等。
掌握倒推法以后,再多的圆盘也能顺利移动成功,只不过是时间问题了。这和平常我们学习生活是一样的,遇到困难绕个弯,换一个角度,换一种方法就把问题解决了。