免费可商用网站,短链接生成器手机版,国外域名绑定国内服务器,免费下载app软件的网站目录
问题描述 第一性原理分析
代码实现
第一步#xff1a;明确函数要干什么
第二步#xff1a;写好递归的“结束条件”
第三步#xff1a;写递归步骤 #x1f333; 递归调用树
#x1f50d;复杂度分析
时间复杂度#xff1a;T(n) 2^n - 1 空间复杂度分析 问题描…目录
问题描述 第一性原理分析
代码实现
第一步明确函数要干什么
第二步写好递归的“结束条件”
第三步写递归步骤 递归调用树
复杂度分析
时间复杂度T(n) 2^n - 1 空间复杂度分析 问题描述
有三个柱子A, B, C上面有 n 个大小不等的圆盘最开始所有圆盘按从大到小顺序堆在柱子 A 上。 目标将所有圆盘移动到柱子 C移动时要满足 一次只能移动一个盘子 任何时刻小盘子不能压在大盘子上。
❓核心问题
如何将 n 个盘子 从 A 移动到 C同时只用 B 做辅助且不违反约束 第一性原理分析
1.基础情况Base Case n 1只有一个盘子直接从 A → C一步解决。这是最小子问题。
2. 如果有两个盘子要怎么动
设柱子为 A起始、B辅助、C目标
你会这样操作 把小盘子从 A → B 把大盘子从 A → C 再把小盘子从 B → C 3. 如果有三个盘子要怎么动
步骤 1移动盘子 1 从 A ➜ C
步骤 2移动盘子 2 从 A ➜ B
步骤 3移动盘子 1 从 C ➜ B
步骤 4移动盘子 3 从 A ➜ C
步骤 5移动盘子 1 从 B ➜ A
步骤 6移动盘子 2 从 B ➜ C
步骤 7移动盘子 1 从 A ➜ C
这就引出一个关键逻辑
✅ 要移动第 n 个最大盘子必须先把上面的 n-1 个盘子“暂时”搬开。 移动 n 个盘子的本质是 —— 找出一个“序列”让我们可以先清掉上面的 n-1 个盘子再移动第 n 个然后再恢复那 n-1 个。 换句话说 把 n-1 个盘子移到辅助柱 把第 n 个最大盘子移到目标柱 再把那 n-1 个盘子从辅助柱移回来。
这三步操作可以形成递归
Hanoi(n, A, B, C):1. 移动 n-1 个盘子从 A → B借助 CHanoi(n-1, A, C, B)2. 移动第 n 个盘子从 A → C3. 移动 n-1 个盘子从 B → C借助 AHanoi(n-1, B, A, C)所以从第一性来看汉诺塔的“递归”不是魔法而是逻辑 没有任何一步是“看上去神奇的” 每一个盘子的移动都必须建立在“先让出空间”的原则上 这就导致了问题具有自相似性每一层和上面那一层的问题结构一样
原理对应在汉诺塔问题的体现 本质原子操作移动一个盘子必须遵守限制 问题的自相似性每个子问题与原问题结构完全一样 ⇒ 递归自然产生 从底向上构建解决结构不依赖公式从 n 1 出发构建到 n 2, 3... 代码实现
第一步明确函数要干什么
我们要写的是一个函数移动 n 个盘子从柱子 A → 柱子 C借助柱子 B。 所以我们需要 盘子的数量int n 三个柱子的名字我们用字符char from, temp, to
#include iostream
using namespace std;// 函数声明移动 n 个盘子从 from → to借助 temp
void hanoi(int n, char from, char temp, char to) {解释 n要移动的盘子数 from起始柱 temp中转柱辅助 to目标柱
第二步写好递归的“结束条件”
为什么要加“终止条件”
如果你不加递归会无限下去直到程序崩溃 if (n 1) {cout Move disk 1 from from to to endl;return;}解释 如果只剩一个盘子那就是最简单的情况直接从 from → to。 cout 是打印这一步。
第三步写递归步骤 // 1. 把 n-1 个盘子从 from → temp借助 tohanoi(n - 1, from, to, temp);// 2. 把第 n 个盘子从 from → tocout Move disk n from from to to endl;// 3. 把 n-1 个盘子从 temp → to借助 fromhanoi(n - 1, temp, from, to);
}分析这三步逻辑 把顶部的 n-1 个盘子先“挪走”递归调用自己 把第 n 个盘子最大的真正地移动到底部打印出来 把刚才挪走的 n-1 个盘子搬回来递归调用自己。
完整代码
#include iostream
using namespace std;// 递归函数将 n 个盘子从 from 移动到 to借助 temp
void hanoi(int n, char from, char temp, char to) {if (n 1) {cout Move disk 1 from from to to endl;return;}// 第一步把 n-1 个盘子从 from → temphanoi(n - 1, from, to, temp);// 第二步移动第 n 个盘子到目标柱cout Move disk n from from to to endl;// 第三步把 n-1 个盘子从 temp → tohanoi(n - 1, temp, from, to);
}int main() {int n;cout Enter number of disks: ;cin n;hanoi(n, A, B, C);return 0;
}递归调用树
我们现在来画出 hanoi(3, A, B, C) 的调用树结构说明递归是怎么层层展开的。 hanoi(3, A, B, C)/ | \hanoi(2, A, C, B) Move 3 hanoi(2, B, A, C)/ | \ / | \hanoi(1,A,B,C) M2 hanoi(1,C,A,B) hanoi(1,B,C,A) M2 hanoi(1,A,B,C)标上实际操作编号 hanoi(3, A, B, C)/ | \hanoi(2, A, C, B) Move 3 hanoi(2, B, A, C)/ | \ / | \hanoi(1,A,B,C) M2 hanoi(1,C,A,B) hanoi(1,B,C,A) M2 hanoi(1,A,B,C)/ | \ | / | \
step1 step2 step3 step4 step5 step6 step7
调用操作内容ABChanoi(3, A, B, C)主函数入口[3, 2, 1][][]hanoi(2, A, C, B)把上面两个盘子从 A ➜ Bhanoi(1, A, B, C)直接移动盘子 1Move disk 1 A→CStep 1[3, 2][][1]Move disk 2 A→BStep 2[3][2][1]Move disk 1 C→BStep 3[3][2, 1][]Move disk 3 A→CStep 4[][2, 1][3]hanoi(2, B, A, C)把两个盘子从 B ➜ CMove disk 1 B→AStep 5[1][2][3]Move disk 2 B→CStep 6[1][][3, 2]Move disk 1 A→CStep 7[][][3, 2, 1] 复杂度分析
时间复杂度T(n) 2^n - 1
汉诺塔的递归形式是这样的
T(n) 2 * T(n - 1) 1意思是 为了移动 n 个盘子 我们要先移动 n - 1 个盘子第一次调用 移动第 n 个盘子1 次 再移动 n - 1 个盘子第二次调用。
利用迭代展开式来看
T(n) 2*T(n-1) 1 2*(2*T(n-2) 1) 1 4*T(n-2) 2 1 8*T(n-3) 4 2 1 ... 2^k * T(n - k) (2^(k-1) ... 2 1)当 k n-1 时T(1) 1代入得到
T(n) 2^(n - 1) * T(1) (2^(n - 2) ... 1) 2^(n - 1) * 1 (2^(n - 1) - 1) 2^n - 1所以时间复杂度是⏱️ T(n) O(2^n)
也就是说 每增加一个盘子所需的移动次数翻倍 1。 极其不可扩展。 空间复杂度分析
我们来看递归函数会“开多少层栈”
void hanoi(int n, char from, char temp, char to)
{if (n 1) return;hanoi(n - 1, from, to, temp); // 一次递归调用// move...hanoi(n - 1, temp, from, to); // 第二次递归调用
}递归深度分析 最大的递归深度就是从 n → n-1 → n-2 → ... → 1 所以最多开 n 层函数栈
所以空间复杂度是 Space: O(n) 因为递归是深度优先遍历 不会存储所有子问题只保存当前路径
️ 如果你是“神庙僧侣”每天只移动 1 次
汉诺塔在传说中是64 个金盘子僧侣每天移动一块。
T(64) 2^64 - 1 ≈ 1.84 × 10^19 次即使 1 秒动一次你也需要
≈ 5.8 × 10^11 年而宇宙年龄都才 138 亿年。所以说移动 64 个盘子“永远也完成不了”。
