有三个柱子A、B和C,A柱子上从上到下放有n个盘子,盘子大小不同,下面盘子的直径比上面盘子的直径更大。现在要将A柱子上所有的盘子移动到C柱子上,移动过程中可以借助B柱子,但需要满足以下三个规则: 每次只能移动一个盘子; 盘子可以放在空柱子上,也可以放在比自己直径更大的盘子上; 在任意时刻,大盘子必须在下面,小盘子必须在上面。 提示:你可以使用递归算法来解决汉诺塔问题。 编写两个函数 void move(int n,char s,char d);//用来输出移动信息,n为盘子编号,s为移动起点,d为移动终点 void hanoi(int n,char s,char m,char d);//将n个盘子从s借助m移动到d
时间: 2024-03-22 14:39:04 浏览: 167
梵塔难题:已知3个柱子1、2、3和两个圆盘A、B(A比B小),初始状态下,A、B依次放在1柱上,目标状态是A、B依次放在3柱子上,条件是每次可移动一个盘子,盘子上方是空顶方可移动,而且任何时候不允许大盘在小盘之上。
好的,这是一个经典的汉诺塔问题。下面是对应的代码实现:
```python
# 定义move函数,用于输出移动信息
def move(n, s, d):
print("Move disk", n, "from", s, "to", d)
# 定义hanoi函数,用于将n个盘子从s柱子借助m柱子移动到d柱子
def hanoi(n, s, m, d):
if n == 1:
# 只有一个盘子时,直接从s移动到d
move(n, s, d)
else:
# 将n-1个盘子从s借助d移动到m
hanoi(n-1, s, d, m)
# 将第n个盘子从s移动到d
move(n, s, d)
# 将n-1个盘子从m借助s移动到d
hanoi(n-1, m, s, d)
# 测试
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
```
这个代码的时间复杂度是O(2^n),因为对于每个盘子,都需要进行一次移动操作。但是由于汉诺塔问题的特殊性质,可以证明其时间复杂度是最优的。
阅读全文