1.6 贪婪算法

hncys

　　换零钱问题



1 #include <stdio.h>
2 #define MAXN 9
3 int parvalue[MAXN]={10000,5000,1000,500,200,100,50,20,10};
4 int num[MAXN]={0};
5 int exchange(int n)
6 {
7     int i,j;
8     for(i=0;i<MAXN;i++)
9         if(n>parvalue) break; //找到比n小的最大面额
10     while(n>0 && i<MAXN)
11     {
12         if(n>=parvalue)
13         {
14             n-=parvalue;
15             num++;
16         }else if(n<10 && n>=5)
17         {
18             num[MAXN-1]++;
19             break;
20         }else i++;   
21     }
22     return 0;
23 }
24
25 int main()
26 {
27     int i;
28     float m;   
29     printf ("请输入找零的金额: " );
30     scanf("%f",&m);
31     exchange((int)100*m);
32     printf("\n%.2f元零钱的组成：\n",m);
33     for(i=0;i<MAXN;i++)
34         if(num>0)
35             printf("%6.2f：%d张\n",(float)parvalue/100.0,num);           
36     getch();
37     return 0;
38 }