解决思路
参考图
- 把A上面的圆盘看做两部分,由下往上 n 和 n-1 ；n必须大于等于2
- 移动 A上面的n-1 部分移动到B,A上面的 最大圆盘 n 移动到 C，B上面的n-1部分移动 C
- 移动后的结果 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());
}
}
