Perhaps the simplest program with a nested loop is one that prints out a square of *'s to the screen. You can see such a program off to the right.
Notice that each loop has a well-defined meaning.
One of the best ways to deal with the complexities of writing programs is to follow the design paradigm of stepwise refinement:
// Get n from user
// --- print squares ----
// For each of n rows do:
// print * n times
while
loops to solve a variety of problems. There will also be a few "detail" issues
that'll come up.
a
and b
is the largest integer that
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 out by the GCD of the numerator and the
denominator - 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 well-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
,
assuming a
is the larger of the two proceeds as
follows:
a
is divided by b
.
a
with b
and b
by r.
b
is the GCD.
a
is 42 and b
is 30, then
a b r ----------------- 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:
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;
r
, and we figures
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 10Now, 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.
Notice that, before we have loops, we can't do this calculation.
Without loops, we would need one line in our program for each year.
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.
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 totalWe 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:
op
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 is that there are three choices for where we can 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 }
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.
// 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 =
Suppose 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! In fact, it hasn't even been declared
anywhere. Thus, op
needs to be declared and
initialized appropriately.
Here is a complete solution.// Initialize total to 0 int total, k; char op; total = 0;
op = '+';// 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 cin >> op; } // Write result cout << total << endl;
~/$ ls -l
-rwxr-xr-- 1 wcbrown faculty 7084 Aug 9 17:00 a.out*
-rw-r--r-- 1 wcbrown faculty 14016 Aug 10 08:03 Class.html
-rw-r--r-- 1 wcbrown faculty 1269 Aug 9 09:41 Ex1.cpp
-rw-r--r-- 1 wcbrown faculty 3299 Aug 9 09:42 Ex1.html
-rw-r--r-- 1 wcbrown faculty 765 Aug 9 16:55 Ex3.cpp
-rw-r--r-- 1 wcbrown faculty 2445 Aug 9 16:56 Ex3.html
-rw-r--r-- 1 wcbrown faculty 620 Aug 9 17:00 Ex3hack.cpp
-rw-r--r-- 1 wcbrown faculty 1748 Aug 9 17:01 Ex3hack.html
-rw-r--r-- 1 wcbrown faculty 711 Aug 9 16:08 Ex4.cpp
-rw-r--r-- 1 wcbrown faculty 620 Aug 9 17:00 Exp3hack.cpp
-rw-r--r-- 1 wcbrown faculty 620 Aug 9 17:00 test.cpp
~/$
Write a program that reads this data, and prints out the largest file
size. File size (in bytes) appears in the column after
"faculty". The ~/$
at the end of the input
is actually the command prompt waiting for the next command.
If you include that in your copy-and-paste, 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!