汉诺塔问题

汉诺塔问题

​ 汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

注意：

​ 1、每次只能移动一个盘子

​ 2、移动过程中，三个座上的盘子始终保持大盘在下，小盘在上。

​ 我们可以将最上边的63个盘子当作一个整体，这样可以看作是只有两个盘子，那么此时就是先将63个盘子这个整体移动到B盘，第64盘子移动到C盘，再将那63个盘子为整体的移动到C盘即可；

​ 【1-63】=> A -> B 【64】=> A ->C 【1-63】=> B -> C

​ 那么这63个盘子怎么移动到B盘呢，还是同样的思想，将前62个盘子看做一个整体，第63个盘子是一个盘子，此时又可以当作只有两个盘子，所以此时移动过程就是将62个盘子为整体的盘子移动到C盘，然后将第63个盘子移动到B盘，再将62个盘子为整体的盘子移动到B盘；

​ 【1-62】=> A -> C 【63】=> A->B 【1-62】=> C -> B

​ 按照这种思路，一步一步递归分解即可。可以得出的核心代码如下：

    move(n-1,source,dest,temp);
    resList.add("move from "+source+" to "+dest);
    move(n-1,temp,source,dest);

牛客题目

​ 我们有从大到小放置的n个圆盘，开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，请实现一个函数打印最优移动轨迹。

​ 给定一个int n，表示有n个圆盘。请返回一个string数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。

private ArrayList<String> resList;
public ArrayList<String> getSolution(int n) {
    // write code here

     resList = new ArrayList<>();
    if (n == 0){
        return resList;
    }

    if (n == 1){
        resList.add("move from left to right");
        return resList;
    }

    move(n,"left","mid","right");
    return resList;
}

private void move(int n,String source,String temp,String dest){


    if (n == 1){

        resList.add("move from "+source+" to "+dest);
    }else {

        move(n-1,source,dest,temp);
        resList.add("move from "+source+" to "+dest);
        move(n-1,temp,source,dest);
    }
}