OK, you just got your first hard program to build. Maybe it's part of your final project, maybe your teacher is just sadistic. It's hard to tell. Regardless, this thing is BIG. No, really big! No, a little bigger than that! Anyway, you're clueless as to what to do with this monster. Congratulations, I can get you to the solution!
Let's look at a "simple" example, the classic vending machine problem.
As you can see, you are now doomed to fail the class. But fear not! Without specifying the language in advance, I can step you through the solution! How, you might ask? Simple, through problem solving.Write a program that will simulate a vending machine. It must read an input file with a specific format and produce an output file based on the correct handling of the money in the vending machine.
The first line of the input file will be the number of quarters, dimes, and nickels in the machine at the beginning of the process.
The subsequent lines of the file will contain the purchase price of an object in the vending machine, and a sequence of dollar/coin values (100, 25, 10, or 5) representing the money that was entered to purchase the item.
Your output must, for each line, indicate the number of quarters, dimes, and nickels produced in change.
If correct change cannot be made, the line must indicate that it could not accept the purchase.
If insufficient money is provided, the line must indicate that the money was rejected.
The final line must be the number of dollars, quarters, dimes, and nickels in the machine at the end of the process.
Before you start typing away, grab a piece of paper and jot down a sample input file (or maybe you got one from your gracious and most merciful torturer... err teacher). Can you figure out, by hand, what the output file should look like?
Let's say the input looks like this:
The first line tells me I have 20 quarters, 10 dimes, and 20 nickels.Code:20 10 20 125 100 10 10 10 65 25 25 25 55 25 25 10
The second line tells me I have a purchase of $1.25 with a dollar bill and three dimes. So I now have 1 dollar, 20 quarters, 13 dimes, and 20 nickels and owe 5 cents in change. So I'll output 0 0 1, and now I have 1 dollar, 20 quarters, 13 dimes, and 19 nickels.
The third line tells me I have a purchase of 65 cents with three quarters. So I now have 1 dollar, 23 quarters, 13 dimes, and 19 nickels and owe 10 cents in change. So I'll output 0 1 0, and now I have 1 dollar, 23 quarters, 12 dimes, and 19 nickels.
The fourth line tells me I have a purchase of 55 cents with three quarters. So I now have 1 dollar, 26 quarters, 12 dimes, and 19 nickels and owe 20 cents in change. So I'll output 0 2 0, and now I have 1 dollar, 26 quarters, 10 dimes, and 19 nickels.
Finally, I have to output 1 26 12 19.
My final output is:
Great, now that we've wasted some pencil lead, can we start typing? NO! Welcome to the hard part of programming, where you actually think about what you just did.Code:0 0 1 0 1 0 0 2 0 1 26 12 19
1) You kept track of the number of dollars, quarters, dimes, and nickels in the machine at all times.
2) You kept track of the purchase price and change due for each line.
3) You figured out how many quarters, dimes, and nickels to produce the needed change for each line.
4) You read the first line to figure out the initial number of dollars, quarters, dimes and nickels
5) You read each successive line for purchase info
6) For each purchase info line, your wrote out the change info
7) After all purchase info lines were read, you wrote out the final money counts.
Summarizing: you kept track of nine pieces of information, had a file you were reading line by line, and another file you were writing line by line. What you just did by hand is what you have to tell the computer to do. If you don't know what you did, then you can't tell the computer to do it. The trick is to slow down and think about what YOU would do to get the right answer WITHOUT the computer!
Now, at last, we can write the pseudocode (that you would turn into code):
At this point, we are REALLY close to a solution. If we had four variables to keep track of the input coins, we would be done. If you wanted, you could also do sneaky things like trying alternate ways to make change (40 cents is a quarter, dime and nickel, or four dimes).Code://variables declared here int ourdollars int ourquarters int ourdimes int ournickels int changedollars //you'll see int changequarters int changedimes int changenickels int price int moneypaid //we forgot to mention this above!!! woops! int changedue int temp //good to have around, don't you think? //I'm being very generic about file access. //You can make sure the write file is blank as needed open(readfile) open(writefile) //get initial money ourdollars = 0 read(readfile, ourquarters) read(readfile, ourdimes) read(readfile, ournickels) readfile.nextline //something to make sure we advance, depends on language while not readfile.eof //we aren't assuming any transactions here! read(readfile, price) moneypaid = 0 while not readfile.eol //read all the coins read(readfile, temp) //told you a temp is handy! moneypaid = moneypaid + temp if temp = 100 then changedollars = changedollars + 1 end if if temp = 25 then changequarters = changequarters + 1 end if if temp = 10 then changedimes = changedimes + 1 end if if temp = 5 then changenickels = changenickels + 1 end if end while if moneypaid < price then //return money write(writefile,"Insufficient money, money returned") //we don't have to do anything fancy to reset our internal counts //because we haven't touched them yet else //keep our money ourdollars = ourdollars + changedollars changedollars = 0 ourquarters = ourquarters + changequarters changequarters = 0 ourdimes = ourdimes + changedimes changedimes = 0 ournickels = ournickels + changenickels changenickels = 0 changedue = moneypaid - price while changedue > 25 and changequarters < ourquarters //can't allocate quarters we don't have! changedue = changedue - 25 changequarters = changequarters + 1 end while while changedue > 10 and changedimes < ourdimes //can't allocate dimes we don't have! changedue = changedue - 10 changedimes = changedimes + 1 end while while changedue > 5 and changenickels < ournickels //can't allocate nickels we don't have! changedue = changedue - 5 changenickels = changenickels + 1 end while if changedue > 0 then //we couldn't make the change! writefile(outfile,"Could not make change!") //problem, we don't know how to pull out the money they gave us! else //we have change, hand it out and deduct from our money writefile(outfile,changequarters,changedimes,changenickels) ourquarters = ourquarters - changequarters ourdimes = ourdimes - changedimes ournickels = ournickels - changenickels end if writefile.nextline end if readfile.nextline end while
I'll leave it to finish this code and translate it into your favorite language. What I'm hoping you'll learn is this:
1) For every programming problem, make sure YOU can figure out the correct output yourself. If you don't know how to get there, you'll never code it.
2) Try to plan out what you need to keep track of. As you can see, it's inconvenient to have to add more variables when you realize you missed something. This is especially true with a BIG program (hundreds of variables to start with).
3) You don't have to figure out EVERYTHING in advance, but you should be able to get a quick outline, and know roughly what your variables need to be.
4) The above pseudo-code is glossing over a LOT of stuff! Reading/writing to files can be messy, especially if the formats are wonky. The result is that even if you have good logic, you will still have a lot of work to do, including debugging.
5) Be patient and don't panic. Was the above program REALLY that hard? I know it scares the snot out of most people the first time they see something like that, but you can figure it out if you work smarter, not harder.
Excellent read! I had a teacher in college who came from the military as a programmer. He was extremely strict about what you have wrote. We had to think every problem out, turn it into psuedocode and have him grade it before we started coding. He said every program he made in the military had to have psuedocode before starting. If you can think your way through a problem you can convert it into psuedocode and then code.
Thanks for the read! +rep
My frustration as a student was that most of the problems I got were too easy for me. I could see how to write the code almost instantly, and pseudo-code was just an irritation. However, when you get something challenging, you quickly see the advantage of planning out the program.
Not a big fan of pseudocode. My reasoning is prototyping gives you the benefits of being an exploratory form of code you can actually execute. All of the benefits, none of the draw backs. Pseudocode made more sense when code was hand converted to assembly, then you'd want to nail things down before starting. However there is no extra efficiency of expression of pseudocode over something like Python. While Python can show your application working before you start the actual implementation. I've never seen an up front design that looked anything like the final implementation so this exploration adds value.Originally Posted by Jordan
OTOH I like high level, module oriented views of a program. Just recently I finished off my preliminary design for my terrain rendering project mentioned in my blog post. It will have three threads and working out the modules and the type of information that flows between them makes it easier to work out where to apply locks to eliminate race conditions. Other than a few key algorithms I haven't bothered with fine details so far.
Of course the vending machine is a classic state machine problem and where they exist it is worth nailing down exactly what the states and the transitions between them are. Then plug in the resulting output. I think being able to look at a problem and saying 'Ah, state machine!' is a skill worth developing.
Personally, I despise pseudo-code as well. I can generally write code in a modular or incremental way that is pretty well guaranteed to work. Writing a framework of the logic IN CODE and then filling in the details consistently works well for me. It's getting a handle on the basic planning, like field mappings for a database migration, that I like to work out in advance.
I find that understanding the data is often harder than writing the code to work with the data. What I would consider a "realistic" pseudocode for the above would be:
Mind you, I vastly prefer flowcharts to pseudocode anyway, but I don't feel like trying to paste a bunch of diagrams here.Code:Read initial values For each line do read price and coins if enough money then determine change If change can be made then output change else output error end if else output error end if loop output final coins
Can't say I've ever felt the need for writing psuedo-code, and a professor forcing me to do so would probably drive me off the deep end.
I definitely think in code rather than flowcharts*. It's just that pseudocode is from a bygone era. I program prototypes in the 'wishful thinking' style proposed by MIT 6.001. I.E. I write algorithms top down and declare ridiculously high level functions that do not yet exist. Then recursively improve until it works. Once you have it working you can refactor it to get it set up nicely. You get instant feedback and the ability to judge the overall structure using both your mental and physical tools.
The point is 'do not implement' does not make sense when implementation does not cost you much but seeing it work is of massive benefit to your ability to reason. The problem is the lack of distinction between final product and prototype in some people's mind. There are some things that need reasoning but I don't think they are direct coding issues in the general case. It's more a matter of what you are trying to do and what the obvious metaphors are in breaking the problem down. It's rare you need magical algorithms but obviously where you do (which my current project does) you think about them first before even the modular break down**.
*just the ability to keep the entire algorithm in view at once is hard with flowcharts. I can see the flows fine in well structured code but also get a larger appreciation. Things like how many nested loops, where are my unconditional branches in relation to each other and so on are easier to see in code.
**it actually took me several weeks to work my way through 5/6 research papers on terrain/mesh rendering to reach a final conclusion about performance and the ability to work in gradual updates. Some very distinct stuff out there and the end solution focuses more on an interesting indexing scheme rather than a brilliant algorithm.
I think we're saying the same thing from more or less different directions. As an example, I'm working on a tutorial on designing classes for a program (since we've had a few questions on that lately). The key is to figure out the basic organization of the data, not to get all the details worked out in advance. When you have a basic plan of action, you can go with it, even if the details aren't hammered out yet.
Ironically enough, my assignment due Friday starts off "Design a vending machine controller." However, mine is hardware based.
To go along with the discussion, I do not use pseudo code either, and when writing an algorithm I rarely use a flow chart. However, when working with several objects, I find it useful to create a "flow" chart (aka a UML diagram).
There are currently 1 users browsing this thread. (0 members and 1 guests)
Posting Permissions
LinkBack URL
About LinkBacks
Reply With Quote
Bookmarks