第四题用Python怎么写

第四题是非必答题，要求设计一个非递归算法来解决汉诺塔问题。以下是使用 Python 实现的一个示例：

### 汉诺塔问题的非递归算法

def move_disk(from_rod, to_rod):
    print(f"Move disk from {from_rod} to {to_rod}")

def hanoi_iterative(n, source, auxiliary, target):
    # 初始化栈和移动方向
    stack = []
    moves = []

    # 根据盘子数量决定初始方向
    if n % 2 == 0:
        auxiliary, target = target, auxiliary

    # 将初始状态压入栈
    stack.append((n, source, auxiliary, target))

    while stack:
        n, source, auxiliary, target = stack.pop()

        if n == 1:
            move_disk(source, target)
            moves.append((source, target))
        else:
            stack.append((n - 1, auxiliary, source, target))
            stack.append((1, source, target, target))
            stack.append((n - 1, source, target, auxiliary))

    return moves

# 测试
n = 3
source = 'A'
auxiliary = 'B'
target = 'C'

moves = hanoi_iterative(n, source, auxiliary, target)
print("Total moves:", len(moves))

### 解释

1. **move_disk 函数**：用于打印移动盘子的操作。
2. **hanoi_iterative 函数**：
- 使用栈来模拟递归调用的过程。
- 根据盘子的数量 `n` 决定初始的方向。如果 `n` 是偶数，交换辅助杆和目标杆的位置。
- 将初始状态 `(n, source, auxiliary, target)` 压入栈。
- 当栈不为空时，弹出栈顶元素并处理：
- 如果当前盘子数量 `n` 为 1，直接移动盘子并记录操作。
- 否则，将三个步骤压入栈：
- 先将 `n-1` 个盘子从源杆移动到辅助杆。
- 移动最底下的盘子从源杆到目标杆。
- 最后将 `n-1` 个盘子从辅助杆移动到目标杆。

### 输出

运行上述代码，将会输出每一步的移动操作以及总步数。例如，对于 `n=3` 的情况，输出如下：

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
Total moves: 7

这个非递归算法通过栈来模拟递归过程，避免了递归带来的栈溢出问题，适用于较大的 `n` 值。