用栈来求解汉诺塔问题

# 递归求解
def hanoiProblem(num, left, mid, right):
    # num是需要移动的盘子数
    # left,mid,right是三座塔
    # 如果盘子数小于等于0
    if num < 1:
        # 移动步数是0
        return 0
    # 其它情况调用递归函数进行求解
    return process(num, left, mid, right, left, right)


# 汉诺塔递归求解函数
def process(num, left, mid, right, from_which, to):
    """
    :param num: 移动的盘子数
    :param left: 左塔
    :param mid: 中塔
    :param right: 右塔
    :param from_which: 盘子现在在哪座塔上
    :param to: 要移动到哪里
    :return: 最少移动步数
    """
    # 递归终止条件
    # 只剩一个盘子
    if num == 1:
        # 第一种情况
        # 从中塔到两端
        # 或者从两端到中塔
        if from_which == 'mid'&nbs***bsp;to == 'mid':
            print("Move 1 from {} to {}".format(from_which, to))
            return 1
        # 第二种情况
        # 从左塔到右塔
        # 或者从右塔到左塔
        else:
            print("Move 1 from {} to {}".format(from_which, mid))
            print("Move 1 from {} to {}".format(mid, to))
            return 2
    # 递归体
    # 第一种情况
    # 从中塔到两端
    # 或者从两端到中塔
    if from_which == 'mid'&nbs***bsp;to == 'mid':
        # 需要三步操作
        # 先将num-1个盘子从from_which移动到除了中塔的另外一座塔上
        another = right if (from_which == 'left'&nbs***bsp;to == 'left') else left
        part1 = process(num - 1, left, mid, right, from_which, another)
        # 将第num个盘子从from_which移动到to
        print("Move {} from {} to {}".format(num, from_which, to))
        part2 = 1
        # 将num-1个盘子从另外一座塔移动到to
        part3 = process(num - 1, left, mid, right, another, to)
        # 最少移动步数
        return part1 + part2 + part3
    # 第二种情况
    # 从左塔移动到右塔
    # 或者从右塔移动到中塔
    else:
        # 分为5步
        # 先将num-1个盘子从from_which移动到to
        part1 = process(num - 1, left, mid, right, from_which, to)
        # 将第num个盘子从from_which移动到中塔
        print("Move {} from {} to {}".format(num, from_which, mid))
        part2 = 1
        # 将num-1个盘子从to移动到from_which
        part3 = process(num - 1, left, mid, right, to, from_which)
        # 将第num个盘子从中塔移动到to
        print("Move {} from {} to {}".format(num, mid, to))
        part4 = 1
        # 最后将num-1个盘子从from_which移动到to
        part5 = process(num - 1, left, mid, right, from_which, to)
        # 最少移动步数
        return part1 + part2 + part3 + part4 + part5


# 移动的盘子数
n = int(input())
step = hanoiProblem(n, 'left', 'mid', 'right')
print("It will move {} steps.".format(step))

# 定义操作列表
# 分别是：
# 不做任何操作
# 左塔到中塔
# 中塔到左塔
# 中塔到右塔
# 右塔到中塔
action = ['No', 'LToM', 'MToL', 'MToR', 'RToM']


# 用栈求解汉诺塔问题
def hanoiProblem(num, left, mid, right):
    """
    :param num:移动的盘子数
    :param left:左塔
    :param mid:中塔
    :param right:右塔
    :return:最少移动步数
    """
    # 用列表模拟栈
    # 左塔
    ls = []
    # 中塔
    ms = []
    # 右塔
    rs = []
    # 将最大值加入栈中
    # 方便后面处理
    max_value = 10 ** 10
    ls.append(max_value)
    ms.append(max_value)
    rs.append(max_value)
    # 向右塔中加入num个盘子
    for i in range(num, 0, -1):
        ls.append(i)
    # 初始化操作序列记录
    record = [action[0]]
    # 初始化最少移动步数
    step = 0
    # 当num座塔没有完全被移动到右塔上时
    while len(rs) != num + 1:
        # 分别进行四种操作的试探
        step += fstackTotstack(record, action[2], action[1], ls, ms, left, mid)
        step += fstackTotstack(record, action[1], action[2], ms, ls, mid, left)
        step += fstackTotstack(record, action[4], action[3], ms, rs, mid, right)
        step += fstackTotstack(record, action[3], action[4], rs, ms, right, mid)
    return step


# 出栈、入栈操作
def fstackTotstack(record, pre_action, now_action, fstack, tstack, from_which, to):
    """
    :param record: 操作序列记录
    :param pre_action: 上个操作
    :param now_action:当前的操作
    :param fstack:出栈
    :param tstack:入栈
    :param from_which:出塔
    :param to:入塔
    :return:移动次数
    """
    # 如果满足操作条件
    if record[0] != pre_action and fstack[-1] < tstack[-1]:
        # 入栈
        tstack.append(fstack.pop())
        print("Move {} from {} to {}".format(tstack[-1], from_which, to))
        # 更新记录
        record[0] = now_action
        return 1
    return 0


n = int(input())
step = hanoiProblem(n, 'left', 'mid', 'right')
print("It will move {} steps.".format(step))