项目欧拉＃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

回答

相关问题