0

それほど難しいことではないはずですが、私はこれでちょっと立ち往生しています。Cで関数を作成する必要があります。これは、指定された数値のすべての可能な組み合わせ（繰り返しなし）を計算して表示します。すべての組み合わせの数字（1から9の範囲のみ）は、追加すると指定された合計になります。

これはあまり明確な説明ではないと思うので、例を示します: 合計が 28 になる 5 つの数字 (1 から 9) のすべてのセットを計算します。

誰かがこれを説明できれば、本当に感謝しています。

4

1 に答える 1

1

512 の異なる選択肢しかないため、結果を簡単に事前計算できます。

事前計算するには:

  • という名前の空のマップ(sum => set(set(digit)))を準備しますlookup。
  • subset(1..9) ごとに
    • その を計算しsumます。
    • lookupにキーがない場合はsum、空のセットである新しいエントリを作成します。
    • subsetに追加lookup[sum]

をルックアップするにはsum:

  • lookupkey がある場合はsum、エントリ (のコピー) を返します。それ以外の場合は、空のセットを返します。

C の低レベル性に対処するには:

マップ int=>x は単なる配列です。x のセットは、単純に配列 + 長さでもあります。

マップの配列は、最大のキーである 45 が既にわかっているため、静的として割り当てることができます。

セットの最大セットを事前に見積もることも、動的割り当てを使用することもできます (より効率的です)。スペースを気にしない場合は、簡単に過剰に割り当てることができます (最大 512 エントリ)。これほど過剰に割り当てたくないと思うので、動的に割り当てる方法を学ぶこともできます。

一連の数字は、9 ビットのビット マスク (メモリでは 16 ビット) として表すことができます。次に、それらを列挙するのは簡単です。

の実際のタイプのスケッチlookup:

typedef setOfDigits int16;

struct setOfSets{
  setOfDigits* data;
  int16 count; //the actual amount of sets in the set
  int16 space; //the size of the allocated array
}

setOfSets lookup[46];

lookup動的割り当てまたは s を使用しないの実際のタイプのスケッチstruct:

int16 lookup[46][512];
int16 lookupLength[46];

space:=countを等式にすると、過剰に割り当てられることはありませんが、頻繁に再割り当てされることに注意してください。これは、実装が簡単ですが、非効率的である可能性があります (ただし、コードは 1 回実行されるため、ねえ)

もちろん、高級言語 (および C++ でさえも) には、ネイティブ (javascript) または標準ライブラリ (C++、Java) を介して動的配列があります。C では、に依存する必要がありますrealloc。

于 2012-12-02T12:18:34.637 に答える