I understand your argument. You're saying M(50),M(51)and M(52) is basically a set of 6 9 and 20 packs and we should approach it by using lower values starting from 0 for one or two variables to simply the solution on paper. I think I have some idea now as to how to approach this problem.
Sent from my iPhone > On 29-Aug-2016, at 5:18 AM, Danny Yoo <d...@hashcollision.org> wrote: > >> On Sun, Aug 28, 2016 at 7:46 AM, shahan khan <shahankh...@gmail.com> wrote: >> Hello >> I'm teching myself Python using MIT opencourse ware. I'm a beginner and >> have some what knowledge of c and c++. I'm using Python version > > > >> Here is my code: > [code cut] > > Before showing code, try to express what you're trying to do in > English first. That is, your explanation near the bottom: > >> I'm using for loops to give possible valutes to a,b and c and then using the >> equation (6*a)+(9*b)+(20*c) to determine possible values for a,b and c for > satisfying the equation. > > ... this should actually be presented because it's the most important > part! The problem with code is that code just executes. Any > expectations we have about what that code does is a matter of human > interpretation. > > > > Anyway, from looking at your original code (modulo indentation), I > *think* the treatment as a search problem, looking for the values of > the parameters a, b, c is reasonable, with the way you're doing nested > for loops, > >> for a in range(1,10): >> for b in range(1,5): >> for c in range(1,5): > > However, I am not entirely convinced that the search bounds are > actually sound. Here's why: I don't know why the numbers 1, 10, 5, > and 5 were chosen in the loop: they seem arbitrary, and you need to > say where those numbers came from. I suspect there's a problem with > them anyway. > > > One concrete reason why I don't think it works: change the problem > slightly. Say that we're trying to find a solution for the parameters > where the Diophantine equation evaluates to 6. Basically, the really > simple edge case. > > What change would you make to your code for this simpler case? I'd > assume that the simplest thing to do would be to change the target > value in the test expression, from: > > if mc==50: ... > > to > > if mc == 6: ... > > > Now, before we even try your program, we *know* there's a trivial > solution for a, b, and c such that the equation sums to six! > > a = 1 > b = 0 > c = 0 > > However, looking back at program structure, we can see, even without > looking at the rest of the code, that it can't possibly consider such > parameters, because it's assuming that all three variables have to be > positive. > > So that's something that we know needs to be fixed in some way. > > > > My take on the problem: this sounds very much like a question begging > for a dynamic programming approach, rather than a nested loop > approach. The reason I say this is because of the part of the problem > statement: > > ############################################################### > Theorem: If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some > x, then it is possible to buy any number of McNuggets >= x, given that > McNuggets come in 6, 9 and 20 packs. > ############################################################### > > would be the beginning of a mathematical induction proof, which is the > scent of a dynamic programming problem. > > > I'd sketch this as follows: let's call M(n) a boolean function on the > natural numbers that's true if we can buy n McNuggets by *any* > combination of 6, 9, and 20 packs. > > We know that: > > * M(6) is true > * M(9) is true > * M(20) is true > > Why? Because we can take a single 6-pack, or a single 9-pack, or a > single 20-pack, and each of these is a way to buy 6, 9, or 20 > McNuggets. > > From that core collection of knowledge, that inductive base, we can > start investigating what else we can discover by building upon that > knowledge inductively. > > > Example: we know that since M(6) is true, that M(12) is true, because > we can include another 6-pack to the one that built up M(6). > Furthermore, we know that M(15) is true, because M(6) is true, and we > can include another 9-pack to the one that built up M(6). > > > What about M(50)? Well, not quite sure. However, I do know this: if > M(50) is true, then *at least one* of the following has to be true: > > a. M(44) is true > b. M(41) is true > c. M(30) is true > > How in the world would we know this? > > Because if we were able to make 50 McNuggets out of a collection of 6, > 9, or 20 packs, then we have to have picked one of those packs. And > the remainder, outside of that pack, is where we get 44, 41, or 30. > > We don't have absolute knowledge here: it's *conditional* because we > don't yet know if M(44), M(41), or M(30) is true. But it's a start. > > I don't want to say too much more about this. The reason is because > if I state the idea just a little bit more formally, it suddenly looks > a heck of a lot like a direct problem solution. But I hope that gives > you some ideas. > > See: https://mail.python.org/pipermail/tutor/2016-July/109391.html for > some links to dynamic programming material. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
