c - 生成帕斯卡三角形的最佳方法

Question

我正在使用层次顺序遍历的概念来生成帕斯卡三角形。

这是代码片段:

void printPascalTriangle(int n)
{
    int line=1,Q[50]={0},f=-1,r=-1,prev,t;

    Enqueue(Q,&f,&r,1);
    Enqueue(Q,&f,&r,0);

    prev=0;
    while(line!=n)
    {
            t = Dequeue(Q,&f,&r);

            if( !t )
            {
                    line++;
                    prev = 0;
                    Enqueue(Q,&f,&r,1);

                    if(!isEmpty(&r))
                            Enqueue(Q,&f,&r,0);

                    printf("\n");
            }
            else
            {
                    printf("%d ", t);
                    Enqueue(Q,&f,&r,prev+t);
                    prev = t;
            }
    }
}

完整代码为here :

这种方法的优点是它的空间复杂度是 O(N)，其中 N 是行数。

有没有更好的方法来做同样的事情？

Answer 1

由于您唯一关心的是空间复杂度，并且您正在使用 int(而不是某种可能无限大小的大整数类型)，您实际上可以实现 O 的空间复杂度(1) 通过使用这两个事实:

• C(n, 0) = 1 对于 0 ≤ n
• C(n, k+1) = C(n , k) × (n − k)/(k + 1) 对于 0 ≤ k <n

这两个事实意味着您可以仅使用同一行的前一个元素来计算每个元素，因此您永远不必一次保存多个元素。

(By C(n, k) 我的意思是 n 行中的元素，位置 k 帕斯卡三角形，假设行和位置从 0 开始编号。)