人民币问题 （C语言代码）

解题思路:
若钱数为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;
}