1. 递归处理汉罗塔问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Hanota {

    /**
     * 汉罗塔问题
     */

    static void dfs(int n, List<Integer> src, List<Integer> buf, List<Integer> tar){
        if (n == 1){
            move(src, tar);
        }
        // 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
        dfs(n - 1, src, tar, buf);
        // 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
        move(src, tar);
        // 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
        dfs(n - 1, buf, src, tar);;
    }

    static void move(List<Integer> src, List<Integer> tar){
        src.remove(src.size() -1);
        tar.addAll(src);
    }
}