给定无限个面值为25分、10分、5分、1分的硬币,计算可以组成n分的组合方式的数目。
思路:
这是一个递归问题。例如n=100,我们先考虑最大的25分硬币。先取0个25分硬币,然后递归去组成100分;接着取1个25分硬币,然后递归去组成75分;接着再取2个25分硬币,然后递归去组成50分,等等。每次取了25分后,再按着相同的思路取10分、5分、1分。
#include <iostream> using namespace std; int MakeChange(int n, int c) { int next = 0; switch (c) { case 25: next = 10; break; case 10: next = 5; break; case 5: next = 1; break; case 1: return 1; } int num = 0; for (int i = 0; i * c <= n; ++i) num += MakeChange(n - i * c, next); return num; } void main() { cout << MakeChange(100, 25) << endl; }