汉诺塔，递归与 python 实现

汉诺塔问题

在三个柱子 A，B，C 中的 A 柱子上放着若干圆盘，其中下面的圆盘总比上面的圆盘大，这个规则三个柱子都必须遵循，目的是：借助三个柱子把若干圆盘都从 A 柱子上移到 C 柱子上，求解其中的步骤。

汉诺塔与递归

汉诺塔问题是一个经典的递归问题。
简单的递归理解就是在一个方法中调用它本身。
更进一步的理解，就是把一个问题持续分解为更简单的问题，直至问题小到可以解决，当然核心还是调用了它本身来解决。

汉诺塔思想

把 A 柱子上的圆盘移到 C 柱子上的步骤最终只有三个而已

1. 把 A 柱子上的除最后一个外的所有园盘都移到 B 柱子上。
2. 把 A 柱子上剩下的那个圆盘移到 C 柱子上。
3. 把剩下的 B 柱子上的所有圆盘豆移到 C 柱子上。

python 实现

count = 0  # 计算总共有多少步
def hanoi(a, b, c, num):
    """
    汉诺塔
    :param a: A 柱子
    :param b: B 柱子
    :param c: C 柱子
    :param num:  圆盘个数
    :return: 
    """
    global count 
    if num == 1:  # 当剩下一个盘时，从 "A" 柱子上移到 "C" 柱子上（注意引号）
        count += 1
        print a + "->" + c
        return
    num -= 1
    hanoi(a, c, b, num)  # 第一步： 把 A 柱子上的除最后一个外的所有原盘都移到 B 柱子上。
    count += 1
    print a + "->" + c  # 第二步： 把 A 柱子上剩下的那个圆盘移到 C 柱子上。
    hanoi(b, a, c, num)  # 第三步：把剩下的 B 柱子上的所有圆盘豆移到 C 柱子上。


if __name__ == '__main__':
    hanoi("A", "B", "C", 3)
    print count

返回结果：

A->C
A->B
C->B
A->C
B->A
B->C
A->C
7

感谢阅读！
如果文章中有错误或存在误解的地方，麻烦多加指教，无比感谢！
The End.