（欧拉计划）总和的组合

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种可能性总数。

Answer 1

Partition Numbers（或分区功能）是重要的关键之一。

像这样的问题通常会比较容易，如果您从底部开始并按照您的方式查看是否可以检测到任何模式。

• P（1）= 1 = {1}
• P（2）= 2 = {[2]，[1 + 1]}
• P（3）= 3 = {[3- （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）向上从之前P（N）的结果的一些组合。

Answer 2

接近这些的一个好方法是进不去迷恋上了“100”，但尽量考虑总额的总和之间的差异ñ和N + 1会是什么，通过寻找模式当n增加1,2,3 ....

我必须现在走，但我有工作要做:)

Answer 3

注意：我的数学是有点生疏，但希望这将有助于...

你正在顺利解决问题。

认为一般：

• 若干Ñ可以写为（n-1）+1或第（n-2）+2
• 您概括这对（NM）+米
• 记住上面也适用于所有数字（包括M）

这样的想法是找到第一套（可以说5 =（5-1）+1），然后治疗（5-1 ）作为新的n ... 5 = 4 +1 ... 5 =（（4-1）+1）+1。 5 =（（3-1）+ 1）+2 .... = 2 + 1 + 2 ......的5 = 3 + 2 ....再次开始耗尽随你走。

Answer 4

就像Euler项目中的大部分问题一样，考虑它们的最佳方式不是被这个巨大的上限所困扰，而是从较小的角度思考问题，并逐步向上推进。也许，在你认识一种模式的途中，或者学习到足以让你轻松回答问题的答案。

我想我可以给你的唯一的其他提示，而不会破坏你的顿悟，就是'分区'这个词。

一旦你想通了这一点，你就会有它在任何时候:)

Answer 5

一种方法是考虑递归函数：找到从正整数（允许重复），加起来就是100

• 零为1，即对于1号绘制的数字系列的排列有非零解
• 单位为2，即对于2号只有一个溶液

另一种方法是考虑生成功能：从零开始，找到排列序列直至目标，保留地图/散列值或中间值并计数

您可以从1迭代或从100递减;无论哪种方式，你都会得到相同的答案。在每一点上，你都可以（对于一个天真的解决方案）产生一系列正整数的排列，直到目标数减1，并且只计算那些加起来到目标数的那些排列。

祝你好运！

Answer 6

解决方案可以使用斩波算法找到。

使用例如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) 

Answer 7

许多数学问题可以通过induction来解决。 你知道具体价值的答案，并且你可以找到每个价值的答案，如果你发现东西链接n与n+1。

例如在你的情况下，你知道的答案有多少种不同的方法可以写成至少两个正整数的和？只是1.

我的意思是n和n+1之间的链接？我的意思是，你必须找到一个公式，告诉你n的答案，你会找到n+1的答案。然后，递归调用这个公式，你就会知道答案，并且你已经完成了（注意：这只是它的数学部分，在现实生活中你可能会发现这种方法会给你太慢而不实际的东西，所以你还没有完成 - 在这种情况下，我认为你会完成）。

现在，假设你知道n可以写成作为至少两个正整数的总和吗？在k不同的方式，其中之一是：

N = A1 + A2 + A3 + ...上午（这笔钱有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作为至少两个正整数的总和。那么还有其他的。找出来，如果你可以:-) 并享受:-)）