分治法求解汉诺塔问题

叁歲伎倆 2023-07-15 09:15 9阅读 0赞

汉诺塔问题简介：  
**汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。**

A             B                C

![在这里插入图片描述][20200316132235900.png]

**思路：**  
\*\*\*1.只有一个盘的时候：直接将盘从A->C;

2.当盘数大于如果n>=2时  
1） 将盘看成两部分，最下面一个盘为下部分，第1到第n-1个盘为上面部分  
2） 将上面部分的盘全部A-B,借助C

3） 然后将最下面那个盘从A->c

4） 最后借助A将B->C

Java代码：

package com.yg.algorithm;/*
    分治算法的代表汉诺塔问题
    */
    
    public class HanoiTowers {
        public static void main(String[] args) {
        hanoiTowers(3,'A','B','C');
        }
    
        public static void hanoiTowers(int num, char a, char b, char c) {
            if (num == 1) {
                System.out.println("第一个盘从" + a + "->" + c);
            } else {
                //如果n>=2时
                //将盘看成两部分，最下面一个盘为下部分，第1到第n-1个盘为上面部分
                //将上面部分的盘全部A-B,借助C
                hanoiTowers(num - 1, a, c, b);
                //然后将最下面那个盘从A->c
                System.out.println("第"+num+"个盘从" + a + "->" + c);
                //最后借助A将B->C
                hanoiTowers(num - 1, b, a, c);
            }
        }
    }

[20200316132235900.png]: /images/20230528/1345642948954d92968df22770926e30.png

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关分治法求解汉诺塔问题

汉诺塔问题简介：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵

叁歲伎倆/ 2023年07月15日 09:15/ 0 赞/ 10 阅读

相关图解汉诺塔问题（递归求解）

> 汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按

我会带着你远行/ 2022年11月30日 12:47/ 0 赞/ 283 阅读

相关汉诺塔问题的递归求解

汉诺塔问题的递归求解汉诺塔解题思路具体实现汉诺塔汉诺塔汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说

系统管理员/ 2022年11月05日 08:46/ 0 赞/ 174 阅读

相关汉诺塔问题求解

汉诺塔问题的描述如下：有3根柱子A、B和C，在A上从下往上按照从小到大的顺序放着64个圆盘，以B为中介，把盘子全部移动到C上。移动过程中，要求任意盘子的下面要么没有盘子，要

本是古典何须时尚/ 2022年09月29日 14:55/ 0 赞/ 114 阅读

相关求解汉诺塔问题

汉诺塔是经典问题。具体表述为：由很多放置在三个塔座上的盘子组成的一个古老难题，所有盘子直径都是不同的，盘子中央都有一个洞使他们刚好可以放在塔座上。所有的盘子刚开始放在塔座A上

你的名字/ 2022年09月25日 12:14/ 0 赞/ 116 阅读

相关汉诺塔问题

1.汉诺塔问题：如果将n个盘子（由小到大）从a通过b，搬到c，搬运过程中不能出现小盘子在大盘子下面的情况。分析：这个一个递归问题。只要将n-1个盘子从a通过c（没有中间点肯

刺骨的言语ヽ痛彻心扉/ 2022年08月20日 10:14/ 0 赞/ 215 阅读

相关 Java递归求解汉诺塔问题

汉诺塔问题 ![Center][] 规则： 1.每次只能移动一个圆盘。 2.圆盘可以插在X,Y,Z中的任一塔座上。 3.任何时刻都不能让一个大的圆盘落

ゝ一世哀愁。/ 2022年07月12日 10:52/ 0 赞/ 194 阅读

相关汉诺塔问题

汉诺塔比较经典的实现是利用递归，但也可以利用堆栈。题意理解：有A,B,C三个柱子，将A柱子上的N个盘子（从大到小排列）移到C柱子上，每次只允许移动一个盘子，并且保证每个柱子

た入场券/ 2022年05月26日 12:14/ 0 赞/ 161 阅读

相关汉诺塔问题求解

汉诺塔问题的描述如下：有3根柱子A、B和C，在A上从下往上按照从小到大的顺序放着64个圆盘，以B为中介，把盘子全部移动到C上。移动过程中，要求任意盘子的下面要么没有盘子，要么只

r囧r小猫/ 2022年04月08日 09:20/ 0 赞/ 382 阅读

相关汉诺塔问题

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新

梦里梦外;/ 2021年09月28日 17:06/ 0 赞/ 455 阅读