生成Pascal三角形的最佳方法

Question

我正在使用级别顺序遍历的概念来生成Pascal Triangle。

这是代码段：

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

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

（通过

C

（n，k）我的意思是说，假设行和位置是从0开始编号。） 我认为您想要的是代码，而不是方程式？这是两种JavaScript实现，一种带有阶乘计算，另一种不带阶乘计算。我不确定要选择哪一个：

Answer 2