CS 180: Data Structures
Spring 2011
MTuWF 10-10:50am in 121 RH

Erin Chambers
Contact Info: echambe5 - at - slu.edu
Office: 011 Ritter Hall


Lab Assignment 2

Topic: Speed Limit
Source Code: speed.cpp
Live Archive Ref#: 3059

In-Class Day:

Tuesday, Feb. 1, 2011
Submission Deadline: Friday, Feb. 4, 11:59pm

Techniques:

Loops, Arithmetic, tracking state information

Please review the general information about lab assignments.


Speed Limit

Bill and Ted are taking a road trip. But the odometer in their car is broken, so they don't know how many miles they have driven. Fortunately, Bill has a working stopwatch, so they can record their speed and the total time they have driven. Unfortunately, their record keeping strategy is a little odd, so they need help computing the total distance driven. You are to write a program to do this computation.

For example, if their log shows

Speed in miles per hour
Total elapsed time in hours
20
2
30
6
10
7

this means they drove 2 hours at 20 miles per hour, then 6-2=4 hours at 30 miles per hour, then 7-6=1 hour at 10 miles per hour. The distance driven is then (2)(20) + (4)(30) + (1)(10) = 40 + 120 + 10 = 170 miles. Note that the total elapsed time is always since the beginning of the trip, not since the previous entry in their log.

Input: The input consists of one or more data sets. Each set starts with a line containing an integer n, 1 ≤ n ≤ 10,  followed by n pairs of values, one pair per line. The first value in a pair, s, is the speed in miles per hour and the second value, t, is the total elapsed time. Both s and t are integers, 1 ≤ s ≤ 90 and 1 ≤ t ≤ 12.  The values for t are always in strictly increasing order. A value of -1 for n signals the end of the input.

Output: For each input set, print the distance driven, followed by a space, followed by the word "miles". 

Example input: Example output:
3
20 2
30 6
10 7
2
60 1
30 5
4
15 1
25 2
30 3
10 5
-1

170 miles
180 miles
90 miles


Prelab

Suppose that the input to the program is:
3
50 2
25 3
35 6
2
10 2
20 4
-1

What would the precise output be? Put your answer in a text file and turn it via email.

Hints

This is a rather straightforward problem, as described. But let me explain why I chose the problem for this lab. The key is to determine how much state information you need to be able to process the travelers' log, one line at a time. Although the syntax of object-oriented programming might be overkill in the race against time, the thought process is important. If I were to define a class for use in this problem, it would have a basic structure as follows:

class TravelLog {
  public:
    /** initialize a new (empty) log.  */
    TravelLog() { ... }

    /** Add a new entry to the log.
     *  @param   speed      current speed in miles per hour
     *  @param   clockTime  elapsed time since beginning of trip (in hours)
     */
    void addEntry(int speed, int clockTime) { ... }

    /** Returns the total number of miles traveled.
     *  @return number of miles
     */
    int getTotalMiles() const { ... }

  private:
    //  ??? state information ???

};
There are three basic operations. (1) initialize the internal state for a new trip, (2) process one additional log entry, and (3) report the total number of miles traveled on the current log. The challenge for you is to determine what internal variables are needed to support these operations. In particular, it is not necessary to store all of the raw log entries. You can consolidate the relevant information into a few well chosen variables. With a wise choice of variables, the rest of the problem is easy.

I will leave it up to you as to whether you actually want to use such a TravelLog class as part of your program, or to do similar calculations in a non-object-oriented way. In either case, you need to have a strategy for tracking the progress of a trip.

Warning: Keep in mind that your submitted program must be able to analyze multiple, independent trials. A common mistake on programming contests is to forget to reinitialize all relevant variables with each new trial (so that the computation on one trial does not adversely affect the computation for the next trial). So if using such a TravelLog class, make sure to start with a new instance for each trip (or if doing this problem implicitly with your own variables, make sure to reinitialize them for each new trip).