找出帕斯卡三角形背后的逻辑

Question

我在 Java 中找到了一些无需使用数组或 nCr 即可获得帕斯卡三角形的代码，如下所示：

int maxRows = 6;
int r, num;
for (int i = 0; i <= maxRows; i++) 
{
    num = 1;
    r = i + 1;

    //pre-spacing
    for (int j = maxRows - i; j > 0; j--) 
    {
        System.out.print(" ");
    }

    for (int col = 0; col <= i; col++) 
    {
        if (col > 0) 
        {
            num = num * (r - col) / col;
        }
        System.out.print(num + " ");
    }
    System.out.println();
}

我这辈子都搞不懂这段代码是如何生成所需的数字的（序列中的下一个）：

    for (int col = 0; col <= i; col++) 
    {
        if (col > 0) 
        {
            num = num * (r - col) / col;
        }
        System.out.print(num + " ");
    }

有人可以解释一下这个号码是如何产生的吗？我有兴趣了解下一位数字的公式是如何获得的，即 num=num*(r-col)/col 是如何工作的！我也有兴趣了解如何推导这样的公式。

Answer 1

首先是一些理论：帕斯卡三角形由二项式系数组成，其中第n行第k列的项表示x^(n−k)y^k的系数，可以使用公式（n选择k）计算，即n！ / ((n - k)!k!)。可以在 wiki 上找到更多详细信息。

现在让我们看一下代码。

num = num * (r - col) / col

假设我们现在正在计算第 n 行第 k 列的 num 值。在执行这一行之前，num 是第 n 行第 (k-1) 列的值，即

num == (n choose (k-1)) == n! / ((n - (k-1))!(k - 1)!)

num 的新值应该是：

    (n choose k) 
== n! / ((n - k)!k!) 
== (n! / ((n - (k-1))!(k - 1)!)) * (n - (k-1)) / k 
== num * (n - k + 1) / k

因此，要获得 num 的新值（从表示前一个条目的 num），我们需要将其乘以（行 # - 列 # + 1），然后除以列 #。

这正是代码所做的。在这一行中：

num = num * (r - col) / col

r其实就是==(row#+1)，col就是col#。

p.s。还不知道如何在 Whosebug 上格式化公式。一旦我弄清楚如何这样做，就需要清理我的答案。

找出帕斯卡三角形背后的逻辑

Logic behind finding out Pascal's Triangle

java

pascals-triangle