1

ベース アドレス 5000 から始まる、メモリ内に次のダイヤモンド配列があります。最初の有効な値は 5008 (インデックス 2) に配置され、他のすべての値はそれを基準にして配置されます。

 .  .  4  .  .
 .  3  7  8  .
 2  2  9  8  5
 .  1  5  9  .
 .  .  3  .  .

「.」で表されるすべての値。配列内は初期化されていないため、アクセスしないでください。

今問題。メモリ内の初期化されていない値にアクセスせずに、この配列を MIPS で並べ替える必要があります。メモリの制約により、ダイヤモンドの有効なインデックスをすべて使用して新しい配列を作成できません。基本的に、私は立ち往生しています。

4

1 に答える 1

3

セルの行は次のkように計算できます。

row(k) = k < (S+1)*(S+1)/4 ? isqrt(k) : S - 1 - isqrt((S*S-1)/2 - k)

nひし形配列の行のインデントは次のとおりです。

indent(n) = abs((S - 1)/2 - n)

n行が始まるセルは次のとおりです。

start(n) = n < S/2 ? n*n : (S*S+1)/2 - (S-n)*(S-n)

これらを組み合わせて、 cell のインデックスを計算できますk。

index(k) = row(k)*S + indent(n) + (k - start(row(k)))

例：

S = 5
. . # . .
. # # # .
# # # # #
. # # # .
. . # . .

cell    row     indent  start   index
0       0       2       0       2
1       1       1       1       6
2       1       1       1       7
3       1       1       1       8
4       2       0       4       10
5       2       0       4       11
6       2       0       4       12
7       2       0       4       13
8       2       0       4       14
9       3       1       9       16
10      3       1       9       17
11      3       1       9       18
12      4       2       12      22

これを使用すると、 Selection sortを簡単に実装できます。

/// Calculates the index of cell k in a diamond array of size S.
int index(int k, int S)
{
    int row = k < (S+1)*(S+1)/4 ? isqrt(k) : S - 1 - isqrt((S*S-1)/2 - k);
    int indent = abs((S - 1)/2 - row);
    int start = n < S/2 ? n*n : (S*S+1)/2 - (S-n)*(S-n);
    return row*S + indent + (k - start);
}

/// Sorts the diamond array data, of size S.
void diamondSelectionSort(int[] data, int S)
{
    int total = (S*S+1)/2;
    for (int i = 0; i < total; i++)
    {
        int indexI = index(i,S);

        int bestCell = i;
        int bestIndex = indexI;
        int bestValue = data[bestIndex];

        for (int j = i+1; j < total; j++)
        {
            int indexJ = index(j,S);

            if (data[indexJ] < bestValue)
            {
                bestCell = j;
                bestIndex = indexJ;
                bestValue = data[indexJ];
            }
        }
    }

    if (bestIndex > i)
    {
        data[bestIndex] = data[indexI];
        data[indexI] = bestValue;
    }
}

/// Integer square root. Adopted from
/// http://home.utah.edu/~nahaj/factoring/isqrt.c.html
int isqrt (int x)
{
    if (x < 1) return 0;

    int squaredbit = (int) ((((unsigned int) ~0) >> 1) & 
            ~(((unsigned int) ~0) >> 2));
    int remainder = x;
    int root = 0;
    while (squaredbit > 0) {
        if (remainder >= (squaredbit | root)) {
            remainder -= (squaredbit | root);
            root = (root >> 1) | squaredbit;
        } else {
            root >>= 1;
        }
        squaredbit >>= 2; 
    }

    return root;
}

index()少し広げることができます：

/// Calculates the index of cell k in a diamond array of size S.
int index(int k, int S)
{
    int row, indent, start;
    if (k < (S+1)*(S+1)/4)
    {
        row = isqrt(k);
        indent = (S - 1)/2 - row;
        start = n*n;
    }
    else
    {
        row = S - 1 - isqrt((S*S-1)/2 - k);
        indent = row - (S - 1)/2;
        start = (S*S+1)/2 - (S-n)*(S-n);
    }
    return row*S + indent + (k - start);
}
于 2013-07-01T10:20:52.050 に答える