数据结构-递归（三）

多路递归

汉诺塔：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * @param n 圆盘个数
 * @param a 起始柱子
 * @param b 中间柱子
 * @param c 目标柱子
 */
static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {
    //如果 0 就中止返回
    if (n == 0) return;
    //把除了最后一个圆盘，通过c柱子移动到b柱子
    move(n - 1, a, c, b);
    //把a最后一个圆盘移动到c;
    c.addLast(a.removeLast());//中间
    //把除了最后一个圆盘，通过a柱子移动到c柱子
    move(n - 1, b, a, c);
}

杨辉三角：

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

//生成当前坐标的值
private static int element(int i, int j) {
    if (j == 0 || i == j) return 1;
    return element(i - 1, j - 1) + element(i - 1, j);
}
//生成空格，用于居中
private static void printSpace(int n, int a) {
    for (int i = 0; i < (n - 1 - a) * 2; i++) {
        System.out.print(" ");
    }
}
//创建杨辉三角
private static void create(int n) {
    for (int i = 0; i < n; i++) {
        printSpace(n,i);
        for (int j = 0; j <= i; j++) {
            System.out.printf("%-4d", element(i, j));
        }
        System.out.println();
    }
}

• 如此调用过于繁琐，因此我们可以舍弃递归（？），使用数组单独记忆上一排的数据从而计算

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  private static void create(int n) { //创建记忆数组 int[] triangle = new int[n]; for (int i = 0; i < n; i++) { //创建临时数组 int[] temp = new int[n]; printSpace(n, i); for (int j = 0; j <= i; j++) { //使用记忆数组进行计算 temp[j] = (j == 0 || i == j) ? 1 : triangle[j - 1] + triangle[j]; System.out.printf("%-4d", temp[j]); } //计算完成后将当前行进行记忆，用于下一次计算 triangle = temp; System.out.println(); } }

• 当前，杨辉三角是可以通过每行前一项计算出下一项的，暂不展开