为什么我的 Pascal 三角代码不起作用？

Question

我一直在尝试使用组合公式来编写帕斯卡三角形，但它无法正常工作，我不确定问题出在哪里？

这是输入：

public class Probs {
    public static int fact(int n) {
        int f;
        for (f = 1; n > 1; n--) {
            f *= n;
        }
        return f;
    }

    public static int comb(int i, int j) {
        return fact(i) / fact(i - j) * fact(j);
    }

    public static void main(String[] args) {
        int n = 5;
        int i;
        int j;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n - i; j++) {
                System.out.print(" ");
            }
            for (j = 0; j <= i; j++) {
                System.out.print(" " + comb(i, j));
            }
            System.out.println();
        }
    }
}

输出：

    1
   1 1
  1 2 4
 1 3 12 36
1 4 24 144 576

你能以一种对初学者友好的方式向我解释为什么吗？

Answer 1

您需要在 comb() 中的操作周围添加括号以获得正确的优先级。

/和*的优先级相同，所以当你写

return fact(i)/ fact(i-j)*fact(j);

这个表达式实际上等同于

return (fact(i)/fact(i-j)) * fact(j);

这不是你真正想要的...

通过在分母中的乘积周围添加括号来修复它：

return fact(i) / (fact(i-j)*fact(j));

Answer 2

检查你的阶乘公式。应该是：

factorial(i) / (factorial(i - j) * factorial(j))

使用 streams，您的代码可能如下所示：

public static int factorial(int n) {
    return IntStream.rangeClosed(2, n).reduce((a, b) -> a * b).orElse(1);
}

public static int[][] pascalsTriangle(int n) {
    return IntStream.range(0, n)
            .mapToObj(i -> IntStream.range(0, i + 1)
                    .map(j -> factorial(i) / (factorial(i - j) * factorial(j)))
                    .toArray())
            .toArray(int[][]::new);
}

public static void main(String[] args) {
    int n = 10;
    int[][] arr = pascalsTriangle(n);
    pyramidOutput(arr);
}

public static void pyramidOutput(int[][] arr) {
    String[] output = Arrays.stream(arr)
            .map(row -> Arrays.stream(row).mapToObj(String::valueOf)
                    .collect(Collectors.joining("  ")))
            .toArray(String[]::new);

    int max = Arrays.stream(output)
            .max(Comparator.comparing(String::length))
            .orElse("").length();

    Arrays.stream(output)
            .map(row -> " ".repeat((max - row.length()) / 2) + row)
            .forEach(System.out::println);
}

输出：

                 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

^{另请参阅：How do I make this into a Pascal's triangle instead of a Right triangle?}

为什么我的 Pascal 三角代码不起作用？

Why my Pascal's triangle code doesn't work?

java

algorithm

recursion

pascals-triangle