tsaiwn dynamic % cat -n coin0.c
     1  #include <stdio.h>
     2      /* greedy */
     3  int nct;   /* number of coin type */
     4  int vct[33], nc[33];    /* value of coin,  number of each coin */
     5  int ncoins;  /* min. number of coins for the change */
     6  void getCoinData(), printResult();
     7  int ask(), makeChange(int);
     8  int main(){
     9      int money, i;
    10      getCoinData();
    11      money=ask();
    12      while(money > 0){
    13          for(i=1; i<= nct; ++i) nc[i] = 0;  ncoins=0; /* clear */
    14          ncoins = makeChange(money);
    15          printResult();
    16          money=ask();
    17      }
    18      return 0;
    19  }
    20  void getCoinData(){
    21      int i, tmp[] = { 0, 1, 5, 10, 25, 50 };
    22      nct = sizeof(tmp) / sizeof(int) - 1;
    23      for(i=1; i<= nct; ++i) {
    24         vct[i] = tmp[i];
    25      }
    26  }
    27  int ask(){
    28      char tmp[99];
    29      printf("How much of the change? ");
    30      gets(tmp); 
    31      return (int)atol(tmp);
    32  }
    33  int makeChange(int m){
    34      int i, nthis;
    35      int nmin = 0;   /* number of min. coin */
    36      i = nct;   /* the max one */
    37      while(m){
    38          if(m >= vct[i]) {
    39              nthis = m / vct[i];
    40              nc[i] += nthis;
    41              nmin += nthis;
    42              m -= nthis * vct[i];   /* remain money */
    43          }
    44          --i;
    45      }
    46      return nmin;
    47  }
    48  void printResult(){
    49      int i;
    50      printf("Total number of coins required: %d\n", ncoins);
    51      for(i=nct; i>0; --i){
    52          if(nc[i]){
    53              printf("\t%d  x %2d\n", nc[i], vct[i]);
    54          }
    55      }
    56      printf("\n");
    57  }
tsaiwn dynamic % gcc  coin0.c
/var/tmp/ccj314Z4.o: In function `ask':
/var/tmp/ccj314Z4.o(.text+0x10a): warning: this program uses gets(), which is unsafe.
tsaiwn dynamic % ./a.out
warning: this program uses gets(), which is unsafe.
How much of the change? 1
Total number of coins required: 1
        1  x  1

How much of the change? 2
Total number of coins required: 2
        2  x  1

How much of the change? 63
Total number of coins required: 5
        1  x 50
        1  x 10
        3  x  1

How much of the change? 67
Total number of coins required: 5
        1  x 50
        1  x 10
        1  x  5
        2  x  1

How much of the change? 0
tsaiwn dynamic %