6

私はこの Java の問題を抱えており、これは高レベルのアルゴリズムに関連していると思われますが、私の検索では実用的なものを見つけることができませんでした。

次のように配列を作成します。

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5   10  10  5  1

基本的に、 A i,j = A i-1,j-1 +A i-1,jです。インデックス (l, c) の要素を返すことになっています: (4, 1) の場合は 4 を返し、(5, 2) は 10 を返します。私の解決策は簡単ですが、十分ではありません。

static long get(int l, int c){
    long[][] matrix = new long[l+1][l+1];
    matrix[0][0]=1;
    matrix[1][0]=1; 
    matrix[1][1]=1;
    for(int i=2;i<=l;i++){
        matrix[i][0]=1;
        for(int j=1;j<=i;j++){
            matrix[i][j] = matrix[i-1][j-1]+matrix[i-1][j];
        }   
    }
    return matrix[l][c];
}

l と c の値が大きい場合は機能しません。BigInteger を使用しても機能しません。検索の結果、ループのスキューとスカラー化にたどり着きましたが、どこから始めればよいかわかりません。正しい方向への操縦は本当に感謝しています。

PS: 初心者の雰囲気で申し訳ありません。これは私の最初の質問です!

4

3 に答える 3

12

閉じた式が存在するパスカルの三角形を説明しています。

matrix[n][k] = n!/(k! * (n-k)!)

PSこれらの数字がよく知られているように見える場合、それは二項定理からのものでもあるためです。一般的な例は次のとおりです。

(x+y)^2 = 1* x^2 + 2xy + 1*y^2
(x+y)^3 = 1*x^3 + 3*xy^2 + 3yx^2 + 1*y^3
于 2012-10-14T20:08:20.233 に答える
4

ループを使用する必要はありません。これは単にパスカルの三角形であり、式は次のとおりです。

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

位置 (n, k) に対する答えを生成します。

于 2012-10-14T20:09:19.773 に答える
0

これを試して：

static long get(int l, int c) throws Exception {
    if (l != c)
         throw new Exception("l != c");
    long[][] matrix = new long[l+1][l+1];
    matrix[0][0]=1;
    for (int i = 1; i <= l; ++i) {
         for (int j = 0; j <= i; ++j) {
              if (j - 1 >= 0) {
                    matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1];
              } else {
                    matrix[i][j] = matrix[i - 1][j];
              }
         }
    }
    return matrix[l][c];
}
于 2012-10-14T20:14:19.493 に答える