Logical Problem Solving
by Robert Lamey, Prentice Hall 2002, 0-13-061882-9
(Paraphrased; examples added for clarification)
a. Be clear about what information you have to work with.
b. Be clear about what information you are trying to discover.
Example: determine pieces per dollar, given date and time, cost per weight, age of the vendor, and pieces per weight.
Pay attention to units. If the unit of measurement is kept with each number, the mathematical operation to be performed will be apparent without the knowledge of any formula. Correct operations will lead to units that cancel. Incorrect operations will lead to units that compound and confound.
Example: obtain distance from speed and time, where speed is in kilometres per hour and time is in hours. Speed multiplied by time yields distance (km/hr * hr č km)
Whenever possible draw a picture.
Example: pipe the output of the grep to more:
|
grep … |
č |
| |
č |
more |
display |
|
source |
stdout |
pipe |
stdin |
destination |
stdout |
Instead of working from the beginning of a problem asking what is the first step toward the end, start at the end and ask what is needed to perform the last step. From there examine what is necessary for the second to last step and work toward the beginning.
Example: write a command that has some "dash" options followed by the input filename followed by the output filename, as in:
command –1 –2 –3 infile outfile
The outfile is always at argv[argc – 1] and infile is always at argv[argc – 2]. Everything between argv[1] and argv[argc – 3] inclusive (if there is anything there at all) must all be dash options.
When approaching a problem look for repeated operations. The number of times the operation is repeated is usually irrelevant.
Example: convert a decimal integer to binary for display (and consider also Rule 4):
BEGIN
GET a positive integer to convert
WHILE the number is not zero
right-bit = remainder mod 2
IF right-bit is zero
SET next rightmost char = '0'
ELSE
SET next rightmost char = '1'
number = number / 2
END WHILE
DISPLAY result
END
When a problem involves repeated operations, be clear about which operations are repeated and belong inside the looping structure and which operations occur only once and should be outside of the loop.
Example: sum the integers from 1 to some ceiling:
BEGIN
FOR 1 to ceiling
GET ceiling Oops
SET total to zero Oops again
ADD 1 to total
PRINT total
END FOR
END
When a problem is too difficult to solve consider limiting the problem to find a special case solution.
Example: calculate the height of a building by dropping an object from the roof and timing its fall until you hear it hit the ground. Ignore variations in local gravity, air resistance while falling, wind forces, and the speed of sound of the impact.
When examining a general problem it is often more illuminating to work with a specific instance. An example with numeric values is always easier to understand than the general case.
Example: calculate the factorial of a number (1 x 2 x … n). Test your solution (the PDL at first) with several numbers, like 3, 5, 10, and 20. Test the boundary cases – how small and how large can n be?
When an exact solution is too difficult to calculate, an approximate answer of arbitrary accuracy can often be found by adding terms that make a partial solution come ever closer to the true solution.
Example: calculate p (pi) to as many digits of precision as possible. A solution is to find that the formula below (among others) gets closer and closer to the value of p as more terms are added to the sum:
p = 4 * ( 1 – 1/3 + 1/5 – 1/7 + … )
See also Rule 5, since a loop will work quite nicely here (and check Rule 15, too).
a. Make a reasonable initial guess.
b. Check the accuracy of the guess.
c. Repeatedly refine the guess until the desired accuracy is achieved.
Example: compute the square root of a number by making a guess, squaring the guess and measuring its error, then adjusting the guess and repeating until the result is "close enough" to the correct value.
This technique was first described to me in 1961 as "the way computers calculate square roots" by a programmer on an ancient (now) IBM 650 computer at the University of Ottawa.
As problems become more complex it becomes increasingly important to divide the logic into smaller units that solve individual parts of the problem. These units correspond to programming functions.
Example: no segment of code should be much larger than one or perhaps 2 screens. Select self-contained pieces that return one or a few results from a small number of arguments such that each piece (function) can be tested on its own and understood entirely with relative ease.
When all else fails try examining all possible solutions in a systematic manner.
Example: many sort algorithms rely on comparing each and every pair of elements in order to re-arrange them in the desired order.
If a statement is assumed to be true and then leads to a conclusion contrary to some known fact, the original assumption must be false. If a statement is assumed to be false and leads to a conclusion contrary to some known fact, the original assumption must be true. All real-world scenarios must be self-consistent.
Example: an application that calculates the floor area of a residential home to be thousands of square metres is probably over-calculating, but if it's a commercial office tower and only hundreds of square metres then it's quite likely to be under-calculating.
When probabilities or odds need to be calculated, brute force can usually be applied by simulation the scenario and counting how many times the event of interest occurs.
Example: if you flip a coin a billion times (1,000,000,000) how many times does it come up heads? A for loop and a random number generator do well for this.
Look for approximations that simplify a problem but do not appreciably affect the accuracy of the solution.
Example: The value of p is something near but greater than 3.141592653589793239462643… but 3.14159265 is probably close enough for most purposes much of the time.
When generalizing a solution to encompass a greater range, greater complexity, broader conditions, or greater utility, focus on the differences between the conditions when the solution works and the new conditions.
Example: a working solution does not have to be rewritten to add another feature. In fact, it's very practical to write a solution in a series of steps, starting with a very limited implementation and adding more features (and complexity) in well-planned stages, testing (and making backups!) at every stage.
A problem can be solved recursively if :
a. The final step or the base condition is known.
b. The first step of the problem leads to exactly the same problem but one step closer to the solution.
Example: recursion (having a function call itself over and over again) is a well-known method for calculating factorials or other mathematical values, for walking binary trees, and for many other programming problems.
This rule has been left to the last because without the other rules there is no starting point, nothing to write down, nothing to try.
What should be tried when facing a new problem?
· Rewrite the problem.
· List the information available.
· Draw a picture.
· Think of a concrete example.
· Limit the problem.
· Look for repeated operations.
· Examine the units.
· Try working the problem backward.
· Try to guess at the answer.
· Try to brute force your way to an answer.
· Try a simulation.
· Create an object [or a structure].
· Try recursion.
But do something!