2

0 から n-1 までの値の 'nCk' の組み合わせに対応する値にメモリ (静的ハードウェア) を割り当てるためのメモリ アドレス指定方法を見つける必要があります。

「n」を 6、「k」を 4 とすると、組み合わせに対応する値 (8 ビットまたは 16 ビット) を格納する必要があります。

(1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,4,5) (1,2,4,6) (1,2,5,6) (1,3,4,5) (1,3,4,6) (1,3,5,6) (1,4,5,6) (2,3,4,5) (2,3,4,6) (2,3,5,6) (2,4,5,6) (3,4,5,6)

「k」(ここでは 4) の数字を取得したら、「k」タプルに対応する要素に直接アクセスできるはずです。

k タプルの下位のインデックスは上位のインデックスよりも小さくなり、どのインデックスも等しくありません。

検索せずにそのようなデータを格納および取得するためのアドレス指定スキームを生成することは可能ですか? これは、アドレスが生成され、可能な限り最小限のメモリ量で、最小限の計算で実行する必要があります。（方法に関係なく多少のメモリは無駄になると思います。）

さまざまなインデックスに対してさまざまな定数を使用する線形ハッシュを考えましたが、それは多くのメモリ損失や、定数を計算するための計算の複雑さにつながります。

この問題に関する提案は非常に役立ちます。

例：

(組み合わせ -> メモリ内の対応する値)

([(1,2,3,4)->14], [(1,2,3,5)->3], [(1,2,3,6)->-4], [(1,2,4,5)->7], [(1,2,4,6)->22], [(1,2,5,6)->-11], [(1,3,4,5)->5], [(1,3,4,6)->3], [(1,3,5,6)->-1], [(1,4,5,6)->9], [(2,3,4,5)->35], [(2,3,4,6)->4], [(2,3,5,6)->7], [(2,4,5,6)->-2], [(3,4,5,6)->6])

上記のモジュールへの入力が (2,3,5,6) の場合、値 (7) を直接取得できるはずです。

編集:「n」と「k」は常に偶数です。

4

1 に答える 1

1

問題の私の理解

したがって、あなたの質問を理解しているように、データを取得するために使用される可能性のある「キー」は、n 値の中から k 値を選択することです。

と ：

  • 0 から n-1 までの n
  • 繰り返し値なし
  • キーに存在する値のみが重要であり、それらの順序は重要ではありません

シンプルな命題

基準点として簡単な提案から始めましょう。

「キー」に存在する値は、「n」ビット アドレスで 1 に設定する必要があるビットであると考えることができます。

  • キーからアドレスへの変換は非常に簡単に思えます
  • メモリサイズは 2^n ワードです (かなり多くのスペースが無駄になります)

分割統治 : n=16, k=2

この特定のケースを見てみましょう: n=16, k=2.

前のソリューションでは、2^16 ワードのメモリを使用しますが、可能なキーは 16*15/2 = 120 しかありません。

このような場合、分割統治戦略は次のようになります。

  1. 2 つの値が両方とも可能な値の最初の部分にある (0 から 7 まで)
  2. どちらも可能な値の 2 番目の部分 (8 から 15 まで) にある
  3. いずれかの値が最初の部分にあり、もう 1 つの値が 2 番目の部分にあります。

この予備テストを使用すると、この場合は以下を使用できます。

  • ケース 1 用の 1 つの 8 ビット アドレス メモリ (参照: 最初の単純な解決策ですが、16 ではなく n=8 を使用)
  • ケース 2 用の 1 つの 8 ビット アドレス メモリ (同上)
  • 最初の部分に 8 つの選択肢があり、2 番目の部分に 8 つの選択肢がある特別なケースがあるため、追加の 8*8=64 ワード メモリ (6 ビット アドレス、最初の 3 ビットは最初の 0 から 7 の値に対応)一部であり、残りの 3 つは、8 から 15 までの値の位置に対応する 0 から 7 までの値です)。

2^8 + 2^8 + 64 = 576 ワード

分割統治 : n=16, k=3

k の値を大きくして、同じことを試してみましょう: k = 3

キーの最小値は 0 ～ 13 です (これが 13 の場合、他の 2 つの値は 14 と 15 になるため)。この最初のセット ビットは非常に簡単に見つけることができます。

したがって、問題を 14 のサブ問題に減らすことができます (すべて k=2 の場合、以前に調査したケースを使用して、それぞれのメモリ使用量を最適化できます)。

  • k=2、n=15 (1 から 15 の間)
  • k=2、n=14 (2 から 15 の間)
  • k=2、n=13 (3 から 15 の間)
  • ...
  • k=2、n=4 (12 から 15 の間)
  • k=2、n=3 (13 から 15 の間)
  • k=2、n=2 (14 から 15 の間なので、可能なケースは 1 つだけです)

私は計算を行っていませんが、これはおそらく最初の単純なソリューションよりもメモリ使用量が優れています。

「シンメトリー」 : n=6, k=4

この si は 6 つの値から 4 つの値を選択するので、選択されていない 2 つの値を決定することと同じであり、メモリの最適化に関する "n=6, k=2" と同様のケースになります。

お役に立てれば。

于 2014-01-21T00:47:52.777 に答える