汉诺塔问题——用贪心算法解决

目录

一：起源

二：问题描述

三：规律

三：解决方案

递归算法

四：代码实现

复杂度分析

---

一：起源

汉诺塔（Tower of Hanoi）问题起源于一个印度的古老传说。在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的 64 片金片，这就是所谓的汉诺塔。

不论白天黑夜，总有一个僧侣按照下面的法则移动这些金片：

I. 一次只移动一片，不管在哪根针上

II. 小片必须在大片上面

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

二：问题描述

有三根柱子（通常标记为 A、B、C），在其中一根柱子（如 A 柱）上从下到上按大小顺序摞着 n 个圆盘，要求把这 n 个圆盘从起始柱移动到目标柱，每次只能移动一个圆盘，并且在移动过程中任何时候都不能出现大盘在小盘上面的情况。辅助柱用于在移动过程中临时存放圆盘。

三：规律

• 移动次数规律：对于 n 个圆盘的汉诺塔问题，最少需要移动的次数为 \(2^n - 1\) 次。

例如:

当 (n = 1) 时，只需移动 1 次；

当 (n = 2) 时，需要移动 (2^2 - 1 = 3) 次；

当 (n = 3) 时，需要移动 (2^3 - 1 = 7) 次，

以此类推。

• 递归规律：可以将 n 个圆盘的汉诺塔问题分解为三个子问题：
  1. 把上面的 \(n - 1\) 个圆盘从起始柱借助目标柱移动到辅助柱。
  2. 把最大的第 n 个圆盘从起始柱移动到目标柱。
  3. 把 \(n - 1\) 个圆盘从辅助柱借助起始柱移动到目标柱。

三：解决方案

递归算法

递归是解决汉诺塔问题最常用的方法，其核心思想是将大问题分解为小问题。

说到这，小伙伴们是否会自然而然会想到分治算法呢？（C语言）算法复习总结2——分治算法-CSDN博客

四：代码实现

#include <stdio.h>// 递归函数用于解决汉诺塔问题
void hanoi(int n, char source, char target, char auxiliary) {if (n == 1) {// 当只有一个圆盘时，直接从源柱移动到目标柱printf("Move disk 1 from %c to %c\n", source, target);return;}// 把 n-1 个圆盘从源柱借助目标柱移动到辅助柱hanoi(n - 1, source, auxiliary, target);// 把第 n 个圆盘从源柱移动到目标柱printf("Move disk %d from %c to %c\n", n, source, target);// 把 n-1 个圆盘从辅助柱借助源柱移动到目标柱hanoi(n - 1, auxiliary, target, source);
}int main() {int n = 3;  // 圆盘的数量// 调用 hanoi 函数开始移动圆盘hanoi(n, 'A', 'C', 'B');return 0;
}

复杂度分析

• 时间复杂度：由于每次递归调用都会将问题规模减小 1，且每次调用会产生两个新的递归调用，所以时间复杂度为 (O(2^n))。
• 空间复杂度：递归调用栈的最大深度为 n，因此空间复杂度为 (O(n))。