P1: FCH/SPH P2: FCH/SPH QC: FCH/TKJ T1: FCH
CB496-01 CB496-Akin September 13, 2002 15:51
1.2 Problem Definition 5
format must be defined so that the user can quickly see or hear the programs results.
Archival results need to be stored on long-term media, such as disk, so that later inter-
pretation of the file’s contents is easy (recall the notion of being able to read tomorrow
what is written today) and the reading process is easy.
The answers to these questions help programmers organize their thoughts and can lead to
decisions about programming language and operating environment. At this point in the pro-
gramming process, the programmer should know what the program is to do and for whom
the program is written. We do not yet have a clear notion of how the program will accomplish
these tasks; that comes down the road. This approach to program organization and design
is known as top–down design. Here, broad program goals and context are defined first with
additional detail filled in as needed. This approach contrasts with bottom–up design, where
the detail is decided first and then merged into a functioning whole. For programming,
top–design makes more sense, but you as well as professional programmers are frequently
lured into writing code immediately, which is usually motivated by the desire to get some-
thing running and figure out later how to organize it all. That approach is prompted by
expediency but usually winds up being more inefficient than a more considered, top–down
approach that takes longer to get off the ground but has increased likelihood of working
more quickly. The result of defining the programming problem is a specification: how the
program is structured, what computations it performs, and how it should interact with the
user.
An Extended Example: The Game of Life
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
To illustrate how to organize and write a simple program, let us structure a program that
plays TheGameofLife. Conway's “Game of Life" was popularized in Martin Gardner's Math-
ematical Games column in the October 1970 and February 1971 issues of Scientific Amer-
ican. This game is an example of what is known in computer science as cellular automata.
An extensive description of the game can be found in The Recursive Universe by William
Poundstone (Oxford University Press, 1987).
The rules of the game are quite simple. Imagine a rectangular array of square cells that are
either empty (no living being present) or filled (a being lives there). As shown in Figure 1.1,
each cell has eight neighboring cells. At each tick of the clock, a new generation of beings
is produced according to how many neighbors surround a given cell.
r
If a cell is empty, fill it if three of its neighboring cells are filled; otherwise, leave it empty.
r
If a cell is filled, it
dies of loneliness if it has zero or one neighbors,
continues to live if it has two or three neighbors, or
dies of overcrowding if it has more than three neighbors.
The programming task is to allow the user to “play the game" by letting him or her define
initial configurations, start the program, which applies the rules and displays each genera-
tion, and stop the game at any time the user wants, returning to the initialization stage so
that a new configuration can be tried. To understand the program task, we as programmers
need to pose several questions, some of which might be
r
What computer(s) are preferred, and what kind of display facilities do they have?
r
Is the size of the array arbitrary or fixed?
r
Am I the only programmer?