46

パスカルの三角形のn番目の行（特定の要素ではなく、行全体）を見つけることに興味があります。それを行うための最も効率的な方法は何でしょうか？

私は、上の行の対応する要素を合計することによって三角形を構築する従来の方法について考えました。

1 + 2 + .. + n = O(n^2)

別の方法は、特定の要素の組み合わせ式を使用することです。

c(n, k) = n! / (k!(n-k)!)

行の各要素については、組み合わせの計算方法によっては、前者の方法の方が時間がかかると思います。何か案は？

4

14 に答える 14

13

1 行は次のように計算できます。

First compute 1.               -> N choose 0
Then N/1                       -> N choose 1
Then N*(N-1)/1*2               -> N choose 2
Then N*(N-1)*(N-2)/1*2*3       -> N choose 3
.....

1 つの数値を掛けて別の数値で割るだけで、前の値から次の値を計算できることに注意してください。

これは、1 つのループで実行できます。サンプルのパイソン。

def comb_row(n):
   r = 0
   num = n
   cur = 1
   yield cur
   while r <= n:
      r += 1  
      cur = (cur* num)/r
      yield cur
      num -= 1
于 2013-03-22T21:48:34.497 に答える
9

最も効率的なアプローチは次のとおりです。

std::vector<int> pascal_row(int n){
    std::vector<int> row(n+1);
    row[0] = 1; //First element is always 1
    for(int i=1; i<n/2+1; i++){ //Progress up, until reaching the middle value
        row[i] = row[i-1] * (n-i+1)/i;
    }
    for(int i=n/2+1; i<=n; i++){ //Copy the inverse of the first part
        row[i] = row[n-i];
    }
    return row;
}
于 2013-11-08T10:23:24.920 に答える
2

Scala プログラミングでは、次のように簡単にできます。

def pascal(c: Int, r: Int): Int = c match {
    case 0 => 1
    case `c` if c >= r => 1
    case _ => pascal(c-1, r-1)+pascal(c, r-1)
}

私はこれを次のように呼びます：

for (row <- 0 to 10) {
    for (col <- 0 to row)
        print(pascal(col, row) + " ")
    println()
}

結果:

. 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:列が最初の列である場合、常に図 1 を返すようにします。

ステップ 2:各 X 番目の行には、X 個の列があります。だから私たちはそう言います。最後の列 X が X 番目の行以上の場合、数値 1 を返します。

ステップ 3:それ以外の場合は、現在の列の直前の列と現在の列の直前の行の繰り返しパスカルの合計を取得します。その列と現在の行の直前の行のパスカル。

幸運を。

于 2016-11-11T22:06:42.393 に答える
2

それを計算する簡単な方法は、次の行の要素が前の行の 2 つの連続する要素の合計として計算できることに注意することです。

[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

たとえば6 = 5 + 1、、、および。15 = 5 + 10_ これにより、前の行から次の行を計算する簡単なアルゴリズムが得られます。1 = 1 + 020 = 10 + 10

def pascal(n):
    row = [1]
    for x in xrange(n):
        row = [l + r for l, r in zip(row + [0], [0] + row)]
    # print row
    return row

print pascal(10)
于 2015-11-30T07:30:26.577 に答える
0

Python での O(n) 空間複雑度ソリューションは次のとおりです。

def generate_pascal_nth_row(n):
    result=[1]*n
    for i in range(n):
        previous_res = result.copy()
        for j in range(1,i):
            result[j] = previous_res[j-1] + previous_res[j]
    return result

print(generate_pascal_nth_row(6))
于 2018-01-11T20:04:07.107 に答える