左移汉诺塔问题

来源：百度知道编辑：UC知道时间：2024/07/05 16:37:59

背景:汉诺塔(Hanoi)问题源自一个古老的传说:相传在古印度的一座神庙前,有一根串着64个祭神用的圆盘的柱子,这些圆盘是按大小顺序叠放的,大的在下,小的在上,僧侣们要将这些圆盘借助一个柱子移到另一个柱子上,移动过程中,一次只能移动一个,并且要始终保证每个柱子上的圆盘大的在下,小的在上,什么时候移完,就意味着世界末日.
现在很多电子辞典都有这款游戏,三根柱子,n个圆盘在第一根柱子上,要全部移到第三根柱子上.而且很容易推出,n个圆盘时,最小移动次数为2^n-1次.
很不巧,我的电子辞典右键用不了,所以圆盘只能左移,且最左端的可以移到最右端,即可能的移动情况为:1->3,2->1,3->2.(数字代表第几根柱子)
问:能否推出n个圆盘的最小移动次数f(n)?递推式也可以.
补充:这个问题是肯定有解的,这没问题.我自己玩了1、2、3、4、5、6个盘,由经验加归纳推出了下列递推式:
f(0)=0;f(1)=1;
f(n)=2*f(n-1)+2*f(n-2)+3
这是肯定可行的,即这必然是其中一个解,但本人不能证明它是最优解.如果问题有最优解,则必然不会比这个解差,恳请各路英雄指点一下小弟,不胜荣幸!

确实，我想错了。正在重新思考

想好了。首先我们清理一下原有的思路。可以用右键的时候：
设n个盘的步数为An。为了把n+1个盘放到最右边，先要把前n个盘放到中间。（我们认为这是最少的步骤。）但是在可以用右键的情况下，整体左移和右移用的步数是一样的。所以有An+1=（2An）+1
最终利用递推法证明An=2^n-1

同样的思路，如果不能用右键，要把n个圆盘挪到最右边，还是要先把n-1个右移到中间，然后挪动地n个盘子，在把n-1个盘子挪到最右边。（这也一定是最少的步骤）。但是此时右移和左移的步骤次数不一样了，这就是最麻烦的部分。
设有一n的盘子的步骤为Bn，而左移n盘子的步骤是An。我们要求的就是An的通项公式。

首先我们有Bn=（Bn-1）+1+(An-1)+1+(Bn-1)
右移的分步考虑，从左到右表示最短步骤：右移n-1个，左移第n个，左移n-1个，左移第n个，右移n-1个。到此完成整个右移过程。

同理有An=(Bn-1)+1+(Bn-1)

把An的公式代入Bn的公式有
Bn=2(Bn-1)+2(Bn-2)+3 （这里是右移的式子，左移要小很多。比如左移3个，只需要15步，但你的式子要用21步）

B1显然等于2，B2显然等于7。（你们应该不会找到更少的步骤吧？）
那么根据计算B3=21 （实际也是，不可能再少了）

所以如果能从B1，B2，B3及Bn=2(Bn-1)+2(Bn-2)+3 猜出Bn的通项公式就可以用递推法证明了。然后An的通项公式也就出来了。但是我想了一个下午也没想出来。暂时只能到这里了。

楼上的,光用左肯定是能(前提,左边的按下左就到右边了)
1234代表4个盘子,0代表没有盘子
100 000 000 000 000 000 000 000 000 000 000 000 000 000 000
200 200 200 000 100 100 000 000 000 000 000 000 000 100 100
300 300 300 300 300 300 300 310

左移汉诺塔问题问题？？？问题~~~~~~~~~ 问题~~~~~~~~~~~~ 问题````````````````````````` 问题`````` ~~~问题! 问题`？` 问题～～～～～～～～问题????