[关闭]
@songpfei 2016-05-13T10:01:24.000000Z 字数 866 阅读 900

找零钱

  1. 列表项

OJ_算法


找零钱
描述:
我们知道人民币有1、2、5、10、20、50、100这几种面值。现在给你n(1≤n≤250)元,让你计算换
成用上面这些面额表示且总数不超过100张,共有几种。比如4元,能用4张1元、2张1元和1张2元、2张2元,
三种表示方法。
题目类别: 循环
难度: 初级
分数:
运行时间限制: 10 Sec
内存限制: 128 MByte
阶段: 招聘管理
输入:
输入有多组,每组一行,为一个整合n。输入以0结束。
输出:
输出该面额有几种表示方法。
样例输入:
1
4
0
样例输出:
1
3

解析:
找钱的面值只有7种:1,2,5,10,20,50,100;当输入一个n值介于某两个面值之间时,如n=25,则n介于20到50之间,那么所找钱的最大值为20;利用递归的思想,此时找钱的方法数可分为两类,一类是包含20面值,另一类是不包含20,利用加法原理,将两类相加即可,而对于这两类还可以继续分,对于包含20的,那么面值此时变成了n-20=5;对于不包含20的,则所找的面值最大为10块,这样递归下去;

    递推式为:find(n,i)=find(n-RMB[i],i)+find(n,i-1);

其中RMB[]={1,2,5,10,20,50,100};,i是指向第一个小于等于n值的RMB[i]的下标。

  1. #include<iostream>
  2. using namespace std;
  3. /*
  4. */
  5. static int RMB[]={1,2,5,10,20,50,100};
  6. int find(int n,int i)
  7. {
  8. if(n<=1 || RMB[i]==1)return 1;
  9. return find(n-RMB[i],i)+find(n,i-1);
  10. }
  11. int main()
  12. {
  13. int n;
  14. int i;
  15. while(cin>>n && n!=0)
  16. {
  17. for(i=6;i>=0 && n<RMB[i];i--);
  18. cout<<find(n,i)<<endl;
  19. }
  20. return 0;
  21. }

考虑如何打印出所有可行解?

参考:http://blog.csdn.net/wumuzi520/article/details/7837143

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注