2

グリッドを反復処理し、インデックスを新しい順序で別のグリッドに変換できるアルゴリズムを探しています。

基本的に、サイズ n*m のグリッドが与えられた場合:

1_1 1_2 1_3 ... 1_n
2_1 2_2 2_3 ... 2_n
.
.
.
m_1 m_2 m_3 ... m_m

どうすれば次のように変換できますか:

1_1 1_2 1_4 ...
1_3 1_5 ...
1_6 ...
...
.
.
.

最初のグリッドを反復処理し、一番上の行で左から右に移動し、次に 2 番目の行で左から右に移動し、一番下の行で左から右に移動するとします。

基本的に、要素を上の三角形に押し込みます。

もう 1 つの問題は、三角形を格納するために使用されるグリッドの長さと幅を、n と m を知るだけでどのように把握するかということです。そのための公式はありますか？

たとえば、5*6 のグリッドは 8*7 に変更されます...

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30

になります：

 1  2  4  7  11 16 22 29
 3  5  8  12 17 23 30
 6  9  13 18 24
 10 14 19 25
 15 20 26
 21 27
 28
4

2 に答える 2

2

以下は私のために働くようです：

public static T[,] ConvertToUpperTriangle<T>(T[,] arr)
{
    // calculate the dimensions
    int elements = arr.GetLength(0) * arr.GetLength(1);

    double rows = 0.5 * (Math.Sqrt(8 * elements + 1) - 1);

    int newHeight = (int)rows;
    int newWidth = (int)Math.Ceiling(rows);

    // create the new array
    var arr2 = new T[newHeight, newWidth];

    int j = 0;
    int i = 0;
    foreach (T element in arr)
    {
        arr2[j, i] = element;
        i--;
        j++;
        if (i < 0)
        {
            i = j;
            j = 0;
        }
    }

    return arr2;
}

は0.5 * (Math.Sqrt(8 * elements + 1) - 1)、実行sum from 1 to n of nしてからWolfram Alphasolve a = 0.5 * n * (n + 1) for nを介して実行されます。

編集：

次のように、特定のインデックスiとa を取得できます。jindex

int rows = (int)(0.5 * (Math.Sqrt(8 * index + 1) - 1));

int bottomLeft = (int)(0.5 * rows * (rows + 1));
int difference = index - bottomLeft;

int i;
int j;

if (bottomLeft == index)
{
    i = 0;
    j = rows - 1;
}
else
{
    i = rows + 1 - difference;
    j = difference - 1;
}
于 2013-03-02T22:59:38.337 に答える
2

関数 (i,j) -> i*N + j である、開始グリッド NxM 内の各グリッド要素 (i,j) の「順序位置」O(i,j) を定義しましょう。

ここで、O(i,j) より小さい最大の三角数を T == (k(k+1)/2 と呼びます) と呼ぶと、(i,j) の新しいグリッド位置は次のようになります: (i,j) j) -> ( O(i,j) - T, k + T - O(i,j) )

O(i,j) と T を代入すると、次のようになります。

(i,j) -> ( i*N + j - k(k+1)/2, k + (k+1)(k+2)/2 - i*N + j)

= ( i*N + j - k(k+1)/2, (k+1)(k+2)/2 - i*N + j)

今手に入るのはここまでです。

更新: k は三角数 T == k(k+1)/2 の辺の長さであることに注意してください。

于 2013-03-02T21:25:40.423 に答える