汉诺塔问题

背景

3根柱子（x,y,z轴），64个盘子（在x轴上）从下至上盘子是从大到小的。

将盘子从x轴搬到z轴有2个条件：
第一：1次只能挪动1个盘子
第二：大的盘子不能放到小的盘子上面

思路

1.对于问题N，如果问题N-1已经解决了，那么N就很容易解决
2.问题点转换为了如何求解 N-1

过程

汉诺塔的解决过程：

假如要挪动6个盘子，那么要做以下三步：

第一步：将第 2 - 6个盘子，挪动到Y轴---》求解N-1
第二步：将第1个盘子挪动到Z轴
第三步：将第2-6个盘子从Y轴挪到Z轴

求解N-1的过程类似于求解N的过程（每一步只需要考虑从N-1到N的过程，无需考虑从1-N）
.....
求解第一层：将圆盘从x轴 搬到 z轴

算法

def hannuota(n,x,y,z):
    ‘‘‘
    n表示圆盘
    xyz表示n本来在x轴，要搬到z轴
    ‘‘‘
    if n==1:
        print("当前搬动的是第%s个盘子，搬动路径为%s==%s"%(n,x,z))
    else:
         # 第一步将前N-1个盘子，从X轴借助Z轴搬到Y
        # 第二步将第N个盘子，从X轴搬到Z轴
        # 第三步将前N-1个盘子，从Y轴借助X轴搬到Z轴
        hannuota(n-1,x,z,y)
        print("当前搬动的是第%s个盘子，搬动路径为%s==%s"%(n,x,z))        
        hannuota(n-1,y,x,z)

print(hannuota(3,"X","Y","Z"))

• 运行结果

当前搬动的是第1个盘子，搬动路径为X==Z
当前搬动的是第2个盘子，搬动路径为X==Y
当前搬动的是第1个盘子，搬动路径为Z==Y
当前搬动的是第3个盘子，搬动路径为X==Z
当前搬动的是第1个盘子，搬动路径为Y==X
当前搬动的是第2个盘子，搬动路径为Y==Z
当前搬动的是第1个盘子，搬动路径为X==Z
None

算法学习：汉诺塔算法

原文：https://www.cnblogs.com/hqq2019-10/p/14418835.html