汉诺塔递归算法python
时间: 2023-11-30 11:43:09 浏览: 41
汉诺塔是一个经典的递归算法问题,其思路是将n个盘子从起始柱子通过中间柱子移动到目标柱子,保证大盘子在下面,小盘子在上面。在移动过程中,不能将大盘子放在小盘子上面。下面是汉诺塔递归算法的Python实现:
```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汉诺塔递归算法
汉诺塔问题是一个经典的递归问题,其目标是将所有圆盘从一个标杆移动到另一个标杆,同时满足每次只能移动一个盘子,并且较大的盘子不能放在较小的盘子上面。下面是一个用Python编写的汉诺塔递归算法的示例代码:
```python
def move(n, A, B, C):
if n == 1:
print(A, "->", C)
else:
move(n-1, A, C, B)
print(A, "->", C)
move(n-1, B, A, C)
n = int(input("请输入盘数:"))
print("具体走法步骤如下:")
move(n, "A", "B", "C")
```
这段代码中,`move`函数接受四个参数,`n`表示当前需要移动的盘子数量,`A`、`B`、`C`分别表示三个标杆。当`n`等于1时,直接将盘子从A移动到C;否则,先将n-1个盘子从A移动到B,然后将最后一个盘子从A移动到C,最后再将n-1个盘子从B移动到C。通过递归调用,实现了整个汉诺塔的移动过程。
请注意,这段代码中使用了全局变量`i`来记录移动的步数,所以在使用时需要将全局变量`i`初始化为1。另外,这段代码中的输出语句使用了箭头符号`->`来表示移动的方向。
希望这个示例代码能够帮助你理解和实现汉诺塔递归算法。
#### 引用[.reference_title]
- *1* *3* [汉诺塔递归算法(Python编程)](https://blog.csdn.net/weixin_44263764/article/details/97390068)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [汉诺塔——python递归](https://blog.csdn.net/New_Teen/article/details/123564145)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]
汉诺塔问题非递归算法python
汉诺塔问题的非递归算法可以使用栈来实现。具体步骤如下:
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
```