c++ - 为什么这个 Pascal Triangle 实现给我尾随零？

Question

我试图递归地实现它(迭代似乎不太优雅，但如果我错了请纠正我)。但输出似乎给了我尾随零，前几行是意外的。我已经检查了基本情况和递归情况，但它们似乎没问题。问题肯定在函数内。

#include <iostream>
unsigned long long p[1005][1005];
void pascal(int n)
{
    if (n == 1)
    {
        p[0][0] = 1;
        return;
    }
    else if (n == 2)
    {
        p[0][0] = 1; p[0][1] = 1;
        return;
    }
    p[n][0] = 1;
    p[n][n-1] = 1;
    pascal(n-1);
    for (int i = 1; i < n;++i)
    {
        p[n][i] = p[n-1][i-1] + p[n-1][i];
    }
    return;
}
int main()
{
    int n;
    std::cin >> n;
    pascal(n);
    for (int i = 0 ; i < n ; ++i)
    {
        for (int j = 0 ;j < i+1 ; ++j)
        {
            std::cout << p[i][j] << " ";
        }
        std::cout << "\n";
    }
}

输出:(我输入)15

1
0 0
0 0 0
1 0 0 0
1 1 0 0 0
1 2 1 0 0 0
1 3 3 1 0 0 0
1 4 6 4 1 0 0 0
1 5 10 10 5 1 0 0 0
1 6 15 20 15 6 1 0 0 0
1 7 21 35 35 21 7 1 0 0 0
1 8 28 56 70 56 28 8 1 0 0 0
1 9 36 84 126 126 84 36 9 1 0 0 0
1 10 45 120 210 252 210 120 45 10 1 0 0 0
1 11 55 165 330 462 462 330 165 55 11 1 0 0 0

Answer 1

基本案例 n = 1和 n = 2过于激进(对于像 10 这样的普通输入永远不会达到 1，因为 2 过早地中断了递归，在数组中留下未触及的零)。 n 的这些值应该被递归案例自动覆盖。我们什么都不做的真正基本情况是 n < 0 .

void pascal(int n)
{   
    if (n < 0) return;

    p[n][0] = 1;
    pascal(n - 1);

    for (int i = 1; i <= n; ++i)
    {
        p[n][i] = p[n-1][i-1] + p[n-1][i];
    }
}

n = 15 的输出:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1

话虽如此，hard code 是不好的做法数组的大小。考虑使用 vector 并将参数传递给函数，这样它们就不会改变全局状态。

我们也可以(对我而言)以更直观的方式迭代编写它:

void pascal(int n)
{   
    for (int i = 0; i < n; ++i)
    {
        p[i][0] = 1;

        for (int j = 1; j <= i; ++j)
        {
            p[i][j] = p[i-1][j-1] + p[i-1][j];
        }
    }
}