求解汉诺塔问题

【常见题目】

题目描述：
给定一个由n个圆盘组成的塔，这些圆盘按照大小递减的方式套在第一根柱上。现要将整个塔移动到第三根柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面。
输入：
输入只有一个正整数n
输出：
接下来每一行输出一步移动步骤。

在此，我们讨论比较一种简单而且很好理解的做法——递归做法，既然递归，我们只要想好递归函数，其它的就交给函数吧。

【代码】

package pers.keafmd.accumulate.codeinterviewguide.hanoi;

import java.util.ArrayList;
import java.util.List;

/**
 * Keafmd
 *
 * @ClassName: ClassicTowerOfHanoi
 * @Description: 经典汉诺塔
 * @author: 牛哄哄的柯南
 * @date: 2022-06-27 19:08
 */
public class ClassicTowerOfHanoi {
    public int step = 1;

    public void hanoi(List<Integer> a,List<Integer> b,List<Integer> c){
        int n = a.size();
        move(n,a,b,c);
    }

    public void move(int n,List<Integer> a,List<Integer> b,List<Integer> c){
        if(n == 1){
            System.out.println("a:"+a+",b:"+b+",c:"+c);
            System.out.println("第"+step+++"步，把"+a.get(0)+"号从"+a+"移动到"+c);
            c.add(a.remove(a.size()-1));
            return;
        }
        // 最初 a是满的,所有盘子都在a上,b是空的,c是空的

        //三步走战略：
        //第一步：把a上面的n-1个盘子从a借助c移动到b上
        move(n-1,a,c,b);
        System.out.println("a:"+a+",b:"+b+",c:"+c);
        System.out.println("第"+step+++"步，把"+a.get(a.size()-1)+"号从"+a+"移动到"+c);
        //第二步：把a上面的最下面的那个盘子从a移动到c
        c.add(a.remove(a.size()-1));
        //第三步：把b上面的n-1个盘子借助a移动到c上
        move(n-1,b,a,c);
    }

    public static void main(String[] args) {
        List<Integer> aList = new ArrayList<>();
        List<Integer> bList = new ArrayList<>();
        List<Integer> cList = new ArrayList<>();

        aList.add(1);
        aList.add(2);
        aList.add(3);
        aList.add(4);
//        A.add(5);
//        A.add(6);

        ClassicTowerOfHanoi classicTowerOfHanoi = new ClassicTowerOfHanoi();
        classicTowerOfHanoi.hanoi(aList,bList,cList);

    }



}

测试效果：

a:[1, 2, 3, 4],b:[],c:[]
第1步，把1号从[1, 2, 3, 4]移动到[]
a:[1, 2, 3],b:[4],c:[]
第2步，把3号从[1, 2, 3]移动到[]
a:[4],b:[1, 2],c:[3]
第3步，把4号从[4]移动到[3]
a:[1, 2],b:[3, 4],c:[]
第4步，把2号从[1, 2]移动到[]
a:[3, 4],b:[2],c:[1]
第5步，把3号从[3, 4]移动到[1]
a:[3],b:[1, 4],c:[2]
第6步，把3号从[3]移动到[2]
a:[1, 4],b:[],c:[2, 3]
第7步，把1号从[1, 4]移动到[2, 3]
a:[1],b:[2, 3, 4],c:[]
第8步，把1号从[1]移动到[]
a:[2, 3, 4],b:[],c:[1]
第9步，把2号从[2, 3, 4]移动到[1]
a:[2, 3],b:[1, 4],c:[]
第10步，把3号从[2, 3]移动到[]
a:[1, 4],b:[2],c:[3]
第11步，把1号从[1, 4]移动到[3]
a:[2],b:[3, 4],c:[1]
第12步，把2号从[2]移动到[1]
a:[3, 4],b:[1, 2],c:[]
第13步，把3号从[3, 4]移动到[]
a:[3],b:[4],c:[1, 2]
第14步，把3号从[3]移动到[1, 2]
a:[4],b:[],c:[1, 2, 3]
第15步，把4号从[4]移动到[1, 2, 3]

Process finished with exit code 0