p ython实现汉诺塔
时间: 2023-06-16 08:07:15 浏览: 66
汉诺塔是一种经典的递归问题,以下是 Python 实现:
```python
def hanoi(n, start, target, aux):
if n == 1:
print(f"Move disk 1 from {start} to {target}")
return
hanoi(n-1, start, aux, target)
print(f"Move disk {n} from {start} to {target}")
hanoi(n-1, aux, target, start)
# 测试
hanoi(3, 'A', 'C', 'B')
```
输出结果为:
```
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
```
解释:假设有 n 个盘子需要从起始柱子移动到目标柱子,可以将此问题拆解为三个子问题:将前 n-1 个盘子从起始柱子移动到辅助柱子、将第 n 个盘子从起始柱子移动到目标柱子、将前 n-1 个盘子从辅助柱子移动到目标柱子。由于子问题的规模都是 n-1,因此可以使用递归来解决问题。需要注意的是,每次移动盘子时需要输出移动的步骤。
相关问题
p ython实现递归汉诺塔
好的,以下是 Python 实现递归汉诺塔的代码:
```python
def move(n, A, B, C):
if n == 1:
print(f"Move disk {n} from {A} to {C}")
else:
move(n-1, A, C, B)
print(f"Move disk {n} from {A} to {C}")
move(n-1, B, A, C)
```
其中,n 表示盘子的数量,A、B、C 分别表示三根柱子,我们需要将 A 柱子上的 n 个盘子移动到 C 柱子上。每次移动的规则是:在 n-1 个盘子所在的柱子(假设为 A)上,将最大的盘子移到目标柱子(C),再将 n-1 个盘子移到中间柱子(B),最后将最大的盘子从中间柱子(B)移到目标柱子(C)上即可。
p y t hon汉诺塔递归
汉诺塔问题是一个经典的递归问题,可以使用递归算法来解决。下面是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)
```
其中,n表示盘子的数量,a、b、c分别表示三个柱子。在汉诺塔问题中,我们要将n个盘子从柱子a移动到柱子c,可以借助柱子b。这个问题可以分解成三个子问题:
1. 将n-1个盘子从a移动到b,可以借助c;
2. 将最后一个盘子从a移动到c;
3. 将n-1个盘子从b移动到c,可以借助a。
递归调用函数hanoi()可以解决这个问题。当n=1时,直接将盘子从a移动到c即可;当n>1时,先将前n-1个盘子从a移动到b,然后将最后一个盘子从a移动到c,最后将前n-1个盘子从b移动到c即可。
阅读全文