project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_31.cpp (1035B)

      1 #include "Euler.h"
      2 
      3 int coins[8] = {200, 100, 50, 20, 10, 5, 2, 1};
      4 
      5 int coinSumRecurse(int money, int maxcoin)
      6 {
      7     int sum = 0;
      8 
      9     if(maxcoin == 7)
     10         return 1;
     11 
     12     for(int i = maxcoin; i < 8; i++)
     13     {
     14         if (money - coins[i] == 0)
     15             ++sum;
     16         if (money - coins[i] > 0)
     17             sum += coinSumRecurse(money - coins[i], i);
     18     }
     19 
     20     return sum;     
     21 }
     22 
     23 int Euler::CoinSums()
     24 {
     25     return coinSumRecurse(200, 0);   
     26 }
     27 
     28 //int Euler::CoinSums() //original solution
     29 //{
     30 //    int sum = 0;
     31 //
     32 //    for (int a = 0; a <= 200; ++a)
     33 //        for (int b = 0; b <= 100; ++b)
     34 //            for (int c = 0; c <= 40; ++c)
     35 //                for (int d = 0; d <= 20; ++d)
     36 //                    for (int e = 0; e <= 10; ++e)
     37 //                        for (int f = 0; f <= 5; ++f)
     38 //                            for (int g = 0; g <= 2; ++g)
     39 //                                if (a + b * 2 + c * 5 + d * 10 + e * 20 + f * 50 + g * 100 == 200)
     40 //                                    ++sum;
     41 //
     42 //    return sum + 1;
     43 //}