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

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 值，而帕斯卡三角形的第 k 行中的条目加起来为 2^k，因此您尝试执行 2^40 ~ 10^12 步。

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

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

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

有更快的方法来计算帕斯卡三角形的条目和奇偶校验。例如，a select 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 ，但你应该先看看模式。

这是 a choice b 的 Java 内存版本:

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