Let's solve A Dish Best Served Cold.
In this problem, we are asked to write a program that takes a list of numbers and calculates the minimum, maximum and mean of the list. This walkthrough will deal briefly with the input handling, before moving on to strategies for calculating the statistical values.
You'll notice that a lot of problems on this site ask your program to read in large amounts of data. So however we end up dealing with the input here, we'll probably be doing something very similar in the future.
As you may have guessed, reading the input is a repetitive task that is best done using loops. We have a simple action (reading in a single integer) that needs to be repeated once for each value in the list.
Say we decide to read the size of the list into the variable N. Then we need to write a loop that executes its code exactly N times. Working in C/C++, I suggest a for loop:
<read in the value of N>
for (int i = 1; i <= N; i++) {
<read in a single integer>
...
}
The inner code is executed as i takes on the values 1, 2, 3, ..., N. After the last iteration, i is incremented and becomes larger than N, so that the computer moves on to the code after the loop. So we can see that the inner code is executed exactly N times.
Actually reading in the integers is something you should already have plenty of practice with. The only difference is that the scanf lines (or your language's equivalent) are now inside a loop.
With the input dealt with, let's move on to the first value we must calculate: the minimum. Now, this is a fairly intuitive task for us. We could probably find the smallest value in a list of several dozen numbers just by looking at it. Unfortunately, when it comes to a programming approach, it's not enough to say "just look at it". We need to come up with a clearly defined, mechanical approach that the computer can use.
Our program receives the input one number at a time. As it is, it cannot look ahead or run its 'eyes' up and down the list. Imagine that a friend read the list out to you in order, like: "Seventy. Seventy-two. Seventy-four. Fifty..." Could you work out the smallest value just by listening?
Here's one way. As your friend reads the list to you, all you need to keep track of is the smallest value you've heard so far.
For example, say the list of numbers went like {7, 6, 7, 10, 4, 8, 3, 7, 6, 5}. Then as you listen to it being read, your thoughts might go "7... 6, that's smaller... too big... too big... 4, that's smaller... too big... 3, that's smaller..." You know that by the time you reach the end of the list, you'll have settled on the smallest number available.
This lends itself to a programming approach. Let's use the variable min to keep track of the smallest number. Now, recall our inner loop:
for (int i = 1; i <= N; i++) {
<read in a single integer>
...
}
While it's possible to store the entire list of numbers in memory (we'll deal with this in later problems), here it's enough just to read the latest integer into a single variable. Let's call it current_value.
Now, if min (the smallest value we've seen) is going to change at all after reading in current_value, then our program must have found a record low number.
How do we know if current_value is smaller than anything else so far? Well, it turns out that all we need to check it against is the old minimum:
To rephrase: "if current_value is smaller than min is, set min to that value".
for (int i = 1; i <= N; i++) {
<read an integer into current_value>
if (current_value < min) {
min = current_value;
}
}
This is looking good: as we read in each integer, we check if it is smaller than our working minimum, and update the variable accordingly. There's only one small problem - what the inner code does with the very first number in the list. Currently, we haven't initialised min (that is, given it a value at the start of the code). But what can we set it to? Before we first enter the loop, we haven't seen any numbers at all, so what does "the smallest number so far" mean for an empty list?
Notice that when we pass the first number we definitely want min to take its value: if we've only seen one number, it has to be the smallest one we've seen (not to mention the largest, the longest, the cutest, etc.). Also, once we've gotten past that first number, our code works exactly as planned, since min means exactly what we want it to. We just need to make a small modification to make sure the program does the right thing with the first number.
There are two common ways around this problem.
Just tell the computer to always take the first value. The first time the loop is run, it shouldn't even worry about comparing current_value to min - just update min straight away.
We have a really convenient way of asking 'are we up to the first number?' - the variable i. The first time the loop is run, i is equal to 1 (or whatever you set it to count from). So then we tell the computer to update min if i is 1 or if there's a smaller value at our disposal.
for (int i = 1; i <= N; i++) {
<read an integer into current_value>
if (i == 1 || current_value < min) {
min = current_value;
}
}
Initialise min to something ridiculously big. Instead of explicitly checking what number we're up to, we can just force (current_value < min) to be true the first time round.
How do we force it to be true? Well, have a look at the problem statement. It tells us that all values will be "between 0 and 1,000,000 inclusive". So if we set min to something greater than 1 million, the if statement will have to trigger the first time around.
min = 2000000;
for (int i = 1; i <= N; i++) {
<read an integer into current_value>
if (current_value < min) {
min = current_value;
}
}
(I just plucked that number out of the air. Plenty of numbers will work, like 1000001 or 999999999. Just make sure it's (a) more than 1 million, and (b) small enough to fit into its data type. In C/C++, an int cannot hold values much larger than 2 billion.)
The first method doesn't require you to know how big the numbers in the list are. The second method has a more streamlined inner loop. Experiment with both of these on pen and paper, and convince yourself that they work.
I'm not going to discuss this part closely. If you're stuck, carefully consider your code for finding the minimum, and try to apply those ideas here.
As the problem statement (and any good maths teacher) will tell you, the mean (or average) of a list of numbers is the sum of those numbers divided by the length of the list. The problem asks us to round it down - conveniently, most programming languages round down their (integer) division by default. What's more, we already know the length of the list - that's N. So we just have to calculate the sum and we're set.
If anything, finding the sum is even easier than finding the minimum or maximum. Whenever our program reads in a number, it just adds it to a running total. It looks something like this:
for (int i = 1; i <= N; i++) {
<read an integer into current_value>
total += current_value;
}
What value should total be initialised to? That's easy - zero. Anything else and that number would mess with the calculated total. Just remember to print total/N at the end.
Our finished loop might look something like this:
<read in the value of N>
<initialise variables, e.g. total = 0;>
for (int i = 1; i <= N; i++) {
<read an integer into current_value>
<update min accordingly>
<update max accordingly>
<update total accordingly>
}
At this stage, you have all the tools you need to write a 100% solution to A Dish Best Served Cold.
Note: Calculating the minimum, maximum, or total of a list is a very common task in informatics problems. Make sure that you understand how your solution works, so that you can reuse and/or adapt it to other situations. Even if your programming language provides a built-in way of doing all these things, you shouldn't rely on it. For example, you might need to perform an action several times and take the smallest result - there may not be an explicit list for you to plug into a generic function.
__END__ $site->putPageFooter(); # Always return true. 1;