用递归函数解决汉诺塔问题
时间: 2023-12-04 20:38:05 浏览: 35
汉诺塔问题是一个经典的递归问题,可以用递归函数来解决。汉诺塔问题的规则如下:有三个柱子A、B、C,A柱子上有n个盘子,盘子大小不等,大的在下面,小的在上面。要求把A柱子上的盘子全部移到C柱子上,并且每次移动只能移动一个盘子,大盘子不能放在小盘子上面。在移动盘子时可以利用B柱子作为中转。
以下是Python代码实现:
```python
def hanoi(n, A, B, C):
if n == 1:
print(A, '-->', C)
else:
hanoi(n-1, A, C, B) # 将前n-1个盘子从A移动到B上
print(A, '-->', C) # 将最底下的最后一个盘子从A移动到C上
hanoi(n-1, B, A, C) # 将B上的n-1个盘子移动到C上
# 测试
hanoi(3, 'A', 'B', 'C')
```
输出结果为:
```
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C
```
相关问题
利用递归函数解决汉诺塔问题
汉诺塔问题是经典的递归问题,可以用递归函数来解决。其基本思想是将大问题分解成小问题来解决,直到问题规模足够小可以直接求解。
具体来说,汉诺塔问题可以描述为:有三个柱子A、B、C,A柱子上面有n个盘子,盘子大小不同且从上到下递减。现在要把这n个盘子从A柱子移动到C柱子,期间可以借助B柱子,但是要求每次只能移动一个盘子,并且大盘子不能放在小盘子上面。
下面是利用递归函数解决汉诺塔问题的代码实现:
```python
def hanoi(n, a, b, c):
if n == 1:
print(f"Move disk {n} from {a} to {c}")
else:
hanoi(n-1, a, c, b)
print(f"Move disk {n} from {a} to {c}")
hanoi(n-1, b, a, c)
# 测试
hanoi(3, 'A', 'B', 'C')
```
其中,n表示盘子数量,a、b、c分别表示A、B、C三个柱子。当n=1时,直接将盘子从a移动到c;当n>1时,将前n-1个盘子从a移动到b,再将第n个盘子从a移动到c,最后将前n-1个盘子从b移动到c。
使用递归函数实现汉诺塔问题
下面是使用递归函数实现汉诺塔问题的 Python 代码:
```python
def hanoi(n, source, target, auxiliary):
if n == 1:
print('Move disk 1 from', source, 'to', target)
return
hanoi(n-1, source, auxiliary, target)
print('Move disk', n, 'from', source, 'to', target)
hanoi(n-1, auxiliary, target, source)
# 测试代码
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` 表示汉诺塔的盘子数,`source` 表示起始柱子,`target` 表示目标柱子,`auxiliary` 表示辅助柱子。首先判断如果只有一个盘子,则直接从起始柱子移动到目标柱子;否则,先将前 `n-1` 个盘子从起始柱子移动到辅助柱子,再将最后一个盘子从起始柱子移动到目标柱子,最后将前 `n-1` 个盘子从辅助柱子移动到目标柱子,递归结束。