使用递归打印帕斯卡三角形

Question

我正在尝试开发一个使用递归打印出 Pascal 三角形 的程序。这是我的代码：

public class PascalTriangle {
    public static int[] computePT(int k) {
        int[] pt = new int[k + 1];
        if (k == 0) {
            pt[0] = 1;
            return pt;
        } else {
            int[] ppt = computePT(k - 1);
            pt[0] = pt[k] = 1;
            for (int i = 1; i < ppt.length; i++) {
                pt[i] = ppt[i - 1] + ppt[i];
            }
        }
        return pt;
    }
}

public class PascalTriangleDriver {
    public static void main(String args[]) {
        int k = 10;

        int arr[] = PascalTriangle.computePT(k);

        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }
}

代码运行完美，但我的问题是我想修改我的 PascalTriangle 代码（而不是 PascalTriangleDriver 代码），例如，当 k=10 时，它打印输出：

1 9 36 84 126 126 84 36 9 1

而不是：

1 10 45 120 210 252 210 120 45 10 1

Answer 1

您似乎犯了一个偏离 1 的错误。解决这个问题的一个简单方法是编写另一个方法，用 k-1:

调用你的原始方法

// this is your original method, just renamed:
private static int[] computePTImpl(int k) {
    int[] pt = new int[k + 1];
    if (k == 0) {
        pt[0] = 1;
        return pt;
    } else {
        int[] ppt = computePT(k - 1);
        pt[0] = pt[k] = 1;
        for (int i = 1; i < ppt.length; i++) {
            pt[i] = ppt[i - 1] + ppt[i];
        }
    }
    return pt;
}

// you will call this method:
public static int[] computePT(int k) {
    return computePT(k - 1);
}

或者，您实际上可以通过将 ks 替换为 k-1s 来修复您的代码：

public static int[] computePT(int k) {
    int[] pt = new int[k]; // note the change
    if (k == 1) { // note the change
        pt[0] = 1;
        return pt;
    } else {
        int[] ppt = computePT(k - 1);
        pt[0] = pt[k - 1] = 1; // note the change
        for (int i = 1; i < ppt.length; i++) {
            pt[i] = ppt[i - 1] + ppt[i];
        }
    }
    return pt;
}

请注意，我们没有更改递归调用，因为如果我们这样做，我们会说 Pascal 三角形的第 k 行取决于第 k-2 行，这不是真的。

Answer 2

您可以迭代填充二项式系数的数组，如下所示：第一行和第一列用1填充，所有其他元素等于行和列中前一个元素的总和。

T[i][j] = T[i][j-1] + T[i-1][j];

您可以创建两种方法：一种是 returns 一个包含三角形的二维数组，第二种是 returns 该三角形的 base。为了清楚起见，它更有用。

输出：

Triangle:
 1  1  1  1  1  1  1  1  1  1 
 1  2  3  4  5  6  7  8  9 
 1  3  6 10 15 21 28 36 
 1  4 10 20 35 56 84 
 1  5 15 35 70 126 
 1  6 21 56 126 
 1  7 28 84 
 1  8 36 
 1  9 
 1 
Base:
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

代码：

public static void main(String[] args) {
    int n = 10;
    System.out.println("Triangle:");
    int[][] arr = binomialTriangle(n);
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++)
            if (arr[i][j] > 0)
                System.out.printf("%2d ", arr[i][j]);
        System.out.println();
    }

    int[] base = binomial(arr);
    System.out.println("Base:");
    System.out.println(Arrays.toString(base));
}

public static int[][] binomialTriangle(int n) {
    // an array of 'n' rows
    int[][] arr = new int[n][];
    // iterate over the rows of the array
    for (int i = 0; i < n; i++) {
        // a row of 'n-i' elements
        arr[i] = new int[n - i];
        // iterate over the elements of the row
        for (int j = 0; j < n - i; j++) {
            if (i == 0 || j == 0) {
                // elements of the first row
                // and column are equal to one
                arr[i][j] = 1;
            } else {
                // all other elements are the sum of the
                // previous element in the row and column
                arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
            }
        }
    }
    return arr;
}

public static int[] binomial(int[][] arr) {
    int[] base = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        // the last element in the row
        base[i] = arr[i][arr[i].length - 1];
    }
    return base;
}

^{另请参阅：Finding trinomial coefficients using dynamic programming}

使用递归打印帕斯卡三角形

Print Pascal's Triangle using recursion

java

arrays

recursion

pascals-triangle