Question

I'm working on Problem Set 2, problem 2/3. I was able to work out problem 1 and understand the theorem. I get why McNuggets>=x if x..x+5 is true, I can't quite put it in words which is why I'm having trouble coding the next iterative program for problem 3. Mainly how to look for all combinations of a, b, and c in 6a +9b+20c = n. the amount of variables is making it hard to grasp. if anyone can at least guide me toward the right step I'd appreciate it!

Answer 1

I think your main problem is to try to write a program that finds solutions to 6a+9b+20c=n for n from 0-50. In this case u should try exhaustive enumeration i.e for each value of n u should check all possible values of a,b and c and see if any of them works. If they work, u could use the break function to get out of the loop and test for the next value of n. Use google to consult how to get out of multiple loops in python. If they don't work then print that there is no solution. You would definitely need to nest loops within loops. Using for loops would help. Once u find solutions I think it would be an easy job to use the knowledge in prob 2 to find the maximum value for which there is no solution. You may start your code with, for n in range(50):

And also if u still don't get it, u may find it useful to watch the next lecture as the barnyard might be particularly helpful for this problem.

Answer 2

I don't think it's necessary to break out of the loop, just populate a 2-dimensional array with values which work. Cycling through all possible values even in a relatively small range like [-20,20] sounds quite tedious. Hopefully someone can come up with something simpler.

One working example:
solved = [1,1,1,35]

Answer 3

Here is a working C++ example for n = 35. You might have to include some error testing.
int solved[20][4];
int i = 0;
int n = 35;
for (int a=-5; a < 5; a++)
for (int b=-5; b<5; b++)
for (int c=-5; c<5; c++)
{
if (6*a + 9*b + 20*c == n)
{
solved[i][0] = a;
solved[i][1] = b;
solved[i][2] = c;
solved[i][3] = n;
i++;
}
}
for (int x=0; x < i; x++)
{
cout << solved[x][0] << ", " << solved[x][1] << ", " << solved[x][2] << ", " << solved[x][3] << endl;
}

Output:
-3, -3, 4, 35
-2, 3, 1, 35
0, -5, 4, 35
1, 1, 1, 35
4, -1, 1, 35

Answer 4

Thanks those both have helped a lot. WAZTAZ, I think I have it, I may be wrong, but should the code be able to work for any three numbers(say i change out 6,9,20)? or just these three specifically since I've tested 50-55 and technically already have a cap on it.

Answer 5

MANDRE< thank you the theory helps I'm just familiarizing with Python so I don't know fully whats going on in C++.

Answer 6

No problem. I'm still learning Python myself but we use C++ for most of our programming modules.

Bear in mind that when writing the code you have to impose limitations on all variables as you could end up with a huge load of combinations. If you use [-20, 20] as your range for a, b and c and n = 35 you end up with 80 combinations, i.e. you can only list "all" combinations in a pre-specified range.

Answer 7

i guess a possible python implementation would be the one below although im having quite some trouble in problem 2 . id be very glad if could post the explanation of the theorem and why it is true. ☺

for a in range((x/6)+1):
for b in range((x/9)+1):
for c in range((x/20)+1):
if 6*a + 9*b + 20*c == x:
print "("+str(a)+","+str(b)+","+str(c)+")"