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 i = 0; i < n; i++)
    {
      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 wel-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
123...n
234...n+1
...
nn+1n+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

  1. 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.
  2. 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.