将一笔零钱换成5分、2分和1分的硬币,要求每种硬币至少有一枚,有几种不同的换法?
输入格式:
输入在一行中给出待换的零钱数额8。
输出格式:
要求按5分、2分和1分硬币的数量依次从大到小的顺序,输出各种换法。每行输出一种换法,格式为:“fen5:5分硬币数量, fen2:2分硬币数量, fen1:1分硬币数量, total:硬币总数量”。最后一行输出“count = 换法个数”。
输入样例:
13
输出样例:
fen5:2, fen2:1, fen1:1, total:4 fen5:1, fen2:3, fen1:2, total:6 fen5:1, fen2:2, fen1:4, total:7 fen5:1, fen2:1, fen1:6, total:8 count = 4
1 #include<stdio.h> 2 #include<math.h> 3 #include<stdlib.h> 4 #include<string.h> 5 int main() { 6 int f5 = 1, f2 = 1, f1 = 1; //定义f5,f2,f1的个数,最少是1个 7 int x = 0; //总数x 8 int cout = 0; //总次数 9 scanf("%d", &x); 10 f5 = x / 5; 11 for (; f5 > 0; f5--) { //大循环,根据f5的个数逐步递减(题上说是f5递减的) 12 f1 = 1; //可以肯定的是,f1的个数在f5定了的情况下是递增的,f2是最后算出来的 13 for (; f2 > 0;f1++) { //算f2 14 if ((f5 * 5 + f2 * 2 + f1) > x) { //判断他们和是否超过x,如果超过,就说明这种个数的5分硬币已经用完了 15 break; 16 } 17 f2 = (x - f5 * 5 - f1) / 2; 18 if ((x - f5 * 5 - f1) % 2 == 0) { //如果f2不是整数,就不输出 19 printf("fen5:%d, fen2:%d, fen1:%d, total:%d ", f5, f2, f1, f1 + f2 + f5); 20 cout++; 21 } 22 f2 = 1; //f2还原,因为如果不还原,上面判断是否退出循环时是有问题的 23 } 24 } 25 printf("count = %d ", cout); 26 return 0; 27 }
注释已经说明了一些情况。
再解释一下自己的思路:根据题目要求,5分硬币是从最多到最少的,所以我们首先要算的就是5分的,这种情况也是最简单的,直接除法就可以了。
接着就会进入陷阱,题上说,5分硬币是首要,2分是次要,1分是最最次要,但是呢,我们该如何管理这个2分硬币,会发现无从下手,所以就只能从1分硬币下手。
1分硬币在5分硬币定了的前提下,它一定是逐渐增加的!!!我们可以根据这个来定2分硬币
于是就有上述代码了,至于里面的判断条件之类的,都可以理解啦!