2010 Homework #02 - Coins

How many ways can one make a single US dollar from exactly 10 coins? Write a program that calculates the answer to this. For bonus points, write one that can calculate the answer for any amount of money and any amount of coins.

50 cent pieces, quarters, dimes, nickels, and pennies are allowed.

The answer to the problem is 6. ENTERPRISE C SOLUTION in the next post.

>>13
I did it in C# recursively. I can't see why memory should be a problem - unless I'm mistaken the stack depth shouldn't be more than the amount of coins?

I made it a bit more dynamic. You can change the values for amount of money, amount of coins and the amount and types of coins.


using System;

namespace ValueSplit
{
  class Program
  {
    //change these values to fit another problem
    static int amountOfMoney = 100, amountOfCoins = 10;
    static int[] coins = new int[] { 50, 25, 10, 5, 1};

    static void Main(string[] args)
    {
      Console.WriteLine("Number of combinations: {0}", Combinations());
      Console.ReadLine();
    }

    static int Combinations()
    {
      return Combinations(new int[coins.Length], 0);
    }
   
    static int Combinations(int[] splitCount, int index)
    {
      int currentValue = 0;

      for (int i = 0; i < index; i++)
        currentValue += splitCount[i];
      int mayUse = amountOfCoins - currentValue;
      if (splitCount.Length - 1 == index)
      {
        splitCount[index] = mayUse;
        currentValue = 0;
        for (int i = 0; i < splitCount.Length; i++)
          currentValue += splitCount[i] * coins[i];
        return amountOfMoney == currentValue ? 1 : 0;
      }

      int combinations = 0;
      for (splitCount[index] = 0; splitCount[index] <= mayUse; splitCount[index]++)
        combinations += Combinations(splitCount, index + 1);
      return combinations;
    }
  }
}

I know I'm a whore for using C# and I already regret posting.