汉诺塔问题

x33g5p2x  于2022-02-14 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(168)

汉诺塔问题的由来

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

思路分析

如果圆盘的数量只有一个就直接将圆盘从初始柱移动到目标柱

圆盘数量为2时将小的圆盘移动到辅助柱然后将大圆盘移动到目标柱

若有n个圆盘 我们可以把这n个圆盘看作是2个盘 ——最下面的盘和上面所有的盘
(1)将上面的n-1个盘移动到B柱(此时A柱为初始柱,B柱为目标柱,C柱为辅助柱)
(2)将最下面的圆盘移动到目标柱(此时A柱为初始柱,C柱为目标柱,B柱为辅助柱)
(3)把辅助柱上的所有盘移动到目标盘(此时B柱为初始柱,C柱为目标柱,A柱为辅助柱)

public class HanoiTower {

    public static void main(String[] args) {
        hanoiTower(4,'A','B','C');
    }

    /**
     *
     * @param num 圆盘的数量
     * @param a 起始柱
     * @param b 辅助柱
     * @param c 目标柱
     */
    public static void hanoiTower(int num,char a,char b,char c){
        /*如果只有一个圆盘就可以直接将圆盘从a柱移动到c柱*/
        if (num == 1){
            System.out.println("第1个圆盘从 " + a + "->" + c);
        }else{
            /*圆盘的数量大于1*/
            /*先把上面的所有盘移动到从A移动到B柱 C柱作为辅助柱*/
            hanoiTower(num-1,a,c,b);
            /*将最下面的盘移动到C柱*/
            System.out.println("第"+num+"个圆盘从 " + a + "->" + c);
            /*把B柱上的圆盘移动到C柱 A柱为辅助柱*/
            hanoiTower(num-1,b,a,c);
        }
    }
}

运行结果

第1个圆盘从 A->B
第2个圆盘从 A->C
第1个圆盘从 B->C
第3个圆盘从 A->B
第1个圆盘从 C->A
第2个圆盘从 C->B
第1个圆盘从 A->B
第4个圆盘从 A->C
第1个圆盘从 B->C
第2个圆盘从 B->A
第1个圆盘从 C->A
第3个圆盘从 B->C
第1个圆盘从 A->B
第2个圆盘从 A->C
第1个圆盘从 B->C

Process finished with exit code 0

相关文章

微信公众号

最新文章

更多