每种硬币不超过100

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

1*100没有超过250，第一层要变

由于5*100已经大于250，所以后面的循环不变

...

...

...

 

#include
/*
//c1是用来存放展开式的系数的，而c2则是用来计算时保存的，
//他是用下标来控制每一项的位置，比如 c2[3] 就是 x^3 的系数。
//用c1保存，然后在计算时用c2来保存变化的值。
*/

const int max=250;
int c1[max+1],c2[max+1];
int main()
{

    int n,i,j,k;
 int deta[]={1,5,10,25,50};
    while(scanf("%d",&n)!=EOF)
    {
        // 计算的方法还是模拟手动运算，一个括号一个括号的计算，
        // 从前往后
        //对于 1+x+x^2+x^3+ 他们所有的系数都是 1
        // 而 c2全部被初始化为0是因为以后要用到 c2[i] += x ;
        for(i=0;i<=100;i++)
        {
            c1[i]=1;
            c2[i]=0;
        }
  for(i=101;i<=250;i++)
        {
            c1[i]=0;
            c2[i]=0;
        }
        //第一层循环是一共有 n 个小括号，而刚才已经算过一个了
        //所以是从2 到  5

        for(i=2;i<=5;i++)
        {
            for(j=0;j<=n;j++)
            {
                for(k=0;k+j<=n;k+=deta[i-1])
                {
                    c2[k+j]+=c1[j];
                }
            }   
            for(j=0;j<=n;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
       printf("%d\n",c1[n]);
    }

    return 0;

}

这条变态题目要求：总硬币数不超过100

这样的话，总数不是很多直接暴力

 

#include<stdio.h>

int main()
{
    int n,u,v,w,x,y;
    while(scanf("%d",&n)!=EOF)
    {
        int count=0;
    for(u=0;u<=100;u++)
        for(v=0;v*5<=n;v++)
            for(w=0;w*10<=n;w++)
                for(x=0;x*25<=n;x++)
                    for(y=0;y*50<=n;y++)
                        if((u+v+w+x+y)<=100 && (u+v*5+w*10+x*25+y*50)==n)
                            count++;

    printf("%d\n",count);

    }

    return 0;
}