河内塔算法： Python, C++ Code
陈莎拉
汉诺塔是什么？
汉诺塔是一个数学谜题，由三根杆和一叠大小递减的圆盘组成。它也被称为梵天塔或卢卡斯塔，因为法国数学家爱德华·卢卡斯于1883年提出了这个谜题。这个谜题源于一个关于在三根杆之间移动金圆盘的传说。
这个拼图由三根杆和数量不定的堆叠圆盘组成。杆子排列成循环塔状，较大的圆盘堆叠在底部，较小的圆盘堆叠在顶部。
游戏开始时，我们有三个木桩或木杆。其中一个木桩（例如示例中的木桩 A）上堆叠着所有的圆盘。目标是在遵守一些特定规则的前提下，将整个圆盘堆从一根木杆（A）移动到另一根木杆（C）。
以下是谜题的初始设置：
汉诺塔问题
这就是最终目标：
汉诺塔规则
以下是汉诺塔的基本规则：
- 在拼图的初始状态下，所有圆盘都堆叠在第一根杆上。
- 最终状态下，杆一上的所有圆盘都堆叠在杆二或杆三上。
- 任何时候都只能有一个圆盘从一根杆移动到另一根杆上。
- 只有杆上的最上层圆盘才能移动。
- 一张大圆盘不能放在一张小圆盘上面。
最初的传说是关于移动64个圆盘。祭司们按照规则一次只能移动一个圆盘。传说中预言，如果他们能够完成这项壮举，世界将会毁灭。在时间复杂度部分，我们将证明，对于n个圆盘的汉诺塔场景，需要2^n-1次移动。
因此，如果祭司们需要 1 秒钟才能移动一个圆盘，那么解决这个谜题的总时间将是 2^64 – 1 秒，或大约 584,942,417,356 年 26 天 7 小时 15 秒。
汉诺塔算法
解决汉诺塔问题的最常用方法是递归算法。首先，我们选择两根杆子作为起点和终点；备用杆子则作为辅助杆或帮手。
以下是解决汉诺塔难题的步骤：
- 将最上面的 n-1 个盘子从源桩移到辅助桩。
- 将第 n 个圆盘从源柱移动到目标柱。
- 将剩余的 n-1 个圆盘从辅助柱移到目标柱。
注意： 如果我们只有一个磁盘，我们可以直接将其从源磁盘移动到目标磁盘。
如何解决汉诺塔难题
让我们用三个圆盘来说明这个算法。假设 A 为源点，B 为辅助点，C 为目标点。
步骤1） 最初，所有圆盘都堆放在 A 柱上。
现阶段：源点 = Peg A，目的地 = Peg C，助手 = Peg B。
现在，我们需要将最上面的 n-1 个盘子从源盘子移到辅助盘子。
注意： 虽然我们一次只能移动一个磁盘，但这一步将我们的 3 个磁盘问题简化为 2 个磁盘问题，这可以通过递归调用来处理。
步骤2） 当我们从桩 A 递归调用桩 B 为目标时，我们使用桩 C 作为辅助桩。
注意，我们又回到了汉诺塔问题的第一阶段，但这次是两个圆盘。我们将 n-1（即一个）圆盘从源点移动到辅助点，辅助点再将最小的圆盘从 A 柱移动到 C 柱。
现阶段：源点 = 桩 A，目的地 = 桩 B，助手 = 桩 C。
步骤3） 根据该算法，第 n 个（第 2 个）磁盘现在被转移到目的地，即桩 B。
现阶段：源点 = 桩 A，目的地 = 桩 B，助手 = 桩 C。
步骤4） 现在，我们将 n-1 号圆盘（圆盘一）从辅助柱 C 移动到目标柱 B，按照算法的第三阶段进行操作。
现阶段：源点 = 桩 A，目的地 = 桩 B，助手 = 桩 C。
步骤5） 递归调用完成后，我们回到算法第一阶段的先前设置。
步骤6） 在第二阶段，我们将磁盘 3 从源柱 A 移动到目标柱 C。
现阶段：源点 = 桩 A，目的地 = 桩 C，助手 = 桩 B。
步骤7） 下一个任务是将剩余的圆盘从辅助柱（柱子 B）移动到目标柱（柱子 C）。这次我们将使用原来的源柱（柱子 A）作为辅助柱。
步骤8） 由于我们不能同时移动两个磁盘，所以我们对磁盘 1 进行递归调用。根据我们的 算法此步骤的目标位置是桩 A。
现阶段：源点 = 桩 B，目的地 = 桩 A，助手 = 桩 C。
步骤9） 我们的递归调用已完成。现在我们将磁盘 2 从源磁盘移动到目标磁盘。
现阶段：源点 = 桩 B，目的地 = 桩 C，助手 = 桩 A。
步骤10） 最后，我们将剩余的 n-1 个磁盘（磁盘 1）从辅助磁盘移动到目标磁盘。
现阶段：源点 = 桩 A，目的地 = 桩 C，助手 = 桩 B。
昵称 Code 汉诺塔
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1 THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi(disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi(disk - 1, helper, dest, source)
END IF
END Procedure
程序代码 C++
#include <bits/stdc++.h> using namespace std; void tower_of_hanoi(int num, string source, string dest, string helper) { if (num == 1) { cout << " Move disk 1 from tower " << source << " to tower " << dest << endl; return; } tower_of_hanoi(num - 1, source, helper, dest); cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl; tower_of_hanoi(num - 1, helper, dest, source); } int main() { int num; cin >> num; printf("The sequence of moves :\n"); tower_of_hanoi(num, "I", "III", "II"); return 0; }
输出：
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
程序代码 Python
def tower_of_hanoi(n, source, destination, helper): if n == 1: print("Move disk 1 from peg", source, "to peg", destination) return tower_of_hanoi(n - 1, source, helper, destination) print("Move disk", n, "from peg", source, "to peg", destination) tower_of_hanoi(n - 1, helper, destination, source) # n = number of disks n = 3 tower_of_hanoi(n, 'A', 'B', 'C')
输出：
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
汉诺塔的复杂性
以下是汉诺塔在时间和空间上的复杂性：
1）时间复杂度：
回顾算法，每次调用都会对 (n-1) 个磁盘进行两次递归调用。每次 (n-1) 次递归又会分解为 ((n-1)-1) 次递归，依此类推，直到达到单磁盘的基本情况。
适用于三张光盘：
- 磁盘 3 对磁盘 2 调用递归函数两次。
- 磁盘 2 对磁盘 1 调用递归函数两次。
- 圆盘 1 以恒定时间移动，因此有时间求解三个圆盘。
以循环形式表达：
= 2 × (求解两个圆盘所需时间) + 移动圆盘 3 的常数时间
= 2 × (2 × 求解一个圆盘所需时间 + 移动圆盘 2 的常数时间) + 移动圆盘 3 的常数时间
= (2 × 2) × 移动圆盘 1 的常数时间 + 2 × 移动圆盘 2 的常数时间 + 移动圆盘 3 的常数时间
对于 n 个磁盘，则变为：
2正1 × 移动圆盘 1 + 2 的恒定时间正2 × 移动圆盘所需时间 2 + ….
这个等比数列的和为 O(2)n – 1），简化为 （2）n)时间复杂度呈指数级增长。
2）空间复杂度：
汉诺塔的空间复杂度为 O(n)。递归使用调用栈，而栈的最大深度等于 n，即圆盘的数量。这就是空间复杂度为 O(n) 的原因。
