計算求和的方法N

Question

對於任何非負的整數K，假設我們恰好有兩個值爲2^K的硬幣（即兩個K的冪）。

現在我們給出一個很長的N.我們需要找到我們用硬幣代表N值的不同方式的數量。

（兩個表示被認爲是不同的，如果存在着發生在所述表示不同數量的倍的值。）

實施例：設N = 6，然後回答是3爲以下三個表示在此是可能的case：

{1, 1, 2, 2} 
{1, 1, 4} and 
{2, 4} 

如何做到這一點，如果N可以達到10^18？

Answer 1

我們可以從一個簡單的解決方案開始，我們有一個2和其餘的1。當然，這需要N至少爲3。否則，有沒有辦法解決：

coins1 = N - 2 
coins2 = 1 
nSolutions = 1 

讓我們先來討論發現的M等於硬幣可能的合併操作的數量的任務，其中的每一個硬幣必須合併（即只使用一種硬幣類型）。這是M可能的整數除數2。此過程可以緩存中間結果以更快地執行後續調用（請參閱動態編程）。

但這有用嗎？在目前的狀態下，我們現在可以隨後交換兩個1's一個2。這可以完成，直到不再有兩個1's，總共floor(N/2 - 1)次。每次合併後（實際上每次合併後都足夠了），我們必須檢查所有2's可以合併的頻率。還有在國家1's，所以我們不能使用其他類型的硬幣：

while(coins1 >= 3) 
{ 
    coins1 -= 2; 
    coins2 += 1; 
    nSolutions += 1; 
    nSolutions += findNumberOfMerges(coins2); //this could be improved 
} 

如果while留，有一個或兩個1's左側。如果剩下一個，我們就完成了，因爲這個必須始終存在，我們已經檢查了所有可能的組合，以不同的方式表示2's。

if(coins1 == 1) 
    return nSolutions; 

在另一種情況下，我們可以再次合併。但是，這不會導致有效的狀態，因爲沒有第二種硬幣類型。但是，我們可以合併一次，以獲得一個有效的狀態（即一個4（成爲coins2），其餘2's（成爲coins1））：

coins1 = coins2 + 1 - 2; 
coins2 = 1; 
nSolutions += 1; 

現在我們有一個類似的狀態，在一開始，這樣我們就可以運行整個程序再次。再一次，直到它返回。