c 8 coins combination code

Question

My code is supposed to calculate the total combinations. For paying cash between 1-500 dollars using these coins: 1, 2, 5, 10, 20, 50, 100, 200. But it doesn't calculate it right. what have I done wrong? You can assume that the input is correct and you can only use loops and if statements. You may not use recursion.

int pr, a, b, c, d, e, f, g,h, poss = 0;
printf_s("What is the amount that you like to check? (or press '0' to exit)\n");
scanf_s("%d", &pr);

for (a = 0; a <= pr; a++)
{
    for (b = 0; b <= (pr/2); b++)
    {
        for (c = 0; c <= (pr /5); c++)
        {
            for (d = 0; d <= (pr /10); d++)
            {
                for (e = 0; e <= (pr /20); e++)
                {
                    for (f = 0; f <= (pr / 50); f++)
                    {
                        for (g = 0; g <= (pr / 100); g++)
                        {

                            for (h = 0; h <= (pr/200); h++)
                            {
                                if (1 * a + 2 * b + 4 * c + 10 * d + 20 * e + 40 * f + 100 * g + h * 200 == pr)

                                    poss += 1;

                            }
                        }
                    }
                }
            }
        }
   }printf_s("The number of possibilities is: %d.\n", poss);
}

Answer 1

When 5 is entered the correct number of perms is reported but expanding the code prints the wrong values. Because this line

if (1 * a + 2 * b + 4 * c + 10 * d + 20 * e + 40 * f + 100 * g + h * 200 == pr)

has the wrong denominations. It should be

if (1 * a + 2 * b + 5 * c + 10 * d + 20 * e + 50 * f + 100 * g + h * 200 == pr)

You should also move the line

printf_s("The number of possibilities is: %d.\n", poss);

outside of the loops.

Answer 2

Your final printf needs to be out of the loops

    for (a = 0; a <= pr; a++)
    {
        for (b = 0; b <= (pr/2); b++)
        {
            for (c = 0; c <= (pr /5); c++)
            {
                for (d = 0; d <= (pr /10); d++)
                {
                    for (e = 0; e <= (pr /20); e++)
                    {
                        for (f = 0; f <= (pr / 50); f++)
                        {
                            for (g = 0; g <= (pr / 100); g++)
                            {

                                for (h = 0; h <= (pr/200); h++)
                                {
                                    if (1 * a + 2 * b + 4 * c + 10 * d + 20 * e + 50 * f + 100 * g + h * 200 == pr)

                                        poss += 1;

                                }
                            }
                        }
                    }
                }
            }
       }
    }
    printf("The number of possibilities is: %d.\n", poss);

Answer 3

As mentioned in Weather Vane answer, OP is using some wrong multipliers in the inner condition (4 and 40 instead of 5 and 50).

It's worth noting that, even with this brute force approach, we can save some CPU time by avoiding unnecessary calculations inside the (way too nested) loops and limiting the ranges of those loops to a smaller extent. Consider the following refactorization:

#include <stdio.h>

int number_of_possibilities(int price)
{
    int poss = 0;
// It takes less time to consume the bigger pieces earlier    
    for ( 
// 'a' represent the sum of the values of 200$ pieces, not the number of 200$
// pieces, which is 'a / 200'           
          int a = 0; a <= price;
// add the value of a single 200$ piece to move forward
          a += 200 )
    {
      for ( int b = 0,
// 'dif_b' is what is left from the price, once the 200$ pieces are counted
                dif_b = price - a;
// we don't need to iterate from 0 to 'price', but only to what is left
            b <= dif_b; b += 100 )                
      {
// 'dif_c' is what is left once the 100$ and 200$ pieces counted so far are
// subctracted from the original price. The same holds for the inner loops     
        for ( int c = 0, dif_c = dif_b - b; c <= dif_c; c += 50 )
        {
          for ( int d = 0, dif_d = dif_c - c; d <= dif_d; d += 20 )
          {
            for ( int e = 0, dif_e = dif_d - d; e <= dif_e; e += 10 )
            {
              for ( int f = 0, dif_f = dif_e - e; f <= dif_f; f += 5 )
              {
                for ( int g = 0, dif_g = dif_f - f; g <= dif_g; g += 2 )
                {
// now that only the 1$ coins are left to consider, we can avoid another inner
// loop and just realize that we need exactly 'dif_g - g' 1$ coins to pay the 
// full price, so there is one and only one possible combination.
                  ++poss;
                }
              }
            }
          }
        }      
      }
    }
    return poss;
}


int main(void)
{
    printf("  i   number of possibilities\n\n");
    for ( int i = 0; i < 501; ++i )
    {
        printf("%4d %16d\n", i, number_of_possibilities(i));
    }
    return 0;
}

Which gives the following:

  i   number of possibilities

   0                1
   1                1
   2                2
   3                2
   4                3
   5                4
   6                5
   7                6
   8                7
   9                8
  10               11

 ...

  99             4366
 100             4563
 101             4710    

 ...

 498          6159618
 499          6224452
 500          6295434

Executed in less then 2 seconds on an old Atom N270 at 1.6 GHz...