AIOC Banner

A Dish Best Served Cold

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.

Reading the input

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.

Calculating the minimum

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.

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.

Calculating the maximum

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.

Calculating the mean

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.

Conclusion

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.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 17 August 2019,  9:12pm AEST