/*----------------------------------------------------------------------
  File    : change2.c
  Contents: compute the number of ways to change a given amount of money
            (improvement on the program by Martin Kersten)
  Author  : Christian Borgelt
  History : 14.12.1997 file created
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define UNITCNT  15             /* number of money units */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
const int unitvals[UNITCNT] = { /* money unit values */
       1,     2,     5,         /*    1,   2 and   5 Pfennig */
      10,           50,         /*   10      and  50 Pfennig */
     100,   200,   500,         /*    1,   2 and   5 DM */
    1000,  2000,  5000,         /*   10,  20 and  50 DM */
   10000, 20000, 50000,         /*  100, 200 and 500 DM */
  100000                        /* 1000              DM */
};

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

double count (int amount)
{                               /* --- compute number of ways to */
                                /*     change the amount `amount' */
  int    i;                     /* loop variable */
  int    cnts[UNITCNT];         /* money unit counters */
  double n = 1;                 /* number of ways to change amount */

  for (i = UNITCNT; --i > 0; ) cnts[i] = 0;
  cnts[0] = amount;             /* start with smallest units only */
  while (++i < UNITCNT) {       /* traverse units > smallest unit */
    if (unitvals[i] <= cnts[0]) {  /* if one more unit i is possible */
      cnts[0] -= unitvals[i];   /* replace unitvals[i] smallest units */
      cnts[i]++;                /* by one money unit i, */
      n += 1;                   /* count the way found, */
      i  = 0; }                 /* and restart the loop */
    else {                      /* if no more units i are possible */
      cnts[0] += cnts[i] *unitvals[i];
      cnts[i]  = 0;             /* change the amount in money units i */
    }                           /* back to the smallest unit and */
  }                             /* continue with the next money unit */
  return n;                     /* return computed number of ways */
}  /* count() */

/*----------------------------------------------------------------------
This function uses the same idea as the program by Martin Kersten.
It keeps the current combination of money units in a vector `cnts' and
uses a loop to construct all possible combinations by working on this
vector, i.e. by constructing a new combination from the current one.
The idea is as follows: We start with smallest money units only, i.e.
with `amount' Pfennigs. Then we start the loop to traverse the money
units larger than the smallest unit. In the loop we test whether we can
increase the number of money units i by one. If this is possible, we
can construct a new way to change the amount by replacing an equivalent
number of smallest units by one of the current unit. We count this way
and then we restart the loop, i.e. we go back to the second smallest
money unit. This is necessary, since after we increased the number of
money units other than the second smallest, we have to test whether
we can use one more of the second smallest money unit. E.g. after we
increased the number of 5 Pfennig coins to change a given amount, we
have to try to change the new remainder using 1 and 2 Pfennig coins.
  We restart the loop by resetting i to zero. This may not be a very
clean way to do this, since it leads to a rather strange behaviour of
the while loop. If you do not like this, you can replace the `i = 0'
by a `break' and surround the while loop with a do-while loop, whose
condition is '(i < UNITCNT)'. Then the outer while loop restarts the
inner while loop as long as the inner loop is aborted by the `break'.
In this manner the inner loop constructs a new way to change the
amount and the outer loops traverses these ways. To make this even
clearer the `n++' can be moved out of the inner while loop (provided
n is initialized to 0, since the last execution of the outer loop does
not construct a new way to change `amount').
  If in the while loop we found that no more money units i can be used,
we change the corresponding amount back to smallest money units. It is
obvious that we did not find a new way to change `amount' in this case.
Then the loop reexecutes and we try to increase the number of the next
larger money unit, since we obviously tried all combinations with the
current number of this larger money unit.
  We thus end up with an algorithm that has a structure very similar to
the nested loop solution. The only difference is that the loop variables
are kept in a vector and a loop through this vector is used to find the
next combination of values for the loop variables.
----------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  double amount;                /* amount to change in DM */

  if (argc != 2) {              /* if wrong number of arguments given */
    printf("usage: %s x\n", argv[0]);
    printf("compute number of ways to change amount x (in DM)\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */
  amount = atof(argv[1]);       /* convert argument to a number */
  if (amount <= 0.0) {          /* check range of amount */
    printf("%s: amount must be > 0\n", argv[0]); return 1; }
  printf("%.15g\n", count((int)(amount *100)));
  return 0;                     /* print number and return 'ok' */
}  /* main() */