汉诺塔问题非递归算法python
时间: 2023-07-25 15:14:04 浏览: 64
汉诺塔问题的非递归算法可以使用栈来实现。具体步骤如下:
1. 将源柱子、辅助柱子、目标柱子入栈。
2. 当栈不为空时,重复以下步骤:
a. 弹出栈顶的三个柱子,记为 A、B、C。
b. 如果 A 中只有一个盘子,则将 A 中的盘子直接移到 C 中。
c. 如果 A 中有多个盘子,则将 A 中除最上面的一个盘子外的所有盘子借助 B 移到 C 中,再将最上面的盘子直接移到 C 中。
d. 将 B、A、C 三个柱子按照顺序入栈。
下面是Python代码实现:
```python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def hanoi(n, A, B, C):
stack = Stack()
stack.push((n, A, B, C))
while not stack.is_empty():
n, A, B, C = stack.pop()
if n == 1:
print(f"Move disk {n} from {A} to {C}")
else:
stack.push((n-1, B, A, C))
stack.push((1, A, B, C))
stack.push((n-1, A, C, B))
hanoi(3, 'A', 'B', 'C')
```
输出结果为:
```
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
```