我们给定一个 [m][m][m] 阶的 N 维矩阵...n 次，其中值位置包含其索引的值和。
例如在 6x6 矩阵中 A , 位置 A[3][4] 处的值将是 7。
我们必须找出大于 x 的元素的总数。对于二维矩阵，我们有以下方法:
如果我们知道一个索引说[i][j] {i+j = x}然后我们通过做 [i++][j--] 创建对角线的 [i--][j++]约束 i和 j始终在 0 范围内至 m.
例如，在值 A[3][4] (x = 7) 的二维矩阵 A[6][6] 中，可以通过以下方式创建对角线:
A[1][6] -> A[2][5] -> A[3][4] -> A[4][3] -> A[5][2] -> A[6][2]
这里我们将我们的问题转化为另一个问题，即计算包括对角线在内的对角线以下的元素。
我们可以轻松算入 O(m)复杂性而不是花费 O(m^2)其中 2是矩阵的顺序。
但是如果我们考虑 N 维矩阵，我们将如何做，因为在 N 维矩阵中如果我们知道那个位置的索引，
其中索引总和为 x说 A[i1][i2][i3][i4]....[in]次。
然后可能有多个满足该条件的对角线，比如做 i1--我们可以增加 {i2, i3, i4....in} 中的任何一个
因此，上面使用的二维矩阵方法在这里变得无用......因为只有两个变量 i1 和 i2 存在。 请帮我找到解决方案
最佳答案
对于 2D:对角线以下元素的数量是 triangular number .
对于 3D:对角线平面以下的元素数是 tetrahedral number
请注意，第 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) = An(s) 有一个重要的性质:s 的 k 次方系数是 n 个被加数组成 k 的方法数。因此，第 n 个到第 k 个系数的总和给出了第 k 个对角线以下元素的计数
关于algorithm - 在 N 维矩阵中找到大于 x 的值，其中 x 是索引之和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12564483/