递归经典题目--汉诺塔问题

汉诺塔背景

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

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

汉诺塔思路

首先，假设只有一个盘子，那么直接从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();
        }
    }
复制代码

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