算法学习：汉诺塔算法

汉诺塔问题

背景

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

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

思路

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

过程

汉诺塔的解决过程：

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

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

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

算法

# 汉诺塔问题

def hannuota(n,x,y,z):
    '''
    :param n: 代表要移动n个盘子
    :param x: 代表x轴
    :param y: 代表y轴
    :param z: 代表z轴
    :return:
    '''
    if n == 1:
        print("把第 %d 个盘子 从 %s --》%s"%(n,x,z))
    else:
        # 简化为三步：
        # 第一步：将前 n-1 个盘子从x轴借助z轴，移动到y轴
        hannuota(n-1,x,z,y)
        # 第二步：将第n个盘子从x轴移动到z轴
        print("把第 %d 个盘子 从 %s --》%s" % (n, x, z))
        # 第三步：将第n-1个盘子从y轴借助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