# Nested Loops

## 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 click the forward and backward arrows below, you'll see one way of following stepwise refinement for the Hankel matrix problem.

#include <iostream>

using namespace std;

int main() {
// Read in the parameter n

// Write Hankel matrix 1,...,2*n

return 0;
}

#include <iostream>

using namespace std;

int main() {
// Read in the parameter n

// Write Hankel matrix 1,...,2*n
for( int row = 1; row <= n; row++ ) {
// Write row entries row, ..., row + n
}

return 0;
}

#include <iostream>

using namespace std;

int main() {
// Read in the parameter n

// Write Hankel matrix 1,...,2*n
for( int row = 1; row <= n; row++ ) {
// Write row entries row, ..., row + n
for( int col = 1; col <= n; col++ ) {
// Write entry (row,col) in two spaces
}
}

return 0;
}

#include <iostream>

using namespace std;

int main() {
// Read in the parameter n

// Write Hankel matrix 1,...,2*n
for( int row = 1; row <= n; row++ ) {
// Write row entries row, ..., row + n
for( int col = 1; col <= n; col++ ) {
// Write entry (row,col) in two spaces
int val = row + (col - 1);
if( val < 10 )
cout << ' ';
cout << val << ' ';
}
cout << endl;
}

return 0;
}

#include <iostream>

using namespace std;

int main() {
// Read in the parameter n
int n;
cout << "Enter value n, where n < 50: ";
cin >> n;

// Write Hankel matrix 1,...,2*n
for( int row = 1; row <= n; row++ ) {
// Write row entries row, ..., row + n
for( int col = 1; col <= n; col++ ) {
// Write entry (row,col) in two spaces
int val = row + (col - 1);
if( val < 10 )
cout << ' ';
cout << val << ' ';
}
cout << endl;
}

return 0;
}


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. Clicking through the arrows below will show you one way of solving this one through stepwise refinement.

#include <iostream>

using namespace std;

int main() {

// Write result

return 0;
}

#include <iostream>

using namespace std;

int main()
{

/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
while()
{

// Evaluate next term c*x^n

// Update value of total
}

// Write result

return 0;
}

#include <iostream>

using namespace std;

int main()
{

/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
while()
{

/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
// - multiply by c

// Add value of term to total
}

// Write result

return 0;
}

#include <iostream>

using namespace std;

int main()
{
double x;
cout << "Enter value for x: ";
cin >> x;

/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
while()
{

/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
double xn = 1;
for(int i = 0; i < n; i++)
xn = xn*x;

// - multiply by c
double term = xn*c;

/******************************/
/** Add value of term to total*/
/******************************/
if (op == '+')
total = total + term;
else
total = total - term;
}

// Write result
cout << "Result is " << total << endl;

return 0;
}

#include <iostream>

using namespace std;

int main()
{
double x;
cout << "Enter value for x: ";
cin >> x;

/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
cout << "Enter polynomial to be evaluated "
<< "(e.g. 3.1*x^2 - 2.0*x^1 + 1.1*x^0 = )"
<< endl;

while(op != '=')
{
/******************************/
/** Read next term c*x^n  *****/
/******************************/
double c;
int n;
char t;
cin >> c >> t >> t >> t >> n;

/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
double xn = 1;
for(int i = 0; i < n; i++)
xn = xn*x;

// - multiply by c
double term = xn*c;

/******************************/
/** Add value of term to total*/
/******************************/
if (op == '+')
total = total + term;
else
total = total - term;
}

// Write result
cout << "Result is " << total << endl;

return 0;
}

#include <iostream>

using namespace std;

int main()
{
double x;
cout << "Enter value for x: ";
cin >> x;

/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
cout << "Enter polynomial to be evaluated "
<< "(e.g. 3.1*x^2 - 2.0*x^1 + 1.1*x^0 = )"
<< endl;

// Initialization for loop
char op;
double total;
op = '+';
total = 0;

while(op != '=')
{
/******************************/
/** Read next term c*x^n  *****/
/******************************/
double c;
int n;
char t;
cin >> c >> t >> t >> t >> n;

/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
double xn = 1;
for(int i = 0; i < n; i++)
xn = xn*x;

// - multiply by c
double term = xn*c;

/******************************/
/** Add value of term to total*/
/******************************/
if (op == '+')
total = total + term;
else
total = total - term;

cin >> op;
}

// Write result
cout << "Result is " << total << endl;

return 0;
}


## Problems

1. Read in a number n and print out the value of $$\sum_{k=0}^n {n \choose k},$$ that is, the sum as k goes from 0 to n of n choose k.

The formula for n choose k is $$\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{k\cdot(k-1)\cdot(k-2)\cdots 1}$$

So, for example 7 choose 3 is (7*6*5)/(3*2*1) = 35.

Notice that this number will always be an integer! So do all of your computations using type int, and don’t do anvy division unless you're sure you'll get exact results, i.e. no remainder. Take a look at this solution to the problem.

2. Write a program that will read in a value n from the user (you may assume that n is less than 30), and print out the nxn multiplication table. A typical run of the program might look like this:
Please enter the table size: 15
1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
2   4   6   8  10  12  14  16  18  20  22  24  26  28  30
3   6   9  12  15  18  21  24  27  30  33  36  39  42  45
4   8  12  16  20  24  28  32  36  40  44  48  52  56  60
5  10  15  20  25  30  35  40  45  50  55  60  65  70  75
6  12  18  24  30  36  42  48  54  60  66  72  78  84  90
7  14  21  28  35  42  49  56  63  70  77  84  91  98 105
8  16  24  32  40  48  56  64  72  80  88  96 104 112 120
9  18  27  36  45  54  63  72  81  90  99 108 117 126 135
10  20  30  40  50  60  70  80  90 100 110 120 130 140 150
11  22  33  44  55  66  77  88  99 110 121 132 143 154 165
12  24  36  48  60  72  84  96 108 120 132 144 156 168 180
13  26  39  52  65  78  91 104 117 130 143 156 169 182 195
14  28  42  56  70  84  98 112 126 140 154 168 182 196 210
15  30  45  60  75  90 105 120 135 150 165 180 195 210 225

Take a look at this solution to this problem.