如何利用分治算法解决 ‘叠罗汉’ 问题,也叫作汉诺塔问题

分享 leeston9 ⋅ 于 2020-07-02 15:03:49 ⋅ 最后回复由 青牛 2020-07-02 15:06:44 ⋅ 1415 阅读

问题: 将A塔的所有盘子移动到C塔,期间可借助B塔,但一直要保证大盘下,小盘上
file
使用java写了分治算法,化大为小,分而治之,加上递归,便可轻松解决这个问题!

 static int step = 0;

    public static void main(String[] args) {
        System.out.println("默认所有盘子在 A 塔,从上到下编号依次为1~8");
        System.out.println("------------------------------------");
        hanoiTower(8, 'A', 'B', 'C');
        System.out.println("-------------------------");
        System.out.println("一共需要走: " + step + " 步");
    }

    /**
     * @param num 盘子数
     * @param A   放在 a 盘的塔
     * @param B   放在 b 盘的塔
     * @param C   放在 c 盘的塔
     */
    public static void hanoiTower(int num, char A, char B, char C) {
        //只有一个盘时直接: A -> C
        if (num == 1) {
            System.out.println("第" + (++step) + "步:将编号为 1 的盘从 " + A + " 移动到 " + C);
        } else {
            // 上面所有盘先 A -> B,递归时借助 C
            hanoiTower(num - 1, A, C, B);
            // 然后最下面的盘移动到 C
            System.out.println("第" + (++step) + "步:将编号为 " + num + " 的盘从 " + A + " 移动到 " + C);
            //最后把 B -> C ,中间借助 A
            hanoiTower(num - 1, B, A, C);
        }
    }

其中的代码逻辑注释中基本已经很清晰,当盘子数为8时,递归调用的逻辑如下结果所示:
file
file
PS:如有疑问,请联系21班李军

版权声明:原创作品,允许转载,转载时务必以超链接的形式表明出处和作者信息。否则将追究法律责任。来自海牛部落-leeston9,http://hainiubl.com/topics/75176
回复数量: 1
  • 青牛 国内首批大数据从业者,就职于金山,担任大数据团队核心研发工程师
    2020-07-02 15:06:44

    开始研究算法了,看样子想进大厂了

暂无评论~~
  • 请注意单词拼写,以及中英文排版,参考此页
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`, 更多语法请见这里 Markdown 语法
  • 支持表情,可用Emoji的自动补全, 在输入的时候只需要 ":" 就可以自动提示了 :metal: :point_right: 表情列表 :star: :sparkles:
  • 上传图片, 支持拖拽和剪切板黏贴上传, 格式限制 - jpg, png, gif,教程
  • 发布框支持本地存储功能,会在内容变更时保存,「提交」按钮点击时清空
Ctrl+Enter