3

Cで次の宿題をしています。基本的に、解決策ではなくアプローチが必要です。

13 x 13 の配列があります。配列には、考慮する必要がある菱形があります。このひし形の外側にあるものはすべて -1 に初期化されます (重要ではありません)。以下の 5 x 5 配列の例 -

x x 1 x x 
x 2 2 2 x
3 3 3 3 3
x 4 4 4 x
x x 5 x x

x=-1

この配列では、各エントリのひし形にある値には 11 ビットが含まれています。5 lsb には 1 つのデータ (色相) が含まれ、他の 6 には別のデータ (直径) が含まれます。色相についてはデータを行方向に単調に並べ替え、次に直径については列方向に単調に並べ替える必要があります。

これを行う最も効率的でメモリを節約する方法は何でしょうか? これを保存する必要があるため、別の配列を作成するのではなく、エントリを入れ替えるのが最善です。最終的に、ソートされたひし形配列になります (まだ -1 があります)。どうもありがとうございました！

4

3 に答える 3

1

要素を並べ替える方法が正確にわかりませんでした

色相については行ごとに単調に、次に直径については列ごとに単調に

しかし、ここにあなたが使うことができるかもしれないいくつかのアイデアがあります.

  • 配列は 13x13 (169 要素) です。その内、ほぼ正確に半分 (84) が空であるため、それらを一時ストレージとして使用できます (たとえば、radix-sort )。
  • 値には意味のある 11 ビットがあります。実際のコンピューターの数値は 16 ビットまたは 32 ビットのいずれかです。そのため、最上位ビットの 5 (またはシステムによっては 21) を一時記憶域として使用できます。
  • 上位 5 ビットを使用する良い方法の 1 つは、そこに 5 LSB (色相) のコピーを置くことです。これにより、通常の整数比較を行うときに 2 つの部分の意味が逆転します (色相が直径よりも重要になります)。
于 2013-06-22T13:19:40.747 に答える