解题思路:
若钱数为a,都换成5元最多有i=a/5张,都换成2元最多有j=a/2张,都换成1元最多有a张,在三种钱币的取值范围内循环,若总价值等于a,就能找到符合要求的钱币张数。转化成代码就是:
#include<stdio.h> int main(){ int a,i,j,k,x,y,z,c=0; scanf("%d",&a); i=a/5;j=a/2;k=a; for(x=1;x<i;x++) for(y=1;y<j;y++) for(z=1;z<k;z++) if(x*5+y*2+z==a)//若总价值等于a c++; //找到符合要求的一种组合 printf("%d",c); return 0; }
按照上述方法,输入总价值10000,好久都没有得到结果,看来该算法有待优化,首先,每种钱币至少有一张,那么5元的张数最多有x=(n-2-1)/5,用i来表示5元的张数,i的取值范围是[1,x],限定了5元的张数后,2元的张数最多有y=(n-5*i-1)/2,用j来表示2元的张数,j的取值范围是[1,y],既然限定了5元和2元的张数,那么1元的张数就等于z=n-5*i-2*j,只要这个值大于0就符合要求。
注意事项:
每种钱币至少有一张,再根据价值和不超过已知的总价值,逐步执行优化。
参考代码:
#include<stdio.h> int main(){ int n,i,j,x,y,z,c; while(~scanf("%d",&n)){ c=0; x=(n-2-1)/5; //减去2元和1元的价值,除以5得5元张数 for(i=1;i<=x;i++){ y=(n-5*i-1)/2; //减去5元和1元的价值,除以2得2元张数 for(j=1;j<=y;j++){ z=n-5*i-2*j; //减去5元和2元的价值,得1元的张数 if(z>0) c++; //只要1元的张数大于0就符合要求 } } printf("%d\n",c); } return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1046 |
C语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1666 |
哥德巴赫曾猜测 (C语言代码)浏览:1093 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:567 |
WU-链表数据求和操作 (C++代码)浏览:1366 |
IP判断 (C语言描述,蓝桥杯)浏览:1108 |
简单的a+b (C语言代码)浏览:488 |
C语言训练-排序问题<1> (C语言代码)浏览:363 |
孤独的骑士 (C语言代码)浏览:1409 |
简单的a+b (C语言代码)浏览:487 |