基于非递归算法的汉诺塔游戏之Python实现

本文代码涉及到汉诺塔问题的非递归算法，可能不是很好理解，我在代码中加了大量注释，希望能够有所帮助，如果实在难以理解的话，请搜索这个算法并结合下面的代码进行阅读和理解。感谢国防科技大学刘万伟老师提供算法思路和第一版本的代码。

def hannoi(n):

#用来记录移动过程中每个盘子的当前位置

#初始都在A柱子上，即chr(65+0)

L = [0] * n

#n个盘子一共需要移动2^n-1次才能完成

for i in range(1, 2**n):

#假设盘子编号分别为0,1,2,...,n-1

#第i步应该移动的盘子编号

#正好是i的二进制形式中最后连续的0的个数

b_i = bin(i)

j = len(b_i) - b_i.rfind('1') - 1

print('第'+str(i)+'步:移动盘子'+str(j+1),

chr(65+L[j]),'->', end=' ')

#把ABC三根柱子摆成三角形

#把第j个盘子移动到下一根柱子上

#根据j的奇偶性决定是顺时针移动还是逆时针移动

L[j] = ((L[j]+1)%3 if j%2 == 0 else (L[j]+2)%3)

#下一根柱子，这里65是A的ASCII码

print(chr(65+L[j]))

hannoi(3)

运行结果为：

第1步:移动盘子1 A -> B

第2步:移动盘子2 A -> C

第3步:移动盘子1 B -> C

第4步:移动盘子3 A -> B

第5步:移动盘子1 C -> A

第6步:移动盘子2 C -> B

第7步:移动盘子1 A -> B