（歐拉計劃）總和的組合

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作爲至少兩個正整數的總和。那麼還有其他的。找出來，如果你可以:-) 並享受:-)）