c# - この関数を一定時間で処理させる方法は？

Question

この無限級数のn番目の項を見つける必要があります：1,2,2,3,3,3,4,4,4,4 .. ..

このタスクの定数時間関数を教えていただけますか？

int i = 1;
while(true)
{
   if(i = n)
      //do things and exit the loop

   i++;
}

これは定数時間関数ではないと思います...

Answer 1

編集

さらにコメントを読んだ後、私は質問を誤解したようです。

一定時間内に配列nの位置にあるアイテムを見つけたい場合、答えは簡単です。配列へのアクセスは一定時間であるためです。ただし、何らかの理由でアクセス時間が一定でないコンテナ（リンクリストなど）を使用している場合、または配列内の値を検索したくない場合は、算術級数の式を使用して答えを見つける必要があります。x[n]

算術級数は、3番目のユニークなアイテムのn位置iが

n = i * (i - 1) / 2

したがって、を解く必要がありiます。二次方程式を使用し、無意味なネガティブオプションを破棄すると、次のようになります。

i = Math.Floor( (1 + Math.Sqrt(1 + 8 * n)) / 2)

元の応答

n番目の一意の用語の位置を探していると仮定します。それ以外の場合、問題は些細なことです。

n番目の一意の項の最初の出現は算術級数に従う必要があるように聞こえます。つまり、n番目の一意の用語の位置は次のようになります。

n * (n - 1) / 2

Answer 2

私がこの問題を理解していることを考えると、これはプログラミングの問題というよりは数学の問題です。

問題が次の場合：

1の1コピー、2の2コピー、3の3コピー... nのnコピーで構成される無限級数を考えると、この級数のk番目の値は何ですか？

この問題に取り組むときの最初の手がかりは、n+1が最初に発生する前に1+2 + 3 ... + nの値があることです。具体的には、n + 1の前に（最初のn個の数値の合計）値があります。 （n）（n-1）/2。

ここで、（n）（n-1）/ 2=kに設定します。乗算し、n ^ 2-n --2k = 0に合理化します。2次方程式を使用して解くと、n =（1 + sqrt（1 + 8k））/2が得られます。このフロアは、以前にnの完全なコピーがいくつあるかを示します。幸い、ゼロベースのインデックスが与えられると、フロアは配列のk番目のポイントの値を示します。

つまり、C＃での最終的な答えは

return (int) Math.Floor((1 + Math.Sqrt(1 + 8 * k)) / 2);

非ゼロベースのインデックス付けが与えられた場合、

return (int) Math.Floor((1 + Math.Sqrt(-7 + 8 * k)) / 2);

Answer 3

        public static long Foo(long index)
        {
            if (index < 0)
            {
                throw new IndexOutOfRangeException();
            }

            long nowNum = 0;
            long nowIndex = 0;
            do
            {
                nowIndex += nowNum;
                nowNum++;
            } while (nowIndex < index);
            return nowNum;
        }