写出汉诺塔递归 用python
时间: 2023-05-30 09:03:05 浏览: 86
汉诺塔问题是一种经典的递归问题,可以用Python实现。以下是汉诺塔递归的Python代码示例:
```python
def hanoi(n, A, B, C):
if n == 1:
print(A, "->", C)
else:
hanoi(n-1, A, C, B)
print(A, "->", C)
hanoi(n-1, B, A, C)
# 示例
hanoi(3, "A", "B", "C")
```
上述代码中,hanoi函数接收四个参数:n表示盘子的数量,A、B、C分别表示三个柱子。当n等于1时,直接将A柱子上的盘子移动到C柱子上。当n大于1时,首先将n-1个盘子从A柱子移动到B柱子上,然后将A柱子上的最后一个盘子移到C柱子上,最后将B柱子上的n-1个盘子移动到C柱子上。递归过程中,每次调用hanoi函数都相当于解决一个规模更小的汉诺塔问题。
相关问题
汉诺塔递归算法python
汉诺塔是一个经典的递归算法问题,其思路是将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 hanoi(n, source, target, auxiliary):
stack = []
while True:
while n > 1:
stack.append((n, source, target, auxiliary))
n -= 1
source, target, auxiliary = source, auxiliary, target
print(f"Move disk {n} from {source} to {target}")
if stack:
n, source, target, auxiliary = stack.pop()
print(f"Move disk {n} from {source} to {target}")
n -= 1
source, target, auxiliary = auxiliary, target, source
else:
break
# 测试
hanoi(3, 'A', 'C', 'B')
```
这段代码使用了一个栈来模拟递归的过程。首先将所有的子问题入栈,然后依次出栈并处理,直到栈为空。