Reading
None.
Nested Loops
#include <iostream>
using namespace std;
int main()
{
// Get n from user
int n;
cout << "Please enter n: ";
cin >> n;
// print square
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout << "* ";
}
cout << endl;
}
return 0;
}
The body of a loop is a block of code like any other - like the
body of "main", or like a then-block or like an else-block. So,
that means that it can contain any of the C++ constructs we've
talked about so far ... including more loops. Loops inside loops
are referred to as "nested", and you'll see a lot of them.
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. See how it involves a loop nested
within a loop? Notice too, though, that each loop has a
well-defined meaning. The outer loop body prints a single row,
the inner loop body prints a single * within that row.
One of
the best ways to deal with the complexities of writing programs
using nested loops is to follow the design paradigm of
stepwise refinement, which basically has you writing
programs in rough steps which are then continually refined until
they end up as actual C++ code. Let's consider an example to see
this in action.
Printing out a Hankel matrix
The Hankel matrix defined by the numbers 1, 2, ..., 2n-1 is
| 1 | 2 | 3 | ... | n |
| 2 | 3 | 4 | ... | n+1 |
| | ... | | |
| n | n+1 | n+2 | ... | 2n-1 |
I want you to write a program that will read in a value n from
the user, you may assume that n is less than 50, and print out
the Hankel matrix defined by 1, 2, ..., 2n-1 on the screen. When
your program runs, it should look something like this:
Enter value n, where n < 50: 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Think about what you're going to have to do in order to ensure
that the columns line up correctly, given that you have single
and double digit numbers!
The key to solving this problem effortlessly is to gradually
develop a solution. If you look at this
page, you'll see how I did that for this problem. This is
what step-wise refinement is about. We've been doing it all
along, in a sense, but it's much more interesting when you have
nested structures like loops and if statements, as opposed to a
simple sequence of flat steps.
Polynomial Evaluation
Let's consider another problem: I want to write a program that
will do polynomial evaluation. That is, it will read in a value
for x and a polynomial in x and print out the
result of evaluating the polynomial at the given value. To make
it a bit easier on ourselves, let's assume that each term is given
as a coefficient times x raised to some power. Thus, we would
write 1.1*x^2 - 3.0*x^1 + 2.1*x^0 instead of
1.1*x^2 - 3.0*x + 2.1. The user will show that he's done
entering the polynomial by typing an equals sign. A typical
run of the program might look like this:
Enter value for x: 3.1
Enter polynomial to be evaluated (e.g. 3.1*x^2 - 2.0*x^1 + 1.1*x^0 = )
0.75*x^5 - 1.8*x^3 + 0.3*x^2 + 1.1*x^1 =
Result is 167.388
In essence this problem is not much different from the "simple
calculator" problem we looked at in
Class 10. The main difference is
that instead of sums and differences of simple numbers, we have
sums and differences of terms in a polynomial.
Once again, a nice way to attack this problem is by stepwise
refinement, where we gradually develop a solution by specifying
in deeper and deeper detail how we'll solve the problem, until
our detail is so great we actually have a complete C++ program.
If you look at this
page, you'll see how I did that for this problem.
Problems
-
You have a bank account whose annual interest rate depends on
the amount of money you have in your account at the beginning
of each year. Your annual rate starts at 3%, and grows by an
additional half a percent for each thousand dollars in your
account up to, but not exceeding 8%. So, for example, if you
have $3,358.02 in your account at the beginning of the year, your
rate is 4.5%. Interest in this account is compounded monthly
at the annual rate (i.e. the monthly compounding rate is the
annual rate divided by 12).
Each year you also make a deposit (before the bank figures
out what your rate is, fortunately).
Write a program that simulates these financial
interactions. It should first ask the user how many years
he wants to simulate, and at the beginning of each year it
should ask the user how much he wants to deposit. A typical
run of the program might look like this:
How many years would you like to simulate: 5
Payment for year 1 : 2000
Payment for year 2 : 1500
Payment for year 3 : 1000
Payment for year 4 : 400
Payment for year 5 : 100
Final balance is 6119.56 dollars.
Take a look at this solution to this problem.
- Read in a number n and print out the value of
n
----- / \
\ | n |
) | |
/ | k |
----- \ /
k = 0
i.e. the sum as k goes from 0 to n of n choose k.
The number n choose k is
n*(n-1)*...*(n - k + 1)
-----------------------
k!
So, for example 7 choose 3 is
7*6*5
----- = 35
3*2*1
Notice that this number will always be an integer! So don't
do your computations using type int, and don't
do any division unless you're sure you'll get exact results,
i.e. no remainder.
Take a look at this solution to the problem.