1

[m][m][m]....n 回のオーダーの N 次元行列が与えられます。値 position には、そのインデックスの値の合計が含まれます。たとえば、6x6 行列Aでは、position の値はA[3][4]7 になります。

x より大きい要素のカウントの総数を見つける必要があります。2 次元行列の場合、次のアプローチがあります。

1 つのインデックスがわかっている場合は、制約[i][j] {i+j = x}を使用するだけで対角線を作成し、常に の範囲内にあります。たとえば 、値 A[3][4] の 2 次元行列 A[6][6] (x = 7)、対角線は次の方法で作成できます。[i++][j--][i--][j++]ij0m.

A[1][6] -> A[2][5] -> A[3][4] -> A[4][3] -> A[5][2] -> A[6][2]

ここでは、対角線を含む対角線の下の要素を数えるという別の問題に問題を変換しました。行列の次数を費やす代わりに、O(m)複雑さ を簡単に数えることができます。しかし、N 次元の行列を考えると、どのようにそれを行うのでしょうか。N 次元の行列では、その場所のインデックスがわかっている場合、インデックスの合計は時間と言えます。次に、その条件を満たす複数の対角線が存在する可能性があります。たとえば、次のいずれかをインクリメントできます。O(m^2)2xA[i1][i2][i3][i4]....[in]i1--{i2, i3, i4....in}

したがって、上記の 2 次元行列に対するアプローチは、ここでは役に立たなくなります... 2 つの変数 i1 と i2 しか存在しないためです。解決策を見つけるのを手伝ってください

4

2 に答える 2

1

2D の場合: 対角線より下の要素の数は三角数です。

3D の場合: 対角面より下の要素の数は四面体数です

K 番目の四面体数は、最初の K 個の三角形数の合計であることに注意してください。

nD の場合: n-simplexial (正確な英語の用語はわかりません) 数 (最初の (n-1)-simplexial 数の合計です)。

K番目のnシンプレクシアルの値は

 S(k, n) = k * (k+1) * (k+2).. (k + n - 1) / n! = BinomialCoefficient(k+n-1, n)

編集:このメソッドは、主な反対角 (超) 平面より下の X の制限された値に対して「そのまま」機能します。

生成関数のアプローチ: 多項式を考えてみましょう

A(s)=1+s+s^2+s^3+..+s^m

次に、それの n 乗
B(s) = A n (s) には重要な特性があります。s の k 乗の係数は、n の被加数から k を構成する方法の数です。したがって、n 番目から k 番目の係数の合計により、k 番目の対角線より下の要素の数が得られます。

于 2012-09-24T12:53:37.980 に答える
0

2 次元行列の場合、問題を別の問題に変換しましたcount the elements below the diagonal including the diagonal。

3 次元行列で視覚化してみてください。3 次元行列の場合、問題は別の問題に還元されます。count the elements below the diagonal plane including the diagonal

于 2012-09-24T12:35:13.967 に答える