(ProjectEuler)Sum Combinations

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

分区号(或分区函数)是这一点的关键.

如果从底部开始并逐步查看是否可以检测到任何模式,这些问题通常会更容易.

• 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)之前的某些结果组合中建立P(N).

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)