帕斯卡三角错误输出

Question

您好，我正在 Java 中制作一个迭代帕斯卡三角形。到目前为止一切正常，直到行数超过 13。输出出现错误。我一定是哪里做错了，请大家帮忙

IterativePascal:

public class IterativePascal extends ErrorPascal implements Pascal {
    private int n;
    IterativePascal(int n) throws Exception {
        super(n);
        this.n = n;
    }
    public void printPascal() {
        printPascal(false);
    }

    public void printPascal(boolean upsideDown) {
        if (n == 0) { return; }
        for (int j = 0; j <= n; j++) {
            for (int i = 0; i < j; i++) {
                System.out.print(binom(j - 1, i) + (j == i + 1 ? "\n" : " "));
            }
        }
    }

    public long binom(int n, int k) {
        return (k == 0 || n == k) ? 1 : faculty(n) / (faculty(k) * faculty(n - k));
    }

    private long faculty(int n) {
        if (n == 0 || n == 1) { return 1; }
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
}

输出：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 4 24 88 221 399 532 532 399 221 88 24 4 1 <----- wrong
1 0 1 5 14 29 44 50 44 29 14 5 1 0 1 <----- wrong

非常感谢您的帮助，因为我是算法方面的新手。

Answer 1

您的号码即将溢出。因为14!太大填不进去javalong.

解决方案是使用 + 而不是 !。

将三角形保存为二维数组并遍历它。每个单元格应该是两个 'above'.

的总和

+---+---+---+---+
| 1 |   |   |   |
| 1 | 1 |   |   |
| 1 | 2 | 1 |   |
| 1 | 3 | 3 | 1 |
+---+---+---+---+

代码如下：

public static void triangle(int n) {
    int[][] triangle = new int[n];
    for (int i = 0; i < n; i++) {
        triangle[i] = new int[i+1];
    }
    triangle[0][0] = 1;
    triangle[1][0] = 1;
    triangle[1][1] = 1;
    for (int i = 2; i < n; i++) {
        triangle[i][0] = 1;
        for (int j = 1; j < triangle[i].length - 1; j++) {
            triangle[i][j] = triangle[i-1][j] + triangle[i-1][j+1];
        }
        triangle[i][triangle[i].length-1] = 1;
    }
    printArray(triangle);
}

编辑：
由于 OP 需要使用二项式递归解决方案，因此我决定添加引入 BigIntegers 的解决方案，因为它可能是这种情况。

public BigInteger binom(int n, int k) {
        return (k == 0 || n == k) ? BigInteger.ONE : faculty(n).divide((faculty(k).multiple(faculty(n - k)));
    }

private BigInteger faculty(int n) {
    BigInteger result = BigInteger.ONE;
    while (!n.equals(BigInteger.ZERO)) {
        result = result.multiply(n);
        n = n.subtract(BigInteger.ONE);
    }
    return result;
}

public void printPascal(boolean upsideDown) {
    if (n == 0) { return; }
    for (int j = 0; j <= n; j++) {
        for (int i = 0; i < j; i++) {
            System.out.print(binom(j - 1, i).toString() + (j == i + 1 ? "\n" : " "));
        }
    }
}

Answer 2

问题可能出在您对阶乘的计算上：我假设您的 int 类型可以容纳最多 32 位的数字，但是 13 位！比那个大。

您可以检查long是否可以存储更大的数字并将结果定义为long。

帕斯卡三角错误输出

Pascal's triangle faulty output

java

arrays

algorithm

pascals-triangle