几个月前,我找到了一段代码,我正在编写面试.
根据我的评论,它试图解决这个问题:
给定一美分的美分价值(例如200 = 2美元,1000 = 10美元),找到构成美元价值的所有硬币组合.只有便士(1¢),镍(5¢),角钱(10¢)和四分之一(25¢).
例如,如果给出100,答案应该是:
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
我相信这可以通过迭代和递归方式解决.我的递归解决方案非常错误,我想知道其他人如何解决这个问题.这个问题的难点在于尽可能提高效率.
我试图实现一个硬币问题,问题规范是这样的
创建一个函数来计算可用于给定金额的所有可能的硬币组合.
All possible combinations for given amount=15, coin types=1 6 7
1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2) 1,1,1,1,1,1,1,1,1,6,
3) 1,1,1,1,1,1,1,1,7,
4) 1,1,1,6,6,
5) 1,1,6,7,
6) 1,7,7,
功能原型:
int findCombinationsCount(int amount, int coins[])
假设硬币阵列已排序.对于上面的例子,这个函数应该返回6.
任何人都指导我如何实现这个？