algorithm - 从 "flat array"索引计算三角矩阵索引？

Question

得到一个表示为平面数组的三角矩阵

0 = [0, 0]
1 = [1, 0], 2 = [1, 1]
3 = [2, 0], 4 = [2, 1], 5 = [2, 2]
6 = [3, 0], 7 = [3, 1], 8 = [3, 2], 9 = [3, 3]

使用原始索引计算索引对的最快方法是什么？一种方法(朴素的蛮力)是这样计算的:

void foo(uint n) {
    uint origN = n;
    uint i = 0;
    while(n > i) {
        n -= ++i;
    }
    cout << origN << " = " << "[" << i << ", " << n << "], ";
    if (i == n) {
       cout << std::endl;
    }
}

有没有一种直接且易于实现的方法？

Answer 1

每行中的第一个数字 n 是 r*(r+1)/2，其中 r 是行号。求解 n = r*(r+1)/2 方程你有这个积极的 r 根:

r = (sqrt(1+8*n)-1)/2

因此，要获得任意 n 的行号，您应该将结果四舍五入:

r = floor(sqrt(1+8*n)-1)/2

现在列号可以作为 n 和行中第一个数字之间的差异找到:

c = n - r*(r+1)/2

这是 Java 中的示例代码:

public static void foo(int n) {
    int r = (int) Math.floor((Math.sqrt(8 * n + 1) - 1) / 2);
    int c = n - r * (r + 1) / 2;
    System.out.println("n = " + n + "; r = " + r + "; c = " + c);
}