Python 练习

1. 题目

古代有一个梵塔，塔内有 A、B、C 三个基座，A 座上有 64 个盘子，盘子大小不等，大的在下，小的在上。有人想把这 64 个盘子从 A 座移到 C 座，但每次只允许移动一个盘子，并且在移动的过程中，3 个基座上的盘子始终保持大盘在下，小盘在上。在移动过程中盘子可以放在任何一个基座上，不允许放在别处。编写程序，用户输入盘子的个数，显示移动的过程。

2. 分析

假定盘子从大到小依次编号为：盘 1、盘 2、…

1. 如果只有一个盘子，则不需要利用 B 座，直接将盘子从 A 移动到 C

2. 如果有 2 个盘子，可以先将盘 2 移动到 B，将盘 1 移动到 C 后，再将盘 2 移动到 C

3. 如果有 3 个盘子，那么根据 2 个盘子的结论，可以借助 C 将盘 2 和盘 3 从 A 移动到 B，将盘 1 从 A 移动到 C，A 变成空座；借助 A 座，将 B 上的两个盘子移动到 C

上述思路可以一直扩展下去，根据以上的分析，可以写出下面的递归表达：

• 将一个盘子从 A 移动到 C

• 借助 C 将 n-1 个盘子从 A 移动到 B

• 将一个盘子从 A 移动到 C n>1

• 借助 A 将 n-1 个盘子从 B 移动到 C

• 借助 B 将 n 个盘子从 A 移动到 C

为了编写一个递归函数实现借助 B 将 n 个盘子从 A 移到 C，比较等式左右两边相似操作，会发现：

1. 盘子的数量从 n 变化到 n-1，问题规模缩小了，显然 n 是一个可变的参数

2. 盘子的起始位置是变化的，等式左侧是 A，右侧是 A 或 B

3. 盘子的最终位置是变化的，等式左侧是 C、右侧是 B 或 C

4. 同样被借助的位置也是变化的

因此，递归函数共有盘子数、起始位置、借助位置和最终位置 4 个变量，因此函数有 4 个可变参数。

3. 实例

def Hanoi(n, ch1, ch2, ch3):
    if n == 1:
        print(ch1, '->', ch3)
    else:
        Hanoi(n - 1, ch1, ch3, ch2)
        print(ch1, '->', ch3)
        Hanoi(n - 1, ch2, ch1, ch3)


N = int(input("请输入盘子的数量："))
Hanoi(N, 'A', 'B', 'C')
10