Почему мой треугольный код Паскаля не работает?

Я пытался написать треугольник Паскаля, используя формулу комбинации, но она просто не работает должным образом, и я не уверен, в чем проблема?

Вот ввод:

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

Можете ли вы объяснить мне, почему в удобной для начинающих форме?


java recursion algorithm pascals-triangle
person Mehmet Erdem    schedule 22.12.2019    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вам нужно добавить круглые скобки вокруг операций в 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));
person filbranden    schedule 22.12.2019

arrow_upward
0
arrow_downward

Проверьте свою формулу для получения факториала. Так должно быть:

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

При использовании потоков ваш код может выглядеть примерно так:

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

См. также: Как мне превратить это в треугольник Паскаля вместо прямоугольного треугольника?

person Community    schedule 15.02.2021