(ProjectEuler) 求和组合

Question

来自ProjectEuler.net:

问题76：将一百写成至少两个正整数之和的不同方式有多少种？

我不知道如何开始... 可以给点方向或帮助吗？我不需要详细的解答，只需要提示。

例如 5 可以被写为：

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

所以总共有6种可能性。

- koldfyre

---

其实我有一个想法，但不知道如何将其转化为可编程的形式。 - Devoted

看起来您已经找到了一种方法。您直觉地确定了一种可递归枚举的方法。实际上，使用递归会给您提供一个相当优雅的解决方案。注意，通过连接所有可以添加3和所有可以添加2的方式，您已经确定了几种添加5的方式。 - BobbyShaftoe

请提供需要翻译的内容。 - Kevin Davis

是的，请将标题编辑得更具体一些。 - Lance Roberts

整个意义在于自己找到答案，所以这是作弊 :) 但是@Bill the Lizard是正确的。 - vava

啊，这就是如何进入Project Euler前十名的方法！只需在这里发布问题即可！ - Frank

Answer 1

划分数（或划分函数）是解决这个问题的关键。

像这样的问题通常更容易，如果你从底部开始并逐步向上工作，看看能否检测到任何模式。

• P(1) = 1 = {1}
• P(2) = 2 = {[2]，[1 + 1]}
• P(3) = 3 = {[3]，[2 + 1]，[1 + 1 + 1]}
• P(4) = 5 = {[4]，[3 + 1]，[2 + 2]，[2 + 1 + 1]，[1 + 1 + 1 + 1]}
• P(5) = 7 ...
• P(6) = 11 ...
• P(7) = 15 ...
• P(8) = 22 ...
• P(9) = 30 ...

提示：看看是否可以通过前面的结果的某些组合来构建P(N)。

- Bill the Lizard

---

必须喜欢数字 [第三段 - P(10^3) = 190569292] - Peter T. LaComb Jr.

Answer 2

使用切分算法可以找到解决方案。

例如，使用6进行切分。然后我们有：

6
5+1
4+2
3+3

但我们还没有完成。

如果我们将5+1视为一个整体，并考虑+1部分已经完成，因为所有其他的结束组合都由4+2和3+3处理。所以我们需要将同样的技巧应用到5上。

4+1+1
3+2+1

我们可以继续进行下去，但不能盲目地进行。例如，4+2会产生3+1+2和2+2+2。但我们不需要3+1+2，因为我们将有一个3+2+1。因此，我们只使用所有4的乘积，其中最低数大于或等于2。

6
5+1
  4+1+1
    3+1+1+1
      2+1+1+1+1
        1+1+1+1+1+1
    2+2+1+1
  3+2+1
4+2
  2+2+2
3+3

下一步是将其放入算法中。

好的，我们需要一个递归函数，它需要接受两个参数：要被切割的数字和最小值：

func CountCombinations(Number, Minimal)
  temp = 1
  if Number<=1 then return 1
  for i = 1 to Floor(Number/2)
    if i>=Minimal then
      temp := temp + CountCombinations(Number-i, i)
  end for
  return temp
end func

检查算法：

C(6,1) = 1 + C(5,1) + C(4,2) + C(3,3) = 11, which is correct.
C(5,1) = 1 + C(4,1) + C(3,2) = 7
C(4,1) = 1 + C(3,1) + C(2,2) = 5
C(3,1) = 1 + C(2,1) = 3
C(2,1) = 1 + C(1,1) = 2
C(1,1) = 1
C(2,2) = 1
C(3,2) = 1
C(4,2) = 1 + C(2,2) = 2
C(3,3) = 1

顺便说一下，100的组合数：

CC(100) = 190569292
CC(100) = 190569291 (if we don't take into account 100 + 0)

- Gamecat

---

我认为OP是在寻求提示而不是答案本身。 - Tim

你能用 PHP 帮我解决这个问题吗？因为我不懂这种编程语言，特别是不知道“:”代表什么。 - Seder

Answer 3

处理这些问题的好方法不是纠结于“100”，而是尝试考虑求和总数为 n 和 n+1 之间的差异，通过寻找随着 n 增加而出现的模式来实现。

我现在可以试一下，但我有工作要做 :)

- Paul Dixon

Answer 4

一种方法是考虑递归函数：找到从正整数中抽取的数字系列的排列，这些排列允许重复，并且它们加起来等于100。

• 零是1，即对于数字1没有解决方案
• 单位是2，即对于数字2只有一种解决方案

另一种方法是考虑生成函数：从零开始找到排列系列，直到目标值，保留中间值和计数的映射/哈希表。

你可以从1开始迭代，或者从100开始递归；无论哪种方式，你都会得到相同的答案。在每个点上，你可以（对于一个朴素的解决方案）生成所有正整数系列的排列，它们计数达到目标数字减1，并且仅计算那些加起来等于目标数字的组合。

祝你好运！

- Steven A. Lowe

Answer 5

像Project Euler中大数问题一样，最好的思考方式不是被那个巨大的上限难住，而是从更小的角度考虑问题，并逐步提高。也许，在解决问题的过程中，你会发现一个模式或者学到足够的知识，轻松地得出答案。

我唯一能给你的提示是“分区”。

一旦你弄清楚了这点，就很快可以得出答案 :)

- sykora

Answer 6

注意：我的数学有点生疏，但希望这可以帮到你...

你在很好地分解问题。

思考一般情况：

• 一个数字 n 可以写成 (n-1)+1 或者 (n-2)+2
• 你可以将其推广为 (n-m)+m
• 记住以上规律同样适用于所有数字（包括 m）

所以，想法是找到第一个集合（假设 5 = (5-1)+1），然后将 (5-1) 视为新的 n...5 = 4 +1...5 = ((4-1)+1)+1。一旦这个集合用完了，就从 5 = 3 + 2 开始...变成 5 = ((3-1)+1)+2....= 2+1+2....在沿途分解每个数字。

- Jamie

Answer 7

许多数学问题可以通过归纳法来解决。您知道特定值的答案，如果您找到将n与n+1联系起来的某些内容，您就可以找到每个值的答案。

例如，在您的情况下，您知道一个正整数至少可以用两个正整数相加的方式表示的不同方法有多少种？的答案只是1。

我所说的n和n+1之间的联系是什么意思呢？我的意思是您必须找到一个公式，只要您知道n的答案，您就可以找到n+1的答案。然后，递归调用该公式，您将知道答案并完成了（注意：这只是数学部分，在现实生活中，您可能会发现这种方法太慢而无法实际使用，因此您还没有完成 - 在这种情况下，我认为您将完成）。

现在，假设你知道n可以被写成至少两个正整数的和，有k种不同的方式，其中一种是：

n=a1+a2+a3+...am（这个和有m项）

关于n+1，你能说什么呢？由于我只想给你一些提示，所以我不会在这里写出解决方案，只会写下接下来的内容。当然，你肯定有相同的k种不同的方式，但在每种方式中都会有一个+1项，其中一种是：

n+1=a1+a2+a3+...am+1（这个和有m+1项）

那么，你当然还有其他k种可能性，例如每个和的最后一项不相同，但会增加一项，如：

n+1=a1+a2+a3+...(am+1)（这个和有m项）

因此，至少有2k种将n+1写成至少两个正整数之和的方式。好吧，还有其他的方式。如果你能找到它们，就去试试吧 :-)

- Davide