解决汉罗塔问题

解决思路

参考图

1. 把A上面的圆盘看做两部分,由下往上 n 和 n-1 ；n必须大于等于2
1. 移动 A上面的n-1 部分移动到B,A上面的最大圆盘 n 移动到 C，B上面的n-1部分移动 C
1. 移动后的结果 A(n-1) -> B, A -> C, B(n-1) -> C

套用上面的结果来分析
当n=1时；A -> C
当n=2时；A -> B , A -> C ，B -> C
当n=3时；A(2) -> B, A -> C，B(2) -> C

A(2) -> B : 这里有转换成了新的模型
A杆上面有两个圆盘，借助C杆需要移动到B杆上去，图形如下：

image.png

移动的结果：A->C , A->B , C->B
B(2) -> C: 同理可以得到新模型

image.png

移动的结果： B->A , B->C，A->C

最后组合起来，当n=3时；移动结果为 A->C , A->B , C->B， A -> C，B->A , B->C，A->C

通过上面的的分析，可以采用递归的方式，forkjoin 来求解

/**
 * 递归解决汉罗塔
 */
public class DiGui {

    /**
     * @param n  有多少个圆盘
     * @param p1 源桩
     * @param p2 辅助桩
     * @param p3 目标桩
     */
    public static void solve(int n, String p1, String p2, String p3) {
        if (n == 1) {
            System.out.println(p1 + " => " + p3);
            return;
        }
        solve(n - 1, p1, p3, p2);
        System.out.println(p1 + " => " + p3);
        solve(n - 1, p2, p1, p3);

    }

    public static void main(String[] args) {
        solve(3, "A", "B", "C");
    }

}

/**
* Fork-Join 的方式来完成
*/
public class ForkJoinWay {

    public static class Worker extends RecursiveTask<String> {
        private int n;
        private String p1;
        private String p2;
        private String p3;

        public Worker(int n, String p1, String p2, String p3) {
            this.n = n;
            this.p1 = p1;
            this.p2 = p2;
            this.p3 = p3;
        }

        @Override
        protected String compute() {
            if (n == 1) {
                return p1 + " => " + p3;
            }
            Worker worker1 = new Worker(n - 1, p1, p3, p2);
            Worker worker2 = new Worker(n - 1, p2, p1, p3);
            invokeAll(worker1, worker2);
            return worker1.join() + "\n" + p1 + " => " + p3 + "\n" + worker2.join() + "\n";
        }
    }

    public static void main(String[] args) {
        ForkJoinPool pool = new ForkJoinPool();
        Worker task = new Worker(3, "A", "B", "C");
        pool.invoke(task);
        System.out.println(task.join());
    }

}