math - 恢复三角形 for 循环中的索引

Question

是否有一种简单的方法可以恢复嵌套 for 循环中的索引？例如，在构建帕斯卡三角形的 for 循环中

int index = 0;
for (int i = 0; i < N; ++i)
  for (int j = 0; j < N-i; ++j)
    index++;

有没有办法只给定索引来恢复i和j？

Answer 1

我将其添加为第二个答案，因为它使用不同的语言(现在是 C)并且具有更直接的方法。我保留原来的答案，因为如果没有它，下面的代码几乎无法解释。我将两个函数合并为一个函数，以减少函数调用开销。另外，为了 100% 确定它回答了原始问题，我逐字使用了该问题中的循环。在驱动程序函数中，我明确表明 N = 4 时的输出是正确的，然后对 N = 10000 进行压力测试(总共 100,000,000 次通过内循环)。我没有任何正式的计时代码，但在我的机器上运行并测试这 1 亿个案例大约需要 1 秒。我的代码假定为 32 位 int。如果需要，更改为 long:

#include <stdio.h>
#include <math.h>

void from_index(int n, int index, int *i, int *j);

int main(void){
    int N;
    int ri,rj; //recovered i,j
    N = 4;
    int index = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N-i; ++j){
                    from_index(N,index,&ri,&rj);
                    printf("i = %d, j = %d, index = %d, ",i,j,index);
                    printf("recovered i = %d, recovered j = %d\n",ri,rj);
                    index++;
            }

    //stress test:

    N = 10000;
    index = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N-i; ++j){
                    from_index(N,index,&ri,&rj);
                    if(i != ri || j != rj){
                        printf("Don't post buggy code to Stack Overflow!\n");
                        printf("(i,j) = (%d,%d) but recovered indices are (%d,%d)\n",i,j,ri,rj);
                        return 0;
                    }
                    index++;
            }
    printf("\nAll %d tests passed!\n",N*N);
    return 0;
}

void from_index(int n, int index, int *i, int *j){
    double d;
    d = 4*n*(n+1) - 7 - 8 * index;
    *i = floor((-1 + sqrt(d))/2);
    *j = *i * (*i + 1)/2;
    *j = n*(n+1)/2 - 1 - index - *j;
    *j = *i - *j;
    *i = n - *i - 1;   
}

输出:

i = 0, j = 0, index = 0, recovered i = 0, recovered j = 0
i = 0, j = 1, index = 1, recovered i = 0, recovered j = 1
i = 0, j = 2, index = 2, recovered i = 0, recovered j = 2
i = 0, j = 3, index = 3, recovered i = 0, recovered j = 3
i = 1, j = 0, index = 4, recovered i = 1, recovered j = 0
i = 1, j = 1, index = 5, recovered i = 1, recovered j = 1
i = 1, j = 2, index = 6, recovered i = 1, recovered j = 2
i = 2, j = 0, index = 7, recovered i = 2, recovered j = 0
i = 2, j = 1, index = 8, recovered i = 2, recovered j = 1
i = 3, j = 0, index = 9, recovered i = 3, recovered j = 0

All 100000000 tests passed!