用于 Java 的 Pascal 三角形的递归方法

Recursive method for Pascal's Triangle for Java

提问by user2932450

I have written a method to evaluate a Pascal Triangle of n rows. However when I test the method I receive the error "Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1". Here is the code.

我写了一个方法来评估 n 行的帕斯卡三角形。但是，当我测试该方法时，我收到错误“线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException: -1”。这是代码。

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

Please let me know if you have any ideas for how the code could be edited to fix the problem.

如果您对如何编辑代码以解决问题有任何想法，请告诉我。

回答by Karthik T

for(int i = 0; i < ppt.length; i++)
    {
        pt[i] = ppt[i-1] + ppt[i];

In your first iteration, i == 0and so (i-1) == -1. This is the cause of the error.

在您的第一次迭代中，i == 0等等(i-1) == -1。这就是错误的原因。

You can special handle the boundaries to avoid this. Or as the others have suggested, start iat 1 instead of 0.

您可以特殊处理边界以避免这种情况。或者像其他人建议的那样，从i1 而不是 0 开始。

回答by ajb

In this code:

在这段代码中：

pt[0] = pt[n] = 1;
for(int i = 0; i < ppt.length; i++)
{
    pt[i] = ppt[i-1] + ppt[i];
}

the problem is that when iis 0, you're trying to access ppt[i-1]which is ppt[-1]. The thing to notice is that when iis 0, you don't need to execute the statement that sets pt[i], because you already set pt[0]up before the loop! Try initializing ito 1 instead of 0.

问题是当i是 0 时，您试图访问ppt[i-1]哪个是ppt[-1]. 需要注意的是wheni为0，不需要执行set的语句pt[i]，因为pt[0]在循环之前你已经设置好了！尝试初始化i为 1 而不是 0。

回答by Clemson

Here is some code a friend of mine came up with

这是我的一个朋友想出的一些代码

import java.util.Scanner;
public class Pascal {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter the number of rows to print: ");
    int rows = scanner.nextInt();
    System.out.println("Pascal Triangle:");
    print(rows);
    scanner.close();
  }

  public static void print(int n) {
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < n - i; k++) {
        System.out.print(" "); // print space for triangle like structure
      }
      for (int j = 0; j <= i; j++) {
        System.out.print(pascal(i, j) + " ");
      }
      System.out.println();
    }
  }

  public static int pascal(int i, int j) {
    if (j == 0 || j == i) {
      return 1;
    } else {
      return pascal(i - 1, j - 1) + pascal(i - 1, j);
    }
  }
}

Happy recursing!

快乐回归！

回答by NeeK

Improvement in @Clemson code using Dynamic Programming :

使用动态编程改进@Clemson 代码：

class Solution {
    int[][] dp ; 
    public List<List<Integer>> generate(int numRows) {
        dp = new int[numRows][numRows];

        List<List<Integer>> results = new ArrayList<>();
        pascal(results, numRows);

        return results;
    }

    private void pascal(List<List<Integer>> results, int numRows) {
        for(int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j <= i ; j++) {
                list.add(dfs(i, j));
            }
            results.add(list);
        }
    }

    private int dfs(int i, int j) {
        if(j == 0 || i == j) return 1;

        if(dp[i][j] != 0) return dp[i][j];

        return dp[i][j] = dfs(i - 1, j - 1) + dfs(i - 1, j );
    }

}

回答by rusty1996

This isn't the solution to your code but it is solution to printing Pascals Triangle using only recursionwhich means no loops, using the combinations formula. All it needs is a main method or demo class to create an instance of the PascalsTriangleclass. Hope this helps future Java students.

这不是您的代码的解决方案，而是使用组合公式仅使用递归（这意味着没有循环）来打印 Pascals Triangle 的解决方案。它只需要一个主要方法或演示类来创建类的实例PascalsTriangle。希望这对未来的 Java 学生有所帮助。

public class PascalsTriangle {

private StringBuilder str; // StringBuilder to display triangle

/**
 * Starts the process of printing the Pascals Triangle
 * @param rows Number of rows to print
 */
public PascalsTriangle(int rows) {

    str = new StringBuilder();

    printTriangle(rows, str);
}

/**
 * Uses recursion to function as an "outer loop" and calls
 * itself once for each row in triangle. Then displays the result
 * @param row The number of the row to generate
 * @param str StringBuilder to insert each row into
 */
public static void printTriangle(int row, StringBuilder str) {

    // calls itself until row equals -1
    if (row >= 0) {

        // calls lower function to generate row and inserts the result into front of StringBuilder
        str.insert(0, getRow(row, 0) + "\n");

        // calls itself with a decremented row number
        printTriangle(row - 1, str);
    } else {

        // when the base case is reached - display the result
        JOptionPane.showMessageDialog(null, str);
        System.exit(0);
    }
}

/**
 * Uses recursion to act as the "inner loop" and calculate each number in the given row
 * @param rowNumber Number of the row being generated
 * @param elementNumber Number of the element within the row (always starts with 0)
 * @return String containing full row of numbers or empty string when base case is reached
 */
public static String getRow(int rowNumber, int elementNumber) {

    // calls itself until elementNumber is greater than rowNumber
    if (elementNumber <= rowNumber) {

        // calculates element using combinations formula: n!/r!(n-r)!
        int element = fact(rowNumber) / (fact(elementNumber) * (fact(rowNumber - elementNumber)));

        // calls itself for each element in row and returns full String            
        return element + " " + getRow(rowNumber, elementNumber + 1);

    } else return "";
}

/**
 * Helper function that uses recursion to calculate factorial of given integer
 * @param n Number to calculate factorial
 * @return Factorial
 */
public static int fact(int n) {
    if (n <= 0)
        return 1;
    else
        return n * fact(n - 1);
}