想兑换100元零钱,有1元,2元,5元,10元四种面值,总共有多少种兑换方法
目前只想到穷举法:
-
#include<stdio.h>
-
#include<stdlib.h>
-
int kindofMoney( )
-
{
-
int l1,l2,l5,l10;
-
int count = 0;
-
for (l1 = 0;l1 <= 100;l1++)
-
{
-
for (l2 = 0;l2<=50;l2++)
-
{
-
for (l5 = 0;l5<=20;l5++)
-
{
-
for (l10 = 0;l10 <= 10;l10++)
-
if (l1*1+l2*2+l5*5+l10*10 == 100)
-
count++;
-
}
-
}
-
}
-
return count;
-
}
-
int main()
-
{
-
int result = kindofMoney();
-
printf("%d\n",result);
-
return 0;
-
}
运行结果(centos5.5)
[root@localhost ~]# ./a.out
2156
[root@localhost ~]#
有种错误的方法代码如下:
-
#include<iostream>
-
using namespace std;
-
//int count = 0;
-
long long kindOfMoney(unsigned int n){
-
if (n == 0) return 0;
-
if (n == 1) return 1;
-
if (n == 2) return 2;
-
if (n == 3) return 2;
-
if (n == 4) return 3;
-
if (n == 5) return 4;
-
if (n == 6) return 5;
-
if (n == 7) return 6;
-
if (n == 8) return 7;
-
if (n == 9) return 8;
-
if (n == 10) return 11;
-
return kindOfMoney(n-1)+kindOfMoney(n-2)+kindOfMoney(n-5)+kindOfMoney(n-10);
-
}
-
int main(){
-
long long result = kindOfMoney(11);
-
cout << result << endl;
-
//system("pause");
-
return 0;
-
}
错误在1+10和10+1是不同的两种,考虑了顺序
可有更好的办法?
阅读(717) | 评论(0) | 转发(0) |