項目歐拉＃31

問題描述：項目歐拉＃31

在英格蘭的貨幣是由英鎊，£和便士，p和有八個硬幣一般循環：
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 
有可能以下列方式使£2：
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p 
多少種方式可以£2使用任意數量的硬幣進行？

我試圖想出我自己的算法，並失敗了。所以，我來到this one（接受的答案）。我試圖在C++中複製它。當我在main（）函數的combos（）中輸入1,2和5時，它會提供正確的答案，但10會返回11，當它應該是12.我的算法出了什麼問題？

#include <iostream> 
#include <cstdlib> 
using namespace std; 

int coin[] = {1, 2, 5, 10, 20, 50, 100, 200}; 

/*Amounts entered must be in pence.*/ 
int combinations(int amount, int size) { 
    int comboCount = 0; 

    if(amount > 0) { 
     if(size >= 0 && amount >= coin[size]) 
      comboCount += combinations(amount - coin[size], size); 
     if(size > 0) //don't do if size is 0 
      comboCount += combinations(amount, size-1); 
    } else if(amount == 0) 
     comboCount++; 

    return comboCount; 
} 

int combos(int amount) { 
    int i = 0; 
    //get largest coin that fits 
    for(i = 7; coin[i] > amount && i >= 0; i--); 
    return combinations(amount, i); 
} 

int main() { 
    cout << "Answer: " << combos(10) << endl; 
    return 0; 
}

來源

2011-07-19 paperbd

的可能重複的[suming具體數目的不同方式來獲得100]（http://stackoverflow.com/questions/6397827/different-ways-of-suming-specific-numbers -to-gain-100） –

那麼，你的代碼可能會返回11，因爲這是正確的答案？

http://ideone.com/uxv4J

來源

2011-07-19 22:35:15

是的。這是我通過手工和程序獲得的。 –

哎呀......是的，顯然10只有11種可能性。 – paperbd

（評論，實際上）：很抱歉，但我只看到10點的組合爲10個便士出的1，2和5：

10p: 0..5*2p + rest*1p  : 6 combinations 
1x5p + 5p, that is 
     0..2*2p + rest*1p  : 3 combinations 
     1*5p     : 1 combination

來源

2011-07-19 22:25:58 ruslik

1x10p硬幣計數，以及5x2p硬幣。 – paperbd

您也可以使用單個10p硬幣，總共11種。 –

對，如果還有10p硬幣，那麼再加一個組合。（最後的組合實際上是2x5p） – ruslik

回答

相關問題