二项式系数数组

Question

所以，我实现了二项式系数

public static int binomial(int n, int k) {
    if (k == 0)
        return 1;
    else if (k > n - k)
        return binomial(n, n - k);
    else
        return binomial(n - 1, k - 1) * n / k;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);

    System.out.println("Insert n: ");
    int n = scan.nextInt();

    System.out.println("Insert k: ");
    int k = scan.nextInt();

    System.out.println("Result: " + binomial(n, k));
}

它有效，但我被卡住的地方只是我需要为两个给定的数字添加 系数数组 。所以如果 n 是 5 并且 k 是 3。系数数组将显示：1 5 10 10。有什么想法吗？

Answer 1

不要在 for 循环中调用递归代码。这增加了愚蠢的冗余。

将数组作为参数传递给 main 中的递归函数。数组在 java.

中通过引用传递

public static int binomial(int n, int k, int[] coefficient) {
    int ret;
    if (k == 0) {
        ret = 1;
    } else if (k > n - k) {
        ret = binomial(n, n - k, coefficient);
    } else {
        ret = binomial(n - 1, k - 1, coefficient) * n / k;
    }
    coefficient[k] = ret;
    return ret;
}

Answer 2

您需要做的就是将表达式放入循环中并保持 n 不变。

for (int k = 0; k <= n; k++) {
    System.out.print(binomial(n, k) + " ");
}

如果您愿意，可以将这些值存储在一个数组中。无需让您的方法变得更复杂。

如果想把它放在数组中，这里有一种简单的方法。

int coefs[] = IntStream.rangeClosed(0, n).map(k -> binomial(n, k)).toArray();

coefs[] = [1, 5, 10, 10, 5, 1]

Answer 3

您可以创建两种迭代方法：一种returns包含帕斯卡三角形的二维数组，第二种returns 该三角形的 base。它对清晰度更有用。

输出：

Insert n:
6
Pascal's triangle:
[1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5]
[1, 3, 6, 10]
[1, 4, 10]
[1, 5]
[1]
Binomial coefficients:
[1, 5, 10, 10, 5, 1]

代码：

public static int[][] binomialTriangle(int n) {
    // an array of 'n' rows
    int[][] arr = new int[n][];
    // iterate over the rows of the array
    IntStream.range(0, n).forEach(i -> {
        // a row of 'n-i' elements
        arr[i] = new int[n - i];
        // iterate over the columns of the array
        IntStream.range(0, n - i).forEach(j -> {
            if (i == 0 || j == 0)
                // first row and column
                // are filled with ones
                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[] binomialCoefficient(int[][] triangle) {
    return Arrays.stream(triangle)
            // the last element in the row
            .mapToInt(row -> row[row.length - 1])
            .toArray();
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.println("Insert n:");
    int n = scan.nextInt();

    System.out.println("Pascal's triangle:");
    int[][] arr = binomialTriangle(n);
    Arrays.stream(arr).map(Arrays::toString).forEach(System.out::println);

    int[] base = binomialCoefficient(arr);
    System.out.println("Binomial coefficients:");
    System.out.println(Arrays.toString(base));
}

^{另请参阅：}

二项式系数数组

Array of binomial coefficients

java

arrays

binomial-coefficients

pascals-triangle