一个n层的汉诺塔，从A移动到C
由于汉诺塔问题本身的限制，我们最先能思考到的点是第n层最后肯定是要放在C的最下面的
有了这个思考后，我们又想，要想使汉诺塔移动次数最小
—— —— —— —— ？？？ 空
A B C
那么我们就要满足可以A中只剩下n这一张圆盘了，而C中是空的，那么我们就可以直接将A中这一张圆盘直接放入C中
OK，A.C的结构确定了，那B的结构是什么呢？
很显然，由于汉诺塔的特性，所以B中此时是n-1层的汉诺塔
我们再将B中的n-1层汉诺塔移动到C中即可，这个操作完全等同于将n-1层汉诺塔从A中移动至C，且B,C为空这一初始条件
因为B中的n-1层圆盘本身满足汉诺塔结构，且第n-1层是小于C中的第n层的也就是可以将C也看成是空的，所以我们可以乱放，怪放，无限放，终极放，究极皮皮放！
OK，我们还要考虑的是从A中移动n-1层到B，这个问题和从A中移动n-1层到C完全一样！！！
所以抛开第n个圆盘从A移动到C这一个操作外
我们还有从A移动整个n-1层汉诺塔到B，然后从B将整个n-1层汉诺塔移动到C的这两步操作！
OK，无论你叫他递归问题也好，DP问题也好，我觉得更像是递归问题，但我还是写成DP的样子把
DP[n] = 2*DP[n-1]+1
写成递归就好
def hanoi(n):
if n == 1:
return 1
result = 0
result += hanoi(n-1)
return result
如果告诉你汉诺塔盘随机地分布在三个柱子上（前提条件是满足每个柱子上依然满足汉诺塔结构），然后问当前状态是不是汉诺塔从A移动到C的必经状态，如果不是返回-1，如果是，返回是当前的第几步
可以这样思考，假设第二个柱子上出现了n号盘子，我们可以肯定的是它不是必经状态因为第n号盘子肯定是直接从A移动到C的
OK有了这个思路就好办了
我们记主柱子为main,辅助柱子为sup，目的柱子为tar
这样记录是有目的的
假设三个汉诺塔是这样的结构
A:main:[X X]
B:sup:[X X]
C:tar:[X X]
假设总共有6号盘子，由上面的结论，从A移动6个盘子到C中总共需要2^6-1 = 63种
我们检查最大的数6在哪个位置
我们知道的是从A将第6号盘子移动到C中是第（63+1）//2 +1 = 32步，
如果6处在sup中，肯定返回-1，
不是的话，我们再看6处在哪个位置
假设6处在tar中，我们可以认为，它可能是将n-1层汉诺塔从sup（B）移动到tar（C）的一个中间过程
那么这个状态就有可能是第34步到第63步中的某一步
记住我们现在的目标是从B中将5层汉诺塔移动到C中，那么此时就与第6个汉诺塔无关
我们将tar中队列最前面的数字弹出tar.pop(0)
且现在的主柱子是B，目标柱子是C，辅助柱子是A，即
A:sup[X X]
B:main[X X]
C:tar[X]
同样的，我们看5在哪，如果5在A中，即辅助柱中，肯定没戏，如果在主柱子中，那么肯定在第32到（63-32+1）//2 +1步中
如此循环
因此我们的程序应该是这样的
因为从A移动n个到C中，所以我们记A为主，B为辅，C为目标，且把所有的盘子按1到n进行标号，
将状态放入A.B.C三个列表中
main = [X,X,X,X,X]
sup = [X,X,X,X,X,X,X]
tar = [X,X,X,X]
两个指针记录区间
left = 1,right = 2^n-1
当left和right重合时，就是找到的次数
while left！ != right:
#如果n在辅助队列中直接返回不在必经之路上
if n in sup:
return -1
#如果n在主队列中，将右区间缩减到原区间的终点的左侧
#且 将目标队列和辅助队列交换位置
#且 将n从main中弹出
elif n in main:
right = (left+right)//2-1
main.pop(0)
sup,tar = tar,sup
elif n in tar:
left = (left+right)//2+1
tar.pop(0)
sup,main = main,sup
reuturn left
考虑了一会儿，发现上面一个漏洞
我们的left和right都是指移动了多少步
而最原始的状态应该表示移动了第0步
所以left的初始值应为0
网友评论