Let's solve Encyclopædia.
In this problem, we are given a list of word counts on the pages of an encyclopædia. Our program must answer multiple questions of the form: "How many pages are there on page x?"
So far, whenever we've encountered problems involving large sets of data, I've tried to describe solutions that only 'remember' one or two variables at a time. With this problem such an approach is no longer possible.
You may be familiar with arrays - these are data structures that let you store large quantities of data. They behave differently in different languages, and you should check how they work in yours. In this walkthrough I'll be using C arrays as an example.
In C, an array is declared much like a normal variable. Say we needed room for 8 int-type variables. Then we would write:
int a[8];
The eight variables we now have access to are a[0], a[1], ..., a[6], a[7]. (Note that the numbering system is zero-based: counting begins at zero, not one. This may seem unintuitive, but turns out to be quite useful when we try manipulating arrays in advanced ways.)
The elements of an array can be manipulated like normal variables. For example, we could write:
<Read values into a[0] and a[1]> a[2] = a[0] + a[1]; <Print out the value of a[2]>
(As before, substitute the comments in angle brackets with code to correctly handle file input and/or output.)
The above would be a correct, albeit strange, solution to Addition (Starter Problems 1).
However, the real power of arrays lies in our ability to access their contents using mathematical expressions. If the variable foo is set to 5, then a[foo] refers to a[5] and we can manipulate a[foo] and store values inside it like any other variable. If the variable i counts from 0 to N-1 over the course of a loop, then in each iteration a[i] will refer to a different element of the array.
This is best seen with an example. The following code reads in a list of nPages integers into an array named wordcounts.
int nWords[10000];
for (int i = 0; i < nPages; i++) {
<Read an integer into wordcounts[i]>
}
At the first iteration of the loop, i is set to zero and so the first integer is stored in wordcounts[0]. The second integer is stored in wordcounts[1], and so on. So if we are after 'the xth integer', then it is stored in wordcounts[x-1].
Accessing arbitrary elements of wordcounts is also straightforward, so long as we remember the numbering system we are using. The following code reads in some number x and prints out the xth integer in the list:
int x; <Read an integer into x> <Write the value of wordcounts[x-1]>
This is quite close to what our current problem asks us to do. The above code would have to be placed inside a loop so that it dealt with the correct number of questions, but otherwise it is already very close to a full solution for Lookup.
Confidence with using arrays to store and manipulate large amounts of data is a very helpful skill, both in most real-world programming scenarios and in competitions like the Australian Informatics Olympiad. The rest of the problems in this set provide an opportunity to become comfortable with arrays and various common tricks that can be done with them.
__END__ $site->putPageFooter(); # Always return true. 1;