出現順序を生成するための数式

Question

可能であれば、単純な数式で除外したい2つのルックアップテーブルがあります。

配列のインデックスから配列{0} => 1、{1,2} => 2、{3,4,5} => 3、s.tのマップです。目視か1二2S、3S 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）は、第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, 
    ... 
} 

これらはインデックスからマップする必要があります。 2番目のルックアップでは、入力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です。 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について起こることは、丸め誤差が部分を払う可能性があるということです。私はこれを100万回以上試してみたが、問題は見られなかった。