Chinaunix首页 | 论坛 | 博客
  • 博客访问: 513845
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1172
  • 用 户 组: 普通用户
  • 注册时间: 2016-06-21 13:40
个人简介

技术改变命运

文章分类

全部博文(184)

文章存档

2020年(16)

2017年(12)

2016年(156)

我的朋友

分类: C/C++

2016-07-06 16:29:06

想兑换100元零钱,有1元,2元,5元,10元四种面值,总共有多少种兑换方法
目前只想到穷举法:

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. int kindofMoney( )
  4. {
  5.     int l1,l2,l5,l10;
  6.     int count = 0;
  7.     for (l1 = 0;l1 <= 100;l1++)
  8.     {
  9.         for (l2 = 0;l2<=50;l2++)
  10.         {
  11.             for (l5 = 0;l5<=20;l5++)
  12.             {
  13.                 for (l10 = 0;l10 <= 10;l10++)
  14.                 if (l1*1+l2*2+l5*5+l10*10 == 100)
  15.                 count++;
  16.             }
  17.         }    
  18.     }
  19.     return count;
  20. }
  21. int main()
  22. {
  23.     int result = kindofMoney();
  24.     printf("%d\n",result);
  25.     return 0;
  26. }
运行结果(centos5.5)
[root@localhost ~]# ./a.out
2156
[root@localhost ~]# 
有种错误的方法代码如下:

点击(此处)折叠或打开

  1. #include<iostream>
  2. using namespace std;
  3. //int count = 0;
  4. long long kindOfMoney(unsigned int n){
  5.     if (n == 0) return 0;
  6.     if (n == 1) return 1;
  7.     if (n == 2) return 2;
  8.     if (n == 3) return 2;
  9.     if (n == 4) return 3;
  10.     if (n == 5) return 4;
  11.     if (n == 6) return 5;
  12.     if (n == 7) return 6;
  13.     if (n == 8) return 7;
  14.     if (n == 9) return 8;
  15.     if (n == 10) return 11;
  16.     return kindOfMoney(n-1)+kindOfMoney(n-2)+kindOfMoney(n-5)+kindOfMoney(n-10);
  17. }
  18. int main(){
  19.     long long result = kindOfMoney(11);
  20.     cout << result << endl;
  21.     //system("pause");
  22.     return 0;
  23. }
错误在1+10和10+1是不同的两种,考虑了顺序
可有更好的办法?
阅读(702) | 评论(0) | 转发(0) |
0

上一篇:跳台阶问题

下一篇:荷兰国旗问题

给主人留下些什么吧!~~