6

可能重复：
作为素数部分的数字

我有这个家庭作业，很难，我必须得到给定数字的所有不同的素数分区。例如，数字 7 有五个不同的素数分区（或表示它拥有的 2 个素数分区的五种不同方式）：

  • 5 + 2
  • 2 + 5
  • 3 + 2 + 2
  • 2 + 3 + 2
  • 2 + 2 + 3

如您所见，如果它是素数，则数字本身被排除在外。我不必打印所有不同的分区，只需打印它们的数量。

所以我对此有点迷茫。我完全无法生成任何代码，但我认为我应该从动态编程的角度来处理这个问题。我只是要求一些提示。有人有想法吗？提前致谢。

输入的最大数字为100。另外，程序的运行时间不能超过1秒，内存限制为128 MB。

4

4 回答 4

2

要解决这个问题，您需要结合三个想法：

假设给定的数字是 n：

  • 找到所有小于 n 的素数，如此处所示。

  • 从您的素数数组和 n 动态计算子集总和。这里和这里有一些提示

  • 然后，计算从第二步得到的每个答案的不同排列的数量，如下所示。

当然，这只是一个提示。但它应该对您编写最终代码有很大帮助。

于 2013-01-18T15:23:53.937 回答
1

您可能想查看Wikipedia上的分区数学，特别是在页面中间的生成函数和受限分区生成函数部分。它提到了由特定加数（由自然数集 T 指定）组成的分区的生成函数。

令数 n 的非顺序依赖素数分区的数量为 R(n)。您可以通过对 x 取第 n 个偏导数并设置 x = 0 从生成函数导出 R(n)。这可能并不容易。

一个警告：这些分区不依赖于顺序（即 1 + 2 和 2 + 1 仅计为一个分区）。

于 2013-01-18T12:56:44.697 回答
1

因此，以提示而不是答案的形式：

  • 正如其他地方所说，您可以预先计算素数。
  • 您可以重复使用较小数字的结果吗？那么，假设您知道 5 的实际排列，这是否有助于您找到 7 的任何实际排列？
  • 结果是否有任何结构，如果有，您可以使用该结构来避免重复计算吗？例如，您列出了数字 7 的 5 个排列，但它们彼此之间表现出一些相似性 - 这是一个普遍趋势，它是什么？
  • 假设您找到了内部结构并且可以使用较小的结果来帮助找到较大的结果，您可以两者都做吗 - 您可以完全避免存储完整的中间结果吗？
  • 最后，您需要列出每个有序组合还是只返回有序组合的数量？您可以在此处节省计算。
于 2013-01-18T12:18:27.133 回答
1

不幸的是，您不能在这里过多地提高蛮力。您绝对应该做的一件事是使用Eratosthenes 筛子预先计算所有素数，直到给定数字。之后，给定一个数字 N 递归打印其所有分区，其中最小的素数是连续素数列表中的每个素数（记住让它是最小的，这样你就不会重复分区）。

编辑：知道你只需要知道分区的数量后：最好的解决方案是使用动态编程。同样，您需要在一个数组中记忆一个二维mem[MAX_SIZE][MAX_SIZE]第一个索引是您正在计算解决方案的数字，第二个索引是您应该用于分区的最小素数的索引。

于 2013-01-18T12:01:09.180 回答