java - 帕斯卡三角形的递归方法

Question

我编写了一种方法来评估Pascal 的行三角形n。但是，当我测试该方法时，我收到错误：

Exception in thread "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;
}

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

Answer 1

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

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

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

Answer 2

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

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);
    }
  }
}

Answer 3

在这段代码中：

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

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

Answer 4

这不是您的代码的解决方案，而是使用组合公式仅使用递归来打印帕斯卡三角形的解决方案，这意味着没有循环。它只需要一个主方法或演示类来创建类的实例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);
}

Answer 5

使用动态编程改进@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 );
    }

}