汉诺塔问题

汉诺塔背景
在印度有这样一个古老的传说，相传大梵天在创造世界的时候，做了三根金刚石柱，在其中一根柱子上从上而下叠着64片黄金圆盘，于是大梵天就要求婆罗门按圆盘的大小重新摆在另外一根柱子上

要求：一次只能移动一根柱子，并且在移动的过程中，也要保持大盘在小盘的下面

image-20220423122213504

汉诺塔思路
首先，假设只有一个盘子，那么直接从A到C即可

当有两个盘子的时候就将上面的较小的盘子先挪到B，再将较大的盘子挪到C上，最后将B

上的较小的盘子放到C上即可

那么，当有3个及以上盘子的时候，就应该有一种整体递归的思维，递归的核心就是大事化小，总结出重复的步骤，找出规律

由于要保证最后大盘子要在小盘子的下面，所以可以将所有盘子看做两个部分，分为最下面最大的盘子和上面剩下的盘子这两部分，可以先将剩下的盘子这个整体从A经过C的中转，再放到B上面。接着再处理最大的盘子，直接放到C，最后再处理剩下的盘子这个整体，可以将他们从B先放到A上中转，再放到C即可

/**

• hanoi中参数解释：
• pos1是指盘子的起始位置
• pos2是指盘子的中转位置
• pos3是指盘子的终点位置

*/

public static void move(char pos1, char pos2) {  //进行打印移动的过程
    System.out.print(pos1 + "->" + pos2 + " ");
}

public static void hanoi(int n, char pos1, char pos2, char pos3) {
    if (n == 1) {
        move(pos1, pos2);//当盘子为1的时候直接从A移到C
    } else {
        hanoi(n - 1, pos1, pos3, pos2);
        move(pos1, pos3);
        hanoi(n - 1, pos2, pos1, pos3);
    }
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNext()) {
        int n = scanner.nextInt();
        hanoi(n, 'A', 'B', 'C');
        System.out.println();
    }
}

复制代码
以上就是关于汉诺塔问题的求解,主要就要理解其中的递归实现 最后,欢迎大家点赞收藏关注，感谢大家的支持！