Hi i'm stuck on problem set 3 problem 2 calculating the highest number of mcnuggets that don't work. We can calculate what numbers work but we can't make it say what doesn't work. Any help???

Question

theeric · Answer

Can you provide a link to the problem?

unklerhaukus · Answer

the set of number that do work, will be equal to all the numbers, minus all the numbers that do work

anonymous · Answer

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset2.pdf

theeric · Answer

It looks like you're looking at problem set 2, problem 3.
And I'm glad you posted the whole thing, thanks!

I think what you want to does is use the theorem from problem 2.

This states that if you get to $x$ McNuggets, and then you find that all of
$\begin{matrix}x+1\x+2\x+3\x+4\x+5\end{matrix}$
McNuggets are acceptable, then you can be sure that $x$ McNuggets can be purchased from the groups of 6, 9, or 20.

Whichever last number of McNuggets that didn't work is the last number of... I repeat myself. But that's it!

Now you need to follow the algorithm listed in there.
But first, since we just found the last number of McNuggets that we can't put together with 6. 9. and 20... Do we have to keep track of it? Or is knowing $x$ good enough?

How do you plan to keep track of what $x$ is, or what you've tested already?
These are good concerns to have, around which you can tweak the given basic algorithm into a well-working one.

And part of the basic algorithm suggests you have to find $a$, $b$, and $c$ in
$6a+9b+20c=n$
where $n$ in the number of McNuggets in question.
Being exhaustive is easy - look for all the possibilities within reason! "For" loops, maybe. Or maybe "while" loops. I'd choose "while" loops, I think. But, either way, just make sure that you develop a good stopping condition. You don't want to have the computer go up to
$6\times 50,000,000,000+9\times 0+20\times0$
just because it hasn't worked out.

Side note: if this wasn't exhaustive, you'd look for some other pattern. And you'd look for all the shortcuts. One that I can think of is inspired by the case above. When you look at the case of $b=0,\ c=0$, then you're left with $6a$. You can use $6a$ to get to $n$ only if $n$ is a multiple of $6$. A language's modulo function might check that out quickly.
In fact, you can use a similar argument when
$a=0,\ c=0$
and
$a=0,\ b=0$
but this is all irrelevant to your problem.
And in the case of just $c=0$, you are left with $6a+9b=n$, in which case $n$ is a multiple of three.

But this is exhaustive. Sort of like using a steamroller in a bowling alley rather than using a bowling ball and mad skills.

I hope this helps! Feel free to ask questions! Take care!

lopus · Answer

you can watch this: http://openstudy.com/study#/updates/53504232e4b0b39169cd4cdd