Solving Hanoi Tower problem

Solving the tower of Hanoi problem

【 Common topics 】

Title Description ：
Given a by n A tower of disks , These disks are sleeved on the first column in a decreasing way . Now move the whole tower to the third column , Only one disc can be moved at a time , And the larger disc cannot be placed on the smaller disc during movement .
Input ：
Enter only one positive integer n
Output ：
Next, each line outputs one move step .

Here it is , We discuss a simple and well understood approach —— Recursive approach , Since recursion , We just have to think about recursive functions , Let's leave the rest to the function .

【 Code 】

package pers.keafmd.accumulate.codeinterviewguide.hanoi;import java.util.ArrayList;import java.util.List;/** * Keafmd * * @ClassName: ClassicTowerOfHanoi * @Description:  Classic Hanoi Tower  * @author:  Cowherd Conan  * @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(" The first "+step+++" Step , hold "+a.get(0)+" Number from "+a+" Move to "+c);            c.add(a.remove(a.size()-1));            return;        }        //  first  a It's full , All the dishes are here a On ,b It's empty. ,c It's empty.         // Three step strategy ：        // First step ： hold a above n-1 A plate from a With the help of c Move to b On         move(n-1,a,c,b);        System.out.println("a:"+a+",b:"+b+",c:"+c);        System.out.println(" The first "+step+++" Step , hold "+a.get(a.size()-1)+" Number from "+a+" Move to "+c);        // The second step ： hold a The bottom plate on the top is from a Move to c        c.add(a.remove(a.size()-1));        // The third step ： hold b above n-1 With the help of a Move to c On         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);    }}

The test results ：

a:[1, 2, 3, 4],b:[],c:[] The first 1 Step , hold 1 Number from [1, 2, 3, 4] Move to []a:[1, 2, 3],b:[4],c:[] The first 2 Step , hold 3 Number from [1, 2, 3] Move to []a:[4],b:[1, 2],c:[3] The first 3 Step , hold 4 Number from [4] Move to [3]a:[1, 2],b:[3, 4],c:[] The first 4 Step , hold 2 Number from [1, 2] Move to []a:[3, 4],b:[2],c:[1] The first 5 Step , hold 3 Number from [3, 4] Move to [1]a:[3],b:[1, 4],c:[2] The first 6 Step , hold 3 Number from [3] Move to [2]a:[1, 4],b:[],c:[2, 3] The first 7 Step , hold 1 Number from [1, 4] Move to [2, 3]a:[1],b:[2, 3, 4],c:[] The first 8 Step , hold 1 Number from [1] Move to []a:[2, 3, 4],b:[],c:[1] The first 9 Step , hold 2 Number from [2, 3, 4] Move to [1]a:[2, 3],b:[1, 4],c:[] The first 10 Step , hold 3 Number from [2, 3] Move to []a:[1, 4],b:[2],c:[3] The first 11 Step , hold 1 Number from [1, 4] Move to [3]a:[2],b:[3, 4],c:[1] The first 12 Step , hold 2 Number from [2] Move to [1]a:[3, 4],b:[1, 2],c:[] The first 13 Step , hold 3 Number from [3, 4] Move to []a:[3],b:[4],c:[1, 2] The first 14 Step , hold 3 Number from [3] Move to [1, 2]a:[4],b:[],c:[1, 2, 3] The first 15 Step , hold 4 Number from [4] Move to [1, 2, 3]Process finished with exit code 0