利用栈完成汗诺塔算法
时间: 2023-07-10 10:22:29 浏览: 41
好的,下面是利用栈完成汉诺塔算法的示例代码:
```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, source, helper, target):
if n == 0:
return
s = Stack()
s.push((n, source, helper, target))
while not s.is_empty():
n, source, helper, target = s.pop()
if n == 1:
print("{} -> {}".format(source, target))
else:
s.push((n-1, helper, source, target))
s.push((1, source, helper, target))
s.push((n-1, source, target, helper))
# 示例用法
hanoi(3, 'A', 'B', 'C')
```
这个算法使用了一个栈来模拟递归调用的过程。每次将需要处理的汉诺塔问题压入栈中,然后根据问题规模的大小,将问题分解为更小的子问题,并将子问题压入栈中。最后,当栈为空时,所有的问题都已经被处理完毕。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)