algorithm - 生成递增序列的数学公式

Question

我有两个查找表，如果可能的话，我想用简单的数学来消除它们。

第一个是从数组中的索引到序列 {0} => 1, {1, 2} => 2, {3, 4, 5} => 3, s.t.有一个 1，两个 2，三个 3，等等。或者视觉上:

lookup1[N] = { 
    1,
    2, 2,
    3, 3, 3,
    4, 4, 4, 4,
    5, 5, 5, 5, 5,
    6, 6, 6, 6, 6, 6,
    7, 7, 7, 7, 7, 7, 7,
    8, 8, 8, 8, 8, 8, 8, 8,
    ...
}

第二个是递增序列，第一个序列是(1)，第二个是(1, 2)，第三个是(1, 2, 3)。这就像模数循环，但在每个循环后增加。视觉上:

lookup2[N] = {
    1,
    1, 2,
    1, 2, 3,
    1, 2, 3, 4,
    1, 2, 3, 4, 5,
    1, 2, 3, 4, 5, 6,
    1, 2, 3, 4, 5, 6, 7,
    1, 2, 3, 4, 5, 6, 7, 8,
    1, 2, 3, 4, 5, 6, 7, 8, 9,
    ...
}

这些需要从索引映射。对于第二次查找，输入 5、4、3 将分别映射到 3、2、1。

是否有任何数学公式可以产生这些模式？我宁愿执行一些指令也不愿进行内存访问。

Answer 1

对于 lookup1 这看起来与 Triangular numbers 密切相关, 事实上它是反问题。三角形数是 n 行三角形中的项目数。所以你有 T1 = 1，T2 = 1+2 = 3，T3 = 1+2+3 = 6，T4 = 1+2+3+4 = 10。或者作为函数 f(1) = 1，f( 2)=3, f(3)=6, f(4)=10。

你想做相反的事情，所以 g(1) = 1，g(3) = 2，g(6) = 3，g(10) = 4。我们稍后会担心其他值。

三角数 f(n) = n (n+1)/2 有一个公式。还有一个更复杂的倒数公式

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

一个小实验表明

ceil((sqrt(8*n+1) - 1) / 2 )

给出你想要的数字。

对于第二部分，你可以使用反三角数的函数，然后找到前一个三角数，并取差

X =  ceil((sqrt(8*n+1) - 1) / 2);
T = (X * (X-1))/2 ; 
print(n-T); 

一个小小的警告。在转换点处，sqrt(8*n+1) 的计算结果应为奇整数值。对于非常大的 n 可能发生的情况是舍入误差可能会支付一部分。我已经对此进行了超过一百万次的测试，但没有发现问题发生。