我必须比较 M
项,其中不应将单个项与其自身进行比较。在这种情况下,我想设计一个算法来找到第 n 个 比较。例如,如果我正在比较 2 个项目,那么比较列表应该是:
2: (1,2)
同样,如果我比较 3 个项目,比较列表应该是:
3: (1,2), (1,3), (2,3)
遵循这种模式:
4: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
5: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)
等等。
我的问题是,如果输入是 M
,第 nth
项 (i,j)
是什么?
M: (1,2), ..., (i,j), ..., (M-1,M)
虽然我可以很容易地编写一个简单的程序来计算这个临时的,但我想知道是否有一个封闭形式的解决方案,这样它就不会随着 M
扩展。
编辑:为了使这一点更清晰(并有一个可以实现用于测试的示例),我希望代码位于 C
中,并具有以下模板:
void findIJ(int M, int n) {
int i = 0;
int j = 0;
/* Do work to find i and j*/
printf("(i,j) = (%i,%i)\n", i, j);
}
最佳答案
第 n 个是 (i, j),其中:
i = max(k; Sum(M-i, i = 1, k) <= n)
i = max(k; M*k - k*(k+1)/2 <= n)
i = 1 + floor(1/2*(-1+2*M-sqrt(1-4*M+4*M*M-8*(n-1))))
所以:
j = n - M * (i-1) + i*(i+1)/2
关于algorithm - 找到第n个比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39862568/