0

虽然它不应该真的很困难，但我一直坚持这一点。我需要在 C 中创建一个函数，计算并显示给定数字的所有可能组合（不重复），其中每个组合的数字（仅从 1 到 9）在相加时给出指定的总和。

我想这不是最清楚的解释，所以这里有一个例子：计算所有 5 个数字（从 1 到 9）的集合，加起来为 28。

如果有人能解释这一点，我将不胜感激。

4

1 回答 1

1

由于只有 512 种不同的选择，您可以轻松地预先计算结果。

预计算：

  • 准备一张空地图(sum => set(set(digit)))，命名为lookup.
  • 对于subset(1..9) 中的每一个
    • 计算其sum.
    • 如果lookup没有 key sum，则创建一个新条目，一个空集。
    • 添加subset到lookup[sum]

要查找sum：

  • 如果lookup有 key sum，则返回（副本）该条目。否则返回一个空集。

为了解决 C 的一些低级问题：

map 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，没有动态分配或structs：

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

请注意，如果您 equate space:=count，那么您永远不会过度分配，但您经常重新分配，这更容易实现但可能效率低下（但代码运行一次，所以嘿）

当然，高级语言（甚至 C++）本身具有动态数组（javascript）或通过标准库（C++、Java）。在 C 中，您必须依赖realloc.

于 2012-12-02T12:18:34.637 回答