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しているため（ある種の大きな整数タイプの潜在的に無制限のサイズとは対照的に）、次の2つの事実を使用して、実際にO（1）のスペースの複雑さを実現できます。

  • C（n、0）= 1（0≤nの場合）
  • C（n、k +1）= C（n、k）×（n − k）/（k + 1）for0≤k < n

これらの2つの事実は、同じ行の前の要素のみを使用して各要素を計算できることを意味します。したがって、一度に複数の要素を保存する必要はありません。

（C（n、k ）とは、行と位置に0から番号が付けられていると仮定して、パスカルの三角形の位置kである行nの要素を意味します。 ）

于 2012-08-24T20:27:15.800 に答える
0

方程式ではなく、コードが必要だと思いますか？これが2つのJavaScript実装です。1つは階乗計算あり、もう1つは階乗計算なしです。どちらを好むかは未定です。

//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 に答える