Imagine that you are a census taker charged with visiting all the homes in Spokesville and Squaresville (Figure 1.1). In each town, you must start and finish at home 1, after visiting each home once. All roads are the same length, and there are the same number of homes in each town. Nonetheless, in Spokesville you will travel a total distance exactly twice the distance required in Squaresville! The difference is due to structure.
It is easy to find the telephone number of a company whose name you know, even in the telephone directory of a large city. But finding the name of a company when you know only its telephone number is a tedious and time-consuming chore.The information in the telephone directory is structured in such a way that one task is easy while the other causes tension headache and eyestrain!
Two maps of the continental United States appear in Figure 1.2; part (a) gives a clear overview, while (b) gives a more detailed view. Structure clarifies, and detail obscures. Still, both are needed for a complete picture. Notice that drawing a border around and naming each state in the overview, in the absence of other distracting details, makes the composition of the country discernible. It is the plethora of detail and subordination of structure that is overwhelming in the other map. The less detailed map is analogous to a functionally modularized program, the other to an unmodularized program.
An algorithm for a given problem specifies a series of operations to be performed that eventually leads to a correct result. Algorithms express solutions step by step. In stating an algorithm, care must be taken to avoid ambiguity and to be sure that it is clear how each step is to be done. When the solution is translated into a programming language for execution by a computer, even more care and attention to detail are needed. But first, the solution is usually expressed in English or flowchart form, before the details required by the programming language are introduced. The next example illustrates the effect of structure in this context.
An integer larger than 1 is a prime number if it cannot be written as the product of two integers, each larger than 1. Suppose we must find a way to print all prime numbers between 2 and some integer n. Thus if n is 12, the primes are 2, 3, 5, 7, and 11. Compare the following two algorithms for accomplishing this task.
It is not difficult to see that if each step of the first algorithm can be carried out, the correct result will be printed. It is considerably more difficult to see that the same is also true of the second algorithm. The first is structured to provide clarity, while the second is poorly structured and provides too much detail. These examples indicate why structure is needed in each stage of program design. Structured solutions are easier to understand, expand, and alter, and structured data make the operations of the algorithm easier and faster to perform.
primes(n) anotherprimes(n)
1. Create a collection called candidates, 1. Set X1, X2, . . . , Xn to
consisting of all integers from 2 to n. zero.
2. Remove all nonprime integers from 2. Set k to 2.
candidates.
3. Print all integers that remain in 3. If Xk is 1, go to step 7.
candidates.
4. Print k.
5. Set m to the integer part of
n/k.
6. Set Xk, X2k, . . . , Xmk to 1.
7. Set k to k + 1.
8. If k ?/FONT> sqrt n, go to
step 3.
9. If Xk is zero, print k.
10. Set k to k - 1.
11. If k ?/FONT> n, go to step 9.
(a) Overview
Figure 1.2(a) Courtesy: Hammond Incorporated, Maplewood, NJ 07040.
(b) Detailed View
Figure 1.2(b) Courtesy: Hammond Incorporated, Maplewood, NJ 07040.