It's usually a good strategy to start answering questions at the places that have the most information, which, in this problem, means start with the prototypes because the problem describes them almost completely:
seasons accepts no arguments and returns the integer number of
breeding seasons - that translates directly into the prototype
int seasons(void)
population accepts as input an integer i representing the
number of breeding seasons since the start of the simulation and returns the
integer number of jackrabbits - another direct translation, this time into
int population(int season)
The problem also gives much information on how seasons() and
population() should behave when called, so dealing with how these two
procedures should be implemented seems like a good question to take up next.
seasons() returns the number of breeding seasons until the jackrabbit
population is not less than max. The important thing to note about
seasons() is that it can be implemented in terms of population():
seasons():
set s to zero
while population(s) is less than max
increase s by one
return s
population() returns the number of jackrabbits at the end of breeding
season i. population()'s implementation follows directly from
Professor Fibonacci's rules for population growth:
population(season):
// Sanity check - seasons shouldn't be negative.
if season less than 0
return 0
// Initially the rabbits haven't bread yet, so the population is equal to
// start.
if season equals 0
return start
// The population after the first season is determined by rule 1.
p1 = start
p2 = start + 1
// The population for seasons after the first requires that we remember the
// population of the previous two seasons and loop around through the seasons
// as described by rule 2.
i = 1
while i less than season and p2 less than max
j = p1
p1 = p2
p2 = j + p2
i = i + 1
// If there are too many rabbits, cut them back to the maximum.
if p2 greater than max
p2 = max
// Return the final population.
return p2
population() and
seasons(), it seems clear start and max are necessary:
int start, max
The solution, of course, is to wrap everything in a class:
class jackrabbit_ecosystem {
public:
jackrabbit_ecosystem(int s, int m)
int seasons(void)
int population(int season)
private:
int max, start
}
max and start should not be accessible outside
the class because changing them during a simulation messes up the results
returned by seasons() and population().
The ecosystem class also has to be initialized, and the easiest way to do that
is to create a constructor that accepts the initial values for max and
start. The prototype for the constructor is shown above, and its
implementation simply assigns s to start and m to max:
jackrabbit_ecosystem():
// Sanity check.
if s > m
abort()
max = m
start = s
One thing to note about the jackrabbit ecosystem given above is that it does a
lot of computation. For large values of season, population() can do
a lot of looping. In addition, seasons() is implemented by calling
population() repeatedly; this might make the jackrabbit ecosystem slow to
execute. Also, population() seems complicated, with all those tests and
computations going on at each call.
Can this design be improved by reducing computations and making
population() simpler? The key to answering this question is to note that,
once start and max are fixed, the values computed by
population() for a specific season don't change; that is, for a specific
ecosystem e and season s, the value of e.population(s) is
constant. This suggests that the population values be computed exactly once
and stored someplace so they can be used by population().
Where should the populations be stored? What we want is something that, when
given a season (an integer) returns the population for that season (another
integer). A little though concludes that an array of integers fills the bill
nicely. An array index i represents season i and the array element
pop[i] represents the population at season i.
How big should the population array be? Here the problem assumption that max - start <= 1000 helps us: given the definition of population growth, there can never be more than 1000 numbers to store, so a thousand-element integer array is big enough.
How should the population array be filled? We can pretty much steal the code
from population(), but there is a subtle point involving the maximum
population to be dealt with. In particular, how should computed populations
greater than the maximum be dealt with in the population array? One
possibility is to fill in the extra spaces in the array with the maximum
population rather than the computed population. This works but is somewhat
wasteful in computation and array space. An alternative is to stop computing
when the population reaches or exceeds max and remember the season in
which that occurred. This alternative allows us to stop computing once the
population grows too big, and also simplifies greatly the implementation of
seasons(), which now only needs to return the maximum season value.
Finally, where should the population computation be done? Because it only needs to be done once and needs to be done before the ecosystem can be used, putting it in the constructor seems like a good idea.
Based on these observations, the redesigned jackrabbit-ecosystem class is
class jackrabbit_ecosystem {
public:
jackrabbit_ecosystem(int s, int m)
pop[0] = s
pop[1] = s + 1
if pop[1] > m
pop[1] = m
max_season = 1
max_pop = m
while pop[max_season] < max_pop
max_season = max_season + 1
pop[max_season] = pop[max_season - 2] + pop[max_season - 1]
int seasons (void)
return max_season
int population (int season)
if 0 <= season and season < max_season
return pop[season]
else
return 0
private:
int max_pop
int max_season
int pop[1000]
}
This page last modified on 13 June 2001.