汉诺Hanoi塔简介及Python代码

汉诺Hanoi塔简介及Python代码

一、汉诺塔（Tower of Hanoi）简介：
一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

二、游戏规格说明：
有三个立柱A、B、C。A柱上穿有大小不等的圆盘N个，较大的圆盘在下，较小的圆盘在上。要求把A柱上的圆盘全部移到C柱上，保持大盘在下、小盘在上的规律（可借助B柱）。每次移动只能把一个柱子最上面的圆盘移到另一个柱子的最上面。请输出移动过程。

三、 程序代码分析：
利用Python语言，开发者可以更容易的将递归算法翻译成程序语句，需要的代码量很小。汉诺塔问题的解决步骤用语言描述很简单，仅三步：

A，B，C三个圆柱，分别为初始位，过渡位，目标位
1）将最上面的n-1个圆盘从初始位A移动到过渡位B；
2）将初始位A的最底下的一个圆盘移动到目标位C；
3）将过渡位B的n-1个圆盘移动到目标位C

四、Python汉诺塔代码如下：

#!/usr/bin/python3.9
# -*- coding: utf-8 -*-
# @Time    : 2022/1/22 20:33
# @Author  : Alston
# @File    : Hanoi.py
# @Software: PyCharm

'''汉诺塔游戏递归'''
def move(n, a, b, c):
    if n == 1:
        print(a, "--->", c)
    else:
        move(n-1, a, c, b)
        print(a, "--->", c)
        move(n-1, b, a, c)

move(3, "A", "B", "C")

'''完成汉诺塔游戏步数'''
def f(n):
    if n == 0:
        return 0
    else:
        return 2*f(n-1)+1

x = int(input("请输入起始位置数字："))
print("总共完成汉诺塔游戏需要", f(x), "步骤")

五、程序运行结果如下：