IC210

Class 10: Loops II

Reading

None

Lecture

This lecture is going to be mostly about using while loops to solve a variety of problems. There will also be a few "detail" issues that'll come up.

Every Mathematician’s Favorite Algorithm: The Euclidean GCD Algorithm

The greatest common divisor (GCD) of two positive integers a and b is the largest integer than evenly divides both a and b. You may remember that some math teacher along the way told you that an answer like 3/6 is wrong, because it can be reduced to 1/2. How? By dividing both the numerator and the denominator by the GCD of the numerator and the denominator which is 3 in this case. So an algorithm that computes the GCD of two numbers is useful ... at least for placating math teachers. It's actually useful in an unimaginable number of other contexts, in things as diverse as encryption for online-banking to controlling the motions of robots.

Strangely, however, today's best known algorithm for solving this problem was invented thousands of years ago. It is called the "Euclidean Algorithm" because it appears in Euclid's book "The Elements", which contained most of the mathematics known in the ancient Greek world. The basic process (algorithm) for computing the GCD of a and b is this: Assuming a is the larger of the two, compute the remainder when a is divided by b, and replace a with b and b by the remainder. Keep doing this until you get a remainder of zero, at which point b is the GCD.
For example, if:    a = 42;
          b = 30;
Then

a b remainder
-----------------
42 30 12
30 12 6
12 6 0

... and therefore 6 is the GCD. We can do this with a loop, and hopefully it's clear that the loop will look something like this:

while(no idea what goes here!)
{
 r = a % b; // remember "%" is remainder
 a = b;
 b = r;
}

We have two questions now: When do we stop? Where is the answer when we stop? We could try to be clever, but that's difficult. Let's just see what happens with the code we do have in the example from above:

Before iteration 1: r = ?, a = 42, b = 30
Before iteration 2: r = 12, a = 30, b = 12
Before iteration 3: r = 6, a = 12, b = 6
Before iteration 4: r = 0, a = 6, b = 0 Stop! No 4th iteration!

As you can see, our clue to stop is that r is zero (or, you could say that b being zero is our clue), and you can see that the answer resides in the variable a. So, we could complete our loop like this:

while (b != 0)
{
 r = a % b; // remember "%" is remainder
 a = b;
 b = r;
}
cout << a << " is the GCD!" << endl;

Interest Done Right: Counting our iterations

In the Problems from Class 3, we considered the problem of computing compound interest. The user entered an annual interest rate r, and we figured out how much you'd have after 10 years at that rate with an investment of $100.00 in the account at the beginning of each year. The bulk of the program might look like the following.

 double T;
 T = 0.0; // Before year 1
 T = (T + 100.0)*(1.0 + r/100.0); // After year 1
 T = (T + 100.0)*(1.0 + r/100.0); // After year 2
 T = (T + 100.0)*(1.0 + r/100.0); // After year 3
 T = (T + 100.0)*(1.0 + r/100.0); // After year 4
 T = (T + 100.0)*(1.0 + r/100.0); // After year 5
 T = (T + 100.0)*(1.0 + r/100.0); // After year 6
 T = (T + 100.0)*(1.0 + r/100.0); // After year 7
 T = (T + 100.0)*(1.0 + r/100.0); // After year 8
 T = (T + 100.0)*(1.0 + r/100.0); // After year 9
 T = (T + 100.0)*(1.0 + r/100.0); // After year 10

Now, to do this right, we'd like the user to enter the annual interest rate r and the number of years you'll keep money in the account y, and we'd like our program to figure out how much you'd have after y years at that rate with an investment of $100.00 in the account at the beginning of each year.

Why couldn't we do that in Class 4? Because you didn't know about loops! In the Class 4 solution, we needed one line in our program for each year. If the user entered 100 years, we'd need to type in a 100+ line line program. To make the program work for any value of y, you need a loop.

First, let's try to rewrite the above block of code, in which the number of years is fixed at 10, using a loop. Fortunately, the above code breaks into a loop pretty easily:

 double T;
 T = 0.0; // Initialization for the loop
 
 while (I need to loop 10 times!)
 {
 T = (T + 100.0)*(1.0 + r/100.0); // After year ?
 }

We need to keep track of how many times we've gone through the loop body, and once we've gone through the loop body 10 times, we stop. Let's introduce an int variable i to keep track of the number of times we've gone through the loop body, i.e. to keep track of the number of iterations of the loop.

 double T;
 T = 0.0; // We don't have any money yet
 int i;
 i = 0; // We haven't completed any iterations yet
 
 while (I need to loop 10 times!)
 {
 T = (T + 100.0)*(1.0 + r/100.0); // After year ?
 i = i + 1; // record that we've completed an iteration
 }

Now, what about the test condition for this loop? Well, we want to keep looping as long as the number of loop iterations completed is less than 10. Once we've completed 10 loop iterations we can move on an print our answer.

 double T;
 T = 0.0; // We don't have any money yet
 int i;
 i = 0; // We haven't completed any iterations yet
 
 while (i < 10)
 {
 T = (T + 100.0)*(1.0 + r/100.0); // After year i + 1
 i = i + 1; // record that we've completed an iteration
 }

Now, what about making this work for any number of years? Here's a complete solution.

The second simplest calculator

Let's consider writing a program that reads from the user a simple arithmetic expression using + and -, like 3 + 4 - 7 + 2 - 4 = , and prints out the result of the expression. Essentially your program will be a big while loop, and initially you might decide to write something like this

// Initialize total to 0
 
// Loop
 
 // read next value
 
 // add or subtract value from total

We can start filling in code here too, since we know how to do some of it at least:

// Initialize total to 0
total = 0;
 
// Loop
while(I don't know what goes here)
{
 // read next value
 cin >> k;
 
 // add or subtract value from total
 if (I don't know what goes here either)
 total = total + k;
 else
 total = total - k;
}

Now, this far things are easy ... they'll start to get tricky. What we haven't dealt with is reading in the +/-'s, and using them to make up test conditions for our loop or our if statement. Let's suppose we read the +/- operation into a variable of type char which we'll call op. Now, which of our three problems will we face next:

when to read in op
how to do the loop test condition
how to do the if test condition

The easiest is probably "how to do the if test condition", if op is a plus sign we add, if it's a minus we subtract. That gives us:

// Initialize total to 0
total = 0;
 
// Loop
while(I don't know what goes here)
{
 // read next value
 cin >> k;
 
 // add or subtract value from total
 if (op == '+')
 total = total + k;
 else
 total = total - k;
}

So, let's next address the question of when to read op. We know that op will have to be read somewhere in the loop, and the question is just where? The way I see it there are three choices for where we'll put cin >> op:

// Initialize total to 0
total = 0;
 
// Loop
while(I don't know what goes here)
{
 <------------------------------- Choice #1
 // read next value
 cin >> k;
 <------------------------------- Choice #2
 // add or subtract value from total
 if (op == '+')
 total = total + k;
 else
 total = total - k;
 <------------------------------- Choice #3
}

Choice #2 can be ruled out immediately, since the op value we want when we do our if-test is the one that came before the k-value, not the one that comes after. Choice #1 can be provisionally thrown out, because the first time through the loop there is no operation to read. (I say "provisionally", because we might be able to get around this by handling our initialization differently. So, we're left with Choice #3, which gives us:

// Initialize total to 0
total = 0;
 
// Loop
while(I don't know what goes here)
{
 // read next value
 cin >> k;
 
 // add or subtract value from total
 if (op == '+')
 total = total + k;
 else
 total = total - k;
 
 // read next op value
 cin >> op;
}

Now, the only thing left is to find a test condition for our while loop. Let's run through our code on the example input "3 + 5 - 2 =" supposing that the while loop test condition simply does what we want. Keep an eye out for what signals us that we're done with the loop:

Hopefully you see that the signal that we shouldn't loop anymore is when op is =.

// Initialize total to 0
total = 0;
 
// Loop
while(op != '=')
{
 // read next value
 cin >> k;
 
 // add or subtract value from total
 if (op == '+')
 total = total + k;
 else
 total = total - k;
 
 // read next op value
 cin >> op;
}

We're still not home yet though, because the first time through the while loop, we test the variable op, but it doesn't have any value! Thus, op needs to be initialized appropriately. Here is a complete solution.

Problems

1. Write a program that allows the user to enter a sequence of "moves" and prints out their position after the moves. Solution 1 is straightforward ... but long and tedious. Solution 2 is clever, shorter, but a bit trickier to understand.

2. Find the largest file is a directory listing. I asked the computer to list the files in one of my directories, and this is what it printed out:

3. -rwxr-xr-- 1 wcbrown faculty 7084 Aug 9 17:00 a.out*
4. -rw-r--r-- 1 wcbrown faculty 14016 Aug 10 08:03 Class.html
5. -rw-r--r-- 1 wcbrown faculty 1269 Aug 9 09:41 Ex1.cpp
6. -rw-r--r-- 1 wcbrown faculty 3299 Aug 9 09:42 Ex1.html
7. -rw-r--r-- 1 wcbrown faculty 765 Aug 9 16:55 Ex3.cpp
8. -rw-r--r-- 1 wcbrown faculty 2445 Aug 9 16:56 Ex3.html
9. -rw-r--r-- 1 wcbrown faculty 620 Aug 9 17:00 Ex3hack.cpp
10.-rw-r--r-- 1 wcbrown faculty 1748 Aug 9 17:01 Ex3hack.html
11.-rw-r--r-- 1 wcbrown faculty 711 Aug 9 16:08 Ex4.cpp
12.-rw-r--r-- 1 wcbrown faculty 620 Aug 9 17:00 Exp3hack.cpp
13.-rw-r--r-- 1 wcbrown faculty 620 Aug 9 17:00 test.cpp
14.valiant>

Write a program that reads this (You can copy it, then paste it into your program window. This must be done by going to your DOS-prompt window, clicking in the upper left corner, and selecting "edit".) data, and prints out the largest file size. File size (in bytes) appears in the column after "faculty". The valiant> at the end of the input is actually the command prompt waiting for the next command. It'll tell you that there are no more file entries to read.

If you're really ambitious, try to also print out the name of the largest file!

---

Assoc Prof Christopher Brown

Last modified by LT M. Johnson 08/15/2007 11:11 AM