求解汉诺塔问题

【常见题目】

题目描述：
给定一个由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