1

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

这是代码片段：

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

完整的代码在这里：

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

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

4

2 回答 2

2

由于您唯一关心的是空间复杂度，并且您正在使用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 ) 我的意思是第n行中的元素，帕斯卡三角形的位置k，假设行和位置从 0 开始编号。）

于 2012-08-24T20:27:15.800 回答
0

我认为您想要代码，而不是方程式？这里有两个 JavaScript 实现，一个有阶乘计算，一个没有。我不确定我更喜欢哪一个：

//1. non-factorial option
function GenerateTriangle1(rows) {
    var pascalsTriangle = [];

    for (var r = 0; r < rows; r++) {
        var elements = r + 1;
        var level = [];

        for (var i = 0; i < elements; i++) {
            if (i === 0 || i === elements - 1 || r === 1)
                level[i] = 1;
            else {
                var prevRow = pascalsTriangle[r - 1];
                level[i] = prevRow[i - 1] + prevRow[i];
            }
        }

        pascalsTriangle[r] = level;
    }

    return pascalsTriangle;
}

//2. Factorial option
function GenerateTriangle2(rows) {
    var pascalsTriangle = [];

    for (var r = 0; r < rows; r++) {
        var elements = r + 1;
        var level = [];

        for (var i = 0; i < elements; i++) {
            level[i] = CalculateTerm(r, i);
        }

        pascalsTriangle[r] = level;
    }

    return pascalsTriangle;
}

function CalculateTerm(row, term) {
    var divisor = Factorial(term) * Factorial(row - term);
    return divisor > 0 ? Factorial(row) / divisor : 1;
}

function Factorial(n) {
    return n > 1 ? n * Factorial(n - 1) : n;
}

console.log(GenerateTriangle1(4))
console.log(GenerateTriangle1(5))
于 2020-01-10T00:07:23.100 回答