知识卡片

普通读书笔记卡 · 5654.c.3.g.2

汉诺塔子任务必须按序执行

理解等级:中级

把上面n-1盘借目标柱移到缓冲柱,移动最大盘到目标柱,再把缓冲柱的n-1盘借原柱移过去。每步都保持小盘在大盘上,后一步依赖前一步形成的柱状态。

最少移动数为2的n次方减1,调用栈线性;若保留全部移动记录,输出空间还指数增长。原书只检查i==1,须n≥1且柱状态合法,空输入否则会无限递归;这些子任务不能因分治形式就并行。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      按照以下顺序解决这三个子问题。 1. 将 −1 个圆盘借助C A 移至 B 2. 将剩余 个圆盘从A 直接移至 C 3. 将 −1) (1) (1) 个圆盘借助A B 移至 C 对于这两个子问题 ,可以通过相同的方式进行

    参考来源

    - 位置:《Hello 算法--Go版本》第12章《分治》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[17862,17972)) - 结论依据:实际三段顺序与dfsHanota调用参数/基本情况,纠正子任务无依赖及输出口径。 - 原始内容:按照以下顺序解决这三个子问题。 1. 将 −1 个圆盘借助C A 移至 B 2. 将剩余 个圆盘从A 直接移至 C 3. 将 −1) (1) (1) 个圆盘借助A B 移至 C 对于这两个子问题 ,可以通过相同的方式进行