将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法？

输入格式:

输入在一行中给出待换的零钱数额x∈(8,100)。

输出格式:

要求按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

#include <stdio.h>
int maxCount(int fen,int x);
int main(int argc, const char *argv[])
{
    int X;
    int fen5_maxC,fen2_maxC,fen1_maxC;
    int remain2_1,remain1;
    int total=0,count=0;
    scanf("%d",&X);//13
    if(X>8 && X<100)
    {
        fen5_maxC = maxCount(5,X);//2//分配给5分钱的最大值
        while(fen5_maxC >= 1)
        {
        remain2_1 = X - 5*fen5_maxC;//13-5*2=3//13-5*1=8
        fen2_maxC = maxCount(2,remain2_1);//1//分配给2分钱的最大值//4
            while(fen2_maxC >= 1)
            {
                remain1   = remain2_1 -2*fen2_maxC;//3-2*1=1//8-2*4=0//8-2*3=2
                fen1_maxC = maxCount(1,remain1);//1//分配给1分钱的最大值//0//2
                while(fen1_maxC >= 1)
                {
                    if(fen5_maxC != 0 && fen2_maxC !=0 && fen1_maxC !=0 && (5*fen5_maxC+2*fen2_maxC+fen1_maxC) == X)
                    {
                        count++;
                        total = fen5_maxC + fen2_maxC + fen1_maxC;
                        printf("fen5:%d, fen2:%d, fen1:%d, total:%d\n",fen5_maxC,fen2_maxC,fen1_maxC,total);
                    }
                    fen1_maxC--;
                }
                fen2_maxC--;
            }
        fen5_maxC--;
        }
    printf("count = %d\n",count);
    }
    return 0;
}
int maxCount(int fen,int x)//面值为x的硬币（大面值）可以最多包含面值为fen的硬币（小面值）的数量
{
    int count = 1;
    while(fen*count<=x)
    {
        count++;
    }
    count--;
    return count;
}

思路

此题乍看之下会觉得比较复杂，但仔细观察可以从依次从大到小的顺序发现：我得先找出5分的最大值，在此基础上找出2分的最大值，再找出1分的最大值。每种硬币至少有一枚，那么判断条件就有了：每个硬币的数量不为0，以及硬币组合后总面值为待换面值。然后就是去找循环的条件，其实也不难发现：次小面值的硬币可以兑换成小面值的硬币，那么当小面值的硬币即fen1兑换完后，我只要把一个2分硬币兑换成1分硬币就能多出一种兑换组合。只要最后每种硬币至少有一枚，那么这就是循环条件，循环变量的控制就是不停地往小面值硬币兑换，即循环变量--。

本文链接：https://shengto.top/c/pat_25.html

转载时须注明出处及本声明