http://blog.csdn.net/mathe/archive/2006/08/31/1147756.aspx 

http://topic.csdn.net/u/20070202/23/65f55fbf-a37c-4e42-82b9-22ebdd573523.html

 

人民币有 1元 2元 5元 10元 20元 50 元 100元  这几种币值.

问:给定200元,求出有多少种币值组合方式.  币种可重复,比如,200张1元的算一种方式. 

一重循环就可以了。 
//result   =   count(50x+20y+10z+5w+2u <=100) 
//assuming   50x+20y+10z=10k, 
//0 <=k <=10 
//We   get   5w+2u <=100-10k,   5x+2y <=k 
//So   the   result   is   
//sum=0; 
//for(k=0;k <=10;k++)   
//   sum+=count(5w+2u <=100-10k)*count(5x+2y <=k); 


根据 
http://blog.csdn.net/mathe/archive/2006/08/31/1147756.aspx 
的结论， 
count(5x+2y <=M) 
可以通过公式计算。 
对于M%10==0 
      E=4M/5 
      S=M*M/20 
I+E=S+1+E/2=M*M/20+1+2M/5 
对于M%10> 0,我们分别还要计算 
      5x+2y=10t+h   (1 <=h <=9)的情况的解的数目。（t> =1) 
对于h为奇数，x必然为奇数，解的数目为不超过[(10t+h)/5]的奇数数目 
对于h为偶数，x必然为偶数，解的数目为不超过[(10t+h)/5]的偶数数目。 


[（10t+h)/5]为2t或2t+1,所以我们得到对于 
h=1,3.   5x+2y=10t+h的解为t个。 
对于h=2,4,5,6,7,8,9,   5x+2y=10t+h的解为t+1个。 
所以对于h=1,2,...,9我们分别需要额外添加的数据为 
h         额外数据 
1             t 
2             2t+1 
3             3t+1 
4             4t+2 
5             5t+3 
6             6t+4 
7             7t+5 
8             8t+6 
9             9t+7 


最终程序可以如下： 
sum=0; 
for(k=0;k <=10;k++){ 
      int   M1,M2; 
      int   t,h; 
      int   s2; 
      M1=100-10*k; 
      M2=k; 
      t=M2/10,h=M2%10; 
      s2=5*t*t+1+4*t; 
      if(h> =1&&h <=2)s2+=h*t+h-1; 
      else   if(h> =3)s2+=h*t+h-2;   //This   part   is   count(5x+2y <=k) 
      sum+=   s2* 
          (M1*M1/20+1+2*M1/5);     //This   part   is   count(5w+2u <=100-10k) 
} 
return   sum;