从 "flat array" 索引计算三角矩阵索引?
Compute triangular matrix indices from "flat array" index?
得到一个表示为平面数组的三角矩阵
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;
}
}
有没有一种既简单又容易实施的方法?
每行的第一个数字 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);
}
对于输入 n
,可以使用以下方法找到答案:
k = (int)(((int)(sqrt(8*n + 1)) - 1)/2)
l = (int)(n - (k * (k+1) /2 ))
答案:
(k,l)
这是一个选项,可能不是最好的(只是为了表明我已经考虑过了):
这是对单调递增函数的二分搜索:
void bar(uint n) {
uint i = 1;
while (n >= i * (i + 1) / 2) {
i <<= 1;
}
i >>= 1;
uint stepSize = i >> 1;
while (stepSize) {
uint tmp = i + stepSize;
if (n >= tmp * (tmp + 1) / 2) {
i = tmp;
}
stepSize >>= 1;
}
cout << n << " = "
<< "[" << i << ", " << (n - i * (i + 1) / 2) << "], ";
if (i == n - i * (i + 1) / 2) {
cout << std::endl;
}
}
得到一个表示为平面数组的三角矩阵
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;
}
}
有没有一种既简单又容易实施的方法?
每行的第一个数字 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);
}
对于输入 n
,可以使用以下方法找到答案:
k = (int)(((int)(sqrt(8*n + 1)) - 1)/2)
l = (int)(n - (k * (k+1) /2 ))
答案:
(k,l)
这是一个选项,可能不是最好的(只是为了表明我已经考虑过了):
这是对单调递增函数的二分搜索:
void bar(uint n) {
uint i = 1;
while (n >= i * (i + 1) / 2) {
i <<= 1;
}
i >>= 1;
uint stepSize = i >> 1;
while (stepSize) {
uint tmp = i + stepSize;
if (n >= tmp * (tmp + 1) / 2) {
i = tmp;
}
stepSize >>= 1;
}
cout << n << " = "
<< "[" << i << ", " << (n - i * (i + 1) / 2) << "], ";
if (i == n - i * (i + 1) / 2) {
cout << std::endl;
}
}