分治算法——汉诺塔问题

Java实现分治算法的汉诺塔问题

package edu.zcc.divideandconquer;

/**
 * 汉诺塔问题是一个简单的分治法问题，2个以上高度的汉诺塔都可以看作只有两个盘，最下面一个盘p和最后一个盘上面的所有盘q，
 * 第一步：将q从第一个柱子移动到第二个柱子上
 * 第二步：将p从第一个柱子移动到第三个柱子上
 * 第三步：将q从第二个柱子移动到第三个柱子上
 * 第四步：通过递归迭代获得结果
 */
public class HannoiTower {
    /**
     * 一个简单的汉诺塔
     * @param num  汉诺塔高度
     * @param A    第一个柱子A
     * @param B   第二个柱子B
     * @param C   第三个柱子C
     * @return    需要移动的次数
     */
    public static int hannoiTower(int num,char A,char B ,char C){
        if(num <= 0) return 0;
        if(num ==1) {
            System.out.println("第1个盘从"+A+"移动到"+C);
            return 1;
        }
        int count=0;
        if(num>=2){
            //第一步：把上面的所有盘移动到B
            count=count+hannoiTower(num-1,A,C,B);
            //第二步：把最下面的盘移动到C
            System.out.println("第"+num+"个盘从"+A+"移动到"+C);
            count++;
            //第三步：把上面的所有盘移动到C
            count=count+hannoiTower(num-1,B,A,C);
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        System.out.println("请输入塔的高度:");
        int num=scan.nextInt();
        System.out.println("一共需要"+HannoiTower.hannoiTower(num,'A','B','C')+"次移动。");
    }
}