python汉诺塔递归算法

汉诺塔问题是一个经典的递归问题，其递归思想是将大问题分解为小问题，直到问题的规模足够小，可以直接求解。下面是Python实现汉诺塔递归算法的代码：

def hanio(n, start, auxiliary, end):
    if n == 1:
        print("将圆盘从" + start + "移动到" + end)
    else:
        # 1. 将n -1个圆盘从A柱（start）经过C柱（end）移动到辅助柱B（auxiliary）
        hanio(n - 1, start, end, auxiliary)
        # 2. 将n个圆盘从A柱（start）移动到C柱（end）
        hanio(1, start, auxiliary, end)
        # 3. 将n-1个圆盘从辅助柱B（auxiliary）经过A柱（start）移动到C柱（end）
        hanio(n - 1, auxiliary, start, end)

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

上述代码中，hanio函数接受四个参数，分别是圆盘的数量n，起始柱子start，辅助柱子auxiliary和目标柱子end。当n等于1时，直接将圆盘从起始柱子移动到目标柱子即可；当n大于1时，需要将n-1个圆盘从起始柱子经过目标柱子移动到辅助柱子，然后将第n个圆盘从起始柱子移动到目标柱子，最后将n-1个圆盘从辅助柱子经过起始柱子移动到目标柱子。

相关问题

汉诺塔递归算法python

汉诺塔是一个经典的递归算法问题，其思路是将n个盘子从起始柱子通过中间柱子移动到目标柱子，保证大盘子在下面，小盘子在上面。在移动过程中，不能将大盘子放在小盘子上面。下面是汉诺塔递归算法的Python实现：

def hanoi(n, start, end, mid):
    if n == 1:
        print(start, '->', end)
    else:
        hanoi(n-1, start, mid, end)
        print(start, '->', end)
        hanoi(n-1, mid, end, start)

其中，n表示盘子的数量，start表示起始柱子，end表示目标柱子，mid表示中间柱子。当n等于1时，直接将起始柱子上的盘子移动到目标柱子上；当n大于1时，先将n-1个盘子从起始柱子移动到中间柱子上，再将最后一个盘子从起始柱子移动到目标柱子上，最后将n-1个盘子从中间柱子移动到目标柱子上。

python汉诺塔非递归算法

汉诺塔问题的非递归算法可以通过栈来实现。具体步骤如下：

1. 将所有的盘子都压入起始柱的栈中，并将起始柱标记为“未完成”状态。
2. 循环执行以下步骤，直到所有盘子都被移到目标柱：

- 若当前柱标记为“未完成”，则将栈顶盘子移到目标柱的栈中，并将目标柱标记为“未完成”状态。

- 若当前柱标记为“已完成”，则将栈顶盘子移到辅助柱的栈中，并将辅助柱标记为“未完成”状态。

- 若当前柱标记为“未完成”，则将栈顶盘子移到起始柱的栈中，并将起始柱标记为“已完成”状态。

3. 将目标柱的所有盘子依次弹出输出。

以下是Python代码实现：

def hanoi(n, start, end, aux):
    stack = [(n, start, end, aux, False)]
    while stack:
        top = stack[-1]
        n, start, end, aux, finished = top
        if n == 1:
            if not finished:
                print(f"Move disk from {start} to {end}")
                stack[-1] = (n, start, end, aux, True)
            else:
                stack.pop()
        elif not finished:
            stack.append((n-1, start, aux, end, False))
        else:
            stack.append((1, start, end, aux, False))
            stack.append((n-1, aux, end, start, False))

# 示例调用
hanoi(3, 'A', 'C', 'B')

输出：

Move disk from A to C
Move disk from A to B
Move disk from C to B
Move disk from A to C
Move disk from B to A
Move disk from B to C
Move disk from A to C