首页 > 代码库 > 1025:统计硬币
1025:统计硬币
题目描述
假设一堆由1分、2分、5分组成的n个硬币总面值为m分，求一共有多少种可能的组合方式（某种面值的硬币可以数量可以为0）。
输入格式
输入数据第一行有一个正整数T，表示有T组测试数据。接下来的T行，每行有两个数n，m，n和m的含义同上。
输出
对于每组测试数据，请输出可能的组合方式数，每组输出占一行。
样例输入
2
3 5
4 8
样例输出
1
2
本题的思路类似于鸡兔同笼问题，所以不难想到使用几个for循环对可能值进行穷举，下面是我写的一个算法，在穷举上略有优化。
1 #include <stdio.h> 2 int main(void) 3 { 4 int n,m; 5 int time; 6 7 scanf("%d",&time); 8 while(time--) 9 { 10 11 int count=0;12 scanf("%d %d",&n,&m);13 int i,j,k,total;14 15 for(i=0;i<=(m/5);i++)16 {17 18 for(j=0;j<=(m/2);j++)19 {20 k=n-j-i; 21 total=k*1+j*2+i*5;22 if(total==m)23 count++;24 }25 26 }27 printf("%d\n",count);28 }29 return 0;30 }
提交后仍有错误，暂未发现在何处。下面是官方的算法，较之又有一些优化。
1 #include<stdio.h> 2 3 int main() 4 { 5 int t,n,m,c1,c2,c5,k; 6 scanf("%d",&t); 7 while(t--) 8 { 9 scanf("%d%d",&n,&m);10 k=0;11 for(c5=0;5*c5<=m;c5++)12 for(c2=0;2*c2+5*c5<=m;c2++)13 {14 c1=m-5*c5-2*c2;15 if(c1+c2+c5==n)16 k++;17 }18 printf("%d\n",k);19 }20 return 0;21 }
另外值得一提的是，本题与1023——坑爹的黑店在算法上有异曲同工之妙。
另：之后又根据官方修改，仍是不过。奇怪。
1 #include <stdio.h> 2 int main(void) 3 { 4 int n,m; 5 int time; 6 7 scanf("%d",&time); 8 while(time--) 9 { 10 11 int count=0;12 scanf("%d %d",&n,&m);13 int i,j,k,total;14 15 for(i=0;5*i<=m;i++)16 {17 18 for(j=0;2*j<=m;j++)19 {20 k=n-j-i; 21 total=k*1+j*2+i*5;22 if(total==m)23 count++;24 }25 26 }27 printf("%d\n",count);28 }29 return 0;30 }
最后终于发现问题，关于k=n-i-j;因为对于i,j的初始没有限制，所以k可能是负值的情况没有排除。
下面代码AC
1 #include <stdio.h> 2 int main(void) 3 { 4 int n,m; 5 int time; 6 7 scanf("%d",&time); 8 while(time--) 9 { 10 11 int count=0;12 scanf("%d %d",&n,&m);13 int i,j,k,total;14 15 for(i=0;5*i<=m;i++)16 {17 18 for(j=0;2*j<=m;j++)19 {20 k=n-j-i; 21 total=k*1+j*2+i*5;22 if(total==m&&k>=0)23 {24 25 count++;26 }27 28 }29 30 }31 printf("%d\n",count);32 }33 return 0;34 }
1025:统计硬币
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。