计算具有大量行和奇偶校验的帕斯卡三角形

Question

我正在使用一个简单的递归函数来打印帕斯卡三角形，但是程序的复杂度似乎呈指数级增长（可能是错误的？）而且我想打印大量的帕斯卡三角形行（50+行），这对于我当前的函数来说似乎是不可能的，因为它在大约 30 多行时开始阻塞。

我还想计算条目的奇偶校验并打印它们的奇偶校验而不是数字，我不确定我是否遗漏了什么并且不需要计算条目的整个值来找到它的奇偶校验我可以只使用规则吗？

public static long pascalsTriangle(int row, int col)
{
    if(row == 0 || col == 0 || col == row) return 1;
    else if(col == 1 || col == row-1) return row;
    else return pascalsTriangle(row - 1, col -1) + pascalsTriangle(row - 1, col);
}


public static void main(String[] args)
{
    int num = 40;
    for(int row = 0; row <= num; row++)
    {
        for(int space = num; space > row; space--) System.out.printf("   ");
        for(int col = 0; col <= row; col++)
        {
            String str_n =   (pascalsTriangle(row, col) % 3 == 0)? "odd " : "even";
            System.out.printf("%6s", str_n);

        }
        System.out.println();
    } 
}

Answer 1

您的代码存在的问题是您正在进行大量冗余计算。算40选20，算39选19，39选20，算38选19两次。您多次计算较低的值以产生每个输出。您的代码需要大约 n 步来生成 n 的值，Pascal 三角形第 k 行中的条目加起来为 2^k，因此您正在尝试执行 2^40 ~ 10^12 步。

相反，您可以将计算出的值存储在二维数组中。这称为 memoization 或动态规划。要计算 a choose b，这将需要大约 (b+1)(a-b+1) 步，比 a choose b 步骤快得多，但是当您计算多个条目时，即使这些步骤中的大部分也被节省了。要减少递归深度，您可能希望按顺序计算行，从第 0 行到第 40 行，即使您只需要一个值。

由于条目变大，您可能运行遇到一些溢出问题。使用 java.math.BigInteger 变量而不是长变量。当您发现第 67 行及以后的行中的条目大于 2^63 时，这就变得很有必要了。

要计算奇偶校验，您只需要跟踪早期值的奇偶校验。

有更快的方法来计算帕斯卡三角形的元素和奇偶校验。例如，a choose b 是 a!/(b!(a-b)!)，您可以更好地沿行递归计算，(a choose 0 ) = 1, a choose b = (a choose min(b,a-b) ), (a 选择 b) = (a 选择 (b-1))*(a-b+1)/b。 There are even faster ways to determine the parities，但你应该先看看模式。

这是一个 Java 记忆版本的选择 b:

import java.math.*;
public static class Binomial
{
    private static BigInteger[][] memoized = new BigInteger[1001][1001];
    public static BigInteger comb(int n, int k)
    {
        if (k>n || n<0 || k<0)
            return BigInteger.valueOf(0);
        if (k > n-k)
            return comb(n,n-k);
        if (n>1000 || k>1000) // we could expand the memoized array dynamically
            return BigInteger.valueOf(-1);

        if (memoized[n][k] != null)
            return memoized[n][k];
        // we got here because we haven't computed it yet
        BigInteger result;
        if (n==0 && k==0)
            result = BigInteger.valueOf(1);
        else 
            result= comb(n-1,k-1).add(comb(n-1,k));
        memoized[n][k] = result;
        return result;
    }
}

Answer 2

每次计算一个值时，您都会重新计算该值所需的每个父级，一直返回到根。计算一行所需的唯一数据是前一行的数据。此外，如果您只想要奇偶校验，则只需为每一行存储 even/odd 值。因此，除非您真的想使用递归，否则我的解决方案将基于以下内容：

  public static int[] calcNextRow(int[] prevRow) {
    int[] newRow = new int[prevRow.length + 1];
    newRow[0] = 1; 
    for (int i = 1; i < prevRow.length; ++i) {
      newRow[i] = (prevRow[i-1] + prevRow[i]) % 2; 
    }
    newRow[prevRow.length] = 1;
    return newRow;
  }

然后你可以以递归的方式使用它，或者直接从循环中调用它：

  public static void main() {
    int[] prevRow = { 1 };
    printRow(prevRow);

    for (int row = 0; row < 10; ++row) {
      int[] nextRow = calcNextRow(prevRow);
      printRow(nextRow);
      prevRow = nextRow;
    }
  }

如果要计算实际值，只需删除 % 2:

  newRow[i] = prevRow[i-1] + prevRow[i];

尽管您显然需要将 int 换成 long 或 BigInteger 换成更大的树。

干杯，

计算具有大量行和奇偶校验的帕斯卡三角形

Calculating pascals triangle with large number of rows and parity

java

recursion