IC210

Class 13: Nested Loops & Stepwise Refinement I

Reading

Review Section 2.3 of Absolte C++

 

Lecture

Aside: Comparing Floating-Point Numbers for Equality

As stated earlier in the course, directly comparing two floating-point numbers for equality is a bad idea due to how floating-point numbers are stored in memory.  Consider 2 1/3 subtracted from 2 2/3.  This should leave a result of 1/3 ... right?  Not necessarily true when it comes to a digital computer's approximation of floating-point numbers. Since floating point calculations involve a bit of uncertainty we can try to allow for this by seeing if two numbers are ‘close’ to each other. If you decide – based on error analysis, testing, or a wild guess – that the result should always be within 0.00001 of the expected result then you can change your comparison to something like this:

    if (fabs(result - expectedResult) < 0.00001)

Take a look at this example of how to properly compare floating-point numbers for equality.

Now, On to Nested Loops

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

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.


Assoc Prof Christopher Brown

Last modified by M. Johnson 08/15/2007 05:08 PM