Transcript Chapter 3

Chapter 6
Iteration
Chapter 6  Iteration
1
Chapter Goals

To be able to program loops with while and
for (sometimes do) statements

To avoid infinite loops and off-by-one errors

To understand nested loops

To learn how to process input

To implement simulations
Chapter 6  Iteration
2
while Loops


Executes a block of code repeatedly
A condition controls how often the loop is
executed
while (condition)
statement;

Usually, the statement is a block statement
(set of statements enclosed in { })
Chapter 6  Iteration
3
Calculating the Growth of an
Investment

Invest $10,000, 5% interest, compounded annually
Year
0
1
Balance
$10,000
$10,500
2
3
4
$11,025
$11,576.25
$12,155.06
5
$12,762.82
Chapter 6  Iteration
4
Calculating the Growth of an
Investment

When has the bank account reached a
particular balance?
int year = 0;
while (balance < targetBalance)
{
year++;
double interest = balance * rate / 100;
balance = balance + interest;
}
Chapter 6  Iteration
5
File Investment.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
/**
A class to monitor the growth of an investment that
accumulates interest at a fixed annual rate.
*/
public class Investment
{
/**
Constructs an Investment object from a starting balance
and interest rate.
@param aBalance the starting balance
@param aRate the interest rate in percent
*/
public Investment(double aBalance, double aRate)
{
balance = aBalance;
rate = aRate;
years = 0;
}
19:
Chapter 6  Iteration
Continued…
6
File Investment.java
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
/**
Keeps accumulating interest until a target balance has
been reached.
@param targetBalance the desired balance
*/
public void waitForBalance(double targetBalance)
{
while (balance < targetBalance)
{
years++;
double interest = balance * rate / 100;
balance = balance + interest;
}
}
/**
Gets the current investment balance.
@return the current balance
*/
Chapter 6  Iteration
Continued…
7
File Investment.java
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57: }
public double getBalance()
{
return balance;
}
/**
Gets the number of years this investment has
accumulated interest.
@return the number of years since the start of the
investment
*/
public int getYears()
{
return years;
}
private double balance;
private double rate;
private int years;
Chapter 6  Iteration
8
File InvestmentTester.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
/**
This program computes how long it takes for an investment
to double.
*/
public class InvestmentTester
{
public static void main(String[] args)
{
final double INITIAL_BALANCE = 10000;
final double RATE = 5;
Investment invest
= new Investment(INITIAL_BALANCE, RATE);
invest.waitForBalance(2 * INITIAL_BALANCE);
int years = invest.getYears();
System.out.println("The investment doubled after "
+ years + " years");
}
}
Continued…
Chapter 6  Iteration
9
File InvestmentTester.java
Output
The investment doubled after 15 years
Chapter 6  Iteration
10
while Loop Flowchart
Figure 1:
Flowchart of a while Loop
Chapter 6  Iteration
11
Syntax 7.1: The while Statement
while (condition)
statement
Example:
while (balance < targetBalance)
{
year++;
double interest = balance * rate / 100;
balance = balance + interest;
}
Purpose:
To repeatedly execute a statement as long as a condition is true
Chapter 6  Iteration
12
Self Check
1.
How often is the statement in the loop
while (false) statement;
executed?
2.
What would happen if RATE was set to 0 in
the main method of the
InvestmentTester program?
Chapter 6  Iteration
13
Answers
1.
Never
2.
The waitForBalance method would never
return due to an infinite loop
Chapter 6  Iteration
14
Common Error: Infinite Loop

.int
years = 0;
while (years < 20)
{
double interest = balance * rate / 100;
balance = balance + interest;
}

int years = 20;
while (years > 0)
{
years++; // Oops, should have been years-double interest = balance * rate / 100;
balance = balance + interest;
}
 Loops
run forever (must kill the program)
Chapter 6  Iteration
15
Common Error: Off-By-One Errors
int years = 0;
while (balance < 2 * initialBalance)
{
years++;
double interest = balance * rate / 100;
balance = balance + interest;
}
System.out.println("The investment reached the target after "
+ years + " years.");

Should years start at 0 or 1?

Should the test be < or <=?
Chapter 6  Iteration
16
Avoiding Off-by-One Error


Look at a scenario with simple values:
initial balance: $100
interest RATE: 50%
after year 1, the balance is $150
after year 2 it is $225, or over $200
so the investment doubled after 2 years
the loop executed two times, incrementing years
each time
Therefore, years must start at 0, not at 1
Chapter 6  Iteration
17
Avoiding Off-by-One Error

Suppose interest rate is 100%

Then after one year
 balance is 2 * initialBalance
so loop should stop

Therefore: must use < not <=

Think!
 Don't just guess and compile
Chapter 6  Iteration
18
do Loops

Executes loop body at least once:
do
statement while (condition);

Example: Validate input
double value;
do
{
System.out.print("Please enter a positive number: ");
value = in.nextDouble();
}
while (value <= 0);
Chapter 6  Iteration
19
do Loops

Can get same effect with a while loop
boolean done = false;
while (!done)
{
System.out.print("Please enter a positive number: ");
value = in.nextDouble();
if (value > 0) done = true;
}
Chapter 6  Iteration
20
do Loop Flowchart
Figure 2:
Flowchart of a do Loop
Chapter 6  Iteration
21
Spaghetti Code

Code with confusing
jumps is called
spaghetti code

Hard to read

Hard to maintain

Avoid spaghetti code!
Chapter 6  Iteration
Figure 3:
Spaghetti Code
22
for Loops

for (initialization; condition; update)
statement
Example:
for (int i = 1; i <= n; i++)
{
double interest = balance * rate / 100;
balance = balance + interest;
}
Chapter 6  Iteration
23
for Loops

Equivalent to
initialization;
while (condition)
{ statement; update; }

Other examples
for (years = n; years > 0; years--) . . .
for (x = -10; x <= 10; x = x + 0.5) . . .
Chapter 6  Iteration
24
Flowchart for for Loop
Figure 4:
Flowchart of a for Loop
Chapter 6  Iteration
25
Syntax 7.2: The for Statement
for (initialization; condition; update)
statement
Example:
for (int i = 1; i <= n; i++)
{
double interest = balance * rate / 100;
balance = balance + interest;
}
Purpose:
To execute an initialization, then keep executing a statement and updating an
expression while a condition is true
Chapter 6  Iteration
26
File Investment.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
/**
A class to monitor the growth of an investment that
accumulates interest at a fixed annual rate
*/
public class Investment
{
/**
Constructs an Investment object from a starting
balance and interest rate.
@param aBalance the starting balance
@param aRate the interest rate in percent
*/
public Investment(double aBalance, double aRate)
{
balance = aBalance;
rate = aRate;
years = 0;
}
Continued…
Chapter 6  Iteration
27
File Investment.java
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
/**
Keeps accumulating interest until a target balance
has been reached.
@param targetBalance the desired balance
*/
public void waitForBalance(double targetBalance)
{
while (balance < targetBalance)
{
years++;
double interest = balance * rate / 100;
balance = balance + interest;
}
}
Continued…
Chapter 6  Iteration
28
File Investment.java
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
/**
Keeps accumulating interest for a number of years.
@param n the number of years
*/
public void waitYears(int n)
{
for (int i = 1; i <= n; i++)
{
double interest = balance * rate / 100;
balance = balance + interest;
}
years = years + n;
}
/**
Gets the current investment balance.
@return the current balance
*/
Chapter 6  Iteration
Continued…
29
File Investment.java
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
public double getBalance()
{
return balance;
}
/**
Gets the number of years this investment has
accumulated interest.
@return the number of years since the start of the
investment
*/
public int getYears()
{
return years;
}
Chapter 6  Iteration
Continued…
30
File Investment.java
68:
69:
70:
71: }
private double balance;
private double rate;
private int years;
Chapter 6  Iteration
31
File InvestmentTester.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
/**
This program computes how much an investment grows in
a given number of years.
*/
public class InvestmentTester
{
public static void main(String[] args)
{
final double INITIAL_BALANCE = 10000;
final double RATE = 5;
final int YEARS = 20;
Investment invest = new Investment(INITIAL_BALANCE, RATE);
invest.waitYears(YEARS);
double balance = invest.getBalance();
System.out.printf("The balance after %d years is %.2f\n",
YEARS, balance);
}
}
Continued…
Chapter 6  Iteration
32
File Investment.java
Output
The balance after 20 years is 26532.98
Chapter 6  Iteration
33
Self Check
3.
Rewrite the for loop in the waitYears
method as a while loop
4.
How many times does the following for loop
execute?
for (i = 0; i <= 10; i++)
System.out.println(i * i);
Chapter 6  Iteration
34
Answers
3.
4.
int i = 1;
while (i <= n)
{
double interest = balance * rate / 100;
balance = balance + interest;
i++;
}
11 times
Chapter 6  Iteration
35
Common for Errors: Semicolons

A semicolon that should not be there
sum = 0;
for (i = 1; i <= 10; i++);
sum = sum + i;
System.out.println(sum);

A missing semicolon
for (years = 1; (balance = balance + balance *
rate / 100) < targetBalance; years++)
System.out.println(years);
Chapter 6  Iteration
36
Nested Loops

Create triangle pattern
[]
[][]
[][][]
[][][][]

Loop through rows: for each row
for (int i = 1; i <= n; i++)
{
// make triangle row
}
Chapter 6  Iteration
37
Nested Loops

Another loop to make triangle row
for (int j = 1; j <= i; j++)
r = r + "[]";
r = r + "\n";

A loop within a loop: nested loops
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
r = r + "[]";
r = r + "\n";
}
Chapter 6  Iteration
38
File Triangle.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
/**
This class describes triangle objects that can be
displayed as shapes like this:
[]
[][]
[][][]
*/
public class Triangle
{
/**
Constructs a triangle.
@param aWidth the number of [] in the last row of
the triangle.
*/
public Triangle(int aWidth)
{
width = aWidth;
}
Continued…
Chapter 6  Iteration
39
File Triangle.java
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37: }
/**
Computes a string representing the triangle.
@return a string consisting of [] and newline
characters
*/
public String toString()
{
String r = "";
for (int i = 1; i <= width; i++)
{
// Make triangle row
for (int j = 1; j <= i; j++)
r = r + "[]";
r = r + "\n";
}
return r;
}
private int width;
Chapter 6  Iteration
40
File TriangleTester.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
/**
This program tests the Triangle class.
*/
public class TriangleTester
{
public static void main(String[] args)
{
Triangle small = new Triangle(3);
System.out.println(small.toString());
Triangle large = new Triangle(15);
System.out.println(large.toString());
}
}
Chapter 6  Iteration
41
Output
[]
[][]
[][][]
[]
[][]
[][][]
[][][][]
[][][][][]
[][][][][][]
[][][][][][][]
[][][][][][][][]
[][][][][][][][][]
[][][][][][][][][][]
[][][][][][][][][][][]
[][][][][][][][][][][][]
[][][][][][][][][][][][][]
[][][][][][][][][][][][][][]
[][][][][][][][][][][][][][][]
Chapter 6  Iteration
42
Self Check
5.
How would you modify the nested loops so
that you print a square instead of a triangle?
6.
What is the value of n after the following
nested loops?
int n = 0;
for (int i = 1; i <= 5; i++)
for (int j = 0; j < i; j++)
n = n + j;
Chapter 6  Iteration
43
Answers
5.
Change the inner loop to
for (int j = 1; j <= width; j++)
6.
20
Chapter 6  Iteration
44
Avoid != in for Loops

Bad idea to use != to test for end of range
for (i = 1; i != n; ++i)
. . .
 What happens if n is negative?

Safer to use
for (i = 1; i <= n; ++i)
. . .
Chapter 6  Iteration
45
Scope of Variable in for Loop

Consider this…
for (int i = 1; i <= n; ++i)
{
. . .
}
// i is no longer defined

Compared to this…
int i;
for (i = 1; i <= n; ++i)
{
. . .
}
// i is still defined here
Chapter 6  Iteration
46
Use Loops as Intended

Java syntax lets you do weird things

Here’s one bad idea…

for (System.out.print(”Inputs: ");
(x = inNextDouble()) > 0;
sum += x)
++count;
And here’s another…
for (int i = 1; i <= years; i++)
{
if (balance >= 5.0)
i = years - 3;
. . .
}
Chapter 6  Iteration
47
Processing Sentinel Values


Sentinel value: Can be used for indicating the
end of a data set
0 or -1 make poor sentinels; better to use Q
System.out.print("Enter value, Q to quit: ");
String input = in.next();
if (input.equalsIgnoreCase("Q"))
We are done
else
{
double x = Double.parseDouble(input);
. . .
}
Chapter 6  Iteration
48
Loop and a half


Sometimes termination condition of a loop can
only be evaluated in the middle of the loop
Can use a boolean variable to control the loop:
boolean done = false;
while (!done)
{
Print prompt String input = read input;
if (end of input indicated)
done = true;
else
{
// Process input
}
}
Chapter 6  Iteration
49
File InputTester.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
import java.util.Scanner;
/**
This program computes the average and maximum of a set
of input values.
*/
public class InputTester
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
DataSet data = new DataSet();
boolean done = false;
while (!done)
{
Chapter 6  Iteration
Continued…
50
File InputTester.java
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31: }
System.out.print("Enter value, Q to quit: ");
String input = in.next();
if (input.equalsIgnoreCase("Q"))
done = true;
else
{
double x = Double.parseDouble(input);
data.add(x);
}
}
System.out.println("Average = " + data.getAverage());
System.out.println("Maximum = " + data.getMaximum());
}
Chapter 6  Iteration
51
File DataSet.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
/**
Computes the average of a set of data values.
*/
public class DataSet
{
/**
Constructs an empty data set.
*/
public DataSet()
{
sum = 0;
count = 0;
maximum = 0;
}
/**
Adds a data value to the data set
@param x a data value
*/
Chapter 6  Iteration
Continued…
52
File DataSet.java
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
public void add(double x)
{
sum = sum + x;
if (count == 0 || maximum < x) maximum = x;
count++;
}
/**
Gets the average of the added data.
@return the average or 0 if no data has been added
*/
public double getAverage()
{
if (count == 0) return 0;
else return sum / count;
}
Chapter 6  Iteration
Continued…
53
File DataSet.java
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49: }
/**
Gets the largest of the added data.
@return the maximum or 0 if no data has been added
*/
public double getMaximum()
{
return maximum;
}
private double sum;
private double maximum;
private int count;
Chapter 6  Iteration
54
Output
Enter value, Q
Enter value, Q
Enter value, Q
Enter value, Q
Average = 7.0
Maximum = 22.0
Chapter 6  Iteration
to
to
to
to
quit:
quit:
quit:
quit:
22
0
-1
Q
55
Self Check
7.
Why does the InputTester class call
in.next and not in.nextDouble?
8.
Would the DataSet class still compute the
correct maximum if you simplified the
update of the maximum field in the add
method to the following statement?
if (maximum < x) maximum = x;
Chapter 6  Iteration
56
Answers
7.
Because we don't know whether the next
input is a number or the letter Q
8.
No. If all input values are negative, the
maximum is also negative. However, the
maximum field is initialized with 0. With this
“simplification”, the maximum would be
incorrectly computed as 0.
Chapter 6  Iteration
57
break and continue Statements

Can use break to immediately exit the loop
while (true)
{
String input = in.next();
if (input.equalsIgnoreCase(“Q”))
break;
double x = Double.parseDouble(input);
data.add(x);
 }Also is a continue statement
 Go immediately to next iteration of loop
 Not as useful as break
 Often use if/else instead of continue
Chapter 6  Iteration
58
Random Numbers and Simulations


In a simulation, you repeatedly generate random
numbers and use them to simulate an activity
Java random number generator:
Random generator = new Random();
int n = generator.nextInt(a); // 0 <= n < a
double x = generator.nextDouble(); // 0 <= x < 1

For example, to “throw” a die…
int d = 1 + generator.nextInt(6);
Chapter 6  Iteration
59
File Die.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
import java.util.Random;
/**
This class models a die that, when cast, lands on a
random face.
*/
public class Die
{
/**
Constructs a die with a given number of sides.
@param s the number of sides, e.g. 6 for a normal die
*/
public Die(int s)
{
sides = s;
generator = new Random();
}
Continued…
Chapter 6  Iteration
60
File Die.java
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30: }
/**
Simulates a throw of the die
@return the face of the die
*/
public int cast()
{
return 1 + generator.nextInt(sides);
}
private Random generator;
private int sides;
Chapter 6  Iteration
61
File DieTester.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
/**
This program simulates casting a die ten times.
*/
public class DieTester
{
public static void main(String[] args)
{
Die d = new Die(6);
final int TRIES = 10;
for (int i = 1; i <= TRIES; i++)
{
int n = d.cast();
System.out.print(n + " ");
}
System.out.println();
}
}
Chapter 6  Iteration
62
Output
First Run
6 5 6 3 2 6 3 4 4 1
Second Run
3 2 2 1 6 5 3 4 1 2
Chapter 6  Iteration
63
Buffon Needle Experiment
Figure 5:
The Buffon Needle Experiment
Chapter 6  Iteration
64
Needle Position
Figure 6:
When Does a Needle Fall on a Line?
Chapter 6  Iteration
65
Needle Position

Needle length = 1, distance between lines = 2

Generate random ylow between 0 and 2

Generate random angle  between 0 and 180
degrees

yhigh = ylow + sin()

Hit if yhigh ≥ 2
Chapter 6  Iteration
66
File Needle.java
01: import java.util.Random;
02:
03: /**
04:
This class simulates a needle in the Buffon needle
experiment.
05: */
06: public class Needle
07: {
08:
/**
09:
Constructs a needle.
10:
*/
11:
public Needle()
12:
{
13:
hits = 0;
14:
tries = 0;
15:
generator = new Random();
16:
}
17:
Continued…
Chapter 6  Iteration
67
File Needle.java
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
/**
Drops the needle on the grid of lines and
remembers whether the needle hit a line.
*/
public void drop()
{
double ylow = 2 * generator.nextDouble();
double angle = 180 * generator.nextDouble();
// Computes high point of needle
double yhigh = ylow + Math.sin(Math.toRadians(angle));
if (yhigh >= 2) hits++;
tries++;
}
/**
Gets the number of times the needle hit a line.
@return the hit count
Continued…
*/
Chapter 6  Iteration
68
File Needle.java
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55: }
public int getHits()
{
return hits;
}
/**
Gets the total number of times the needle was dropped.
@return the try count
*/
public int getTries()
{
return tries;
}
private Random generator;
private int hits;
private int tries;
Chapter 6  Iteration
69
File NeedleTester.java
01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
/**
This program simulates the Buffon needle experiment
and prints the resulting approximations of pi.
*/
public class NeedleTester
{
public static void main(String[] args)
{
Needle n = new Needle();
final int TRIES1 = 10000;
final int TRIES2 = 1000000;
Chapter 6  Iteration
Continued…
70
File NeedleTester.java
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23: }
for (int i = 1; i <= TRIES1; i++)
n.drop();
System.out.printf("Tries = %d, Tries / Hits = %8.5f\n",
TRIES1, (double) n.getTries() / n.getHits());
for (int i = TRIES1 + 1; i <= TRIES2; i++)
n.drop();
System.out.printf("Tries = %d, Tries / Hits = %8.5f\n",
TRIES2, (double) n.getTries() / n.getHits());
}
Output
Tries = 10000, Tries / Hits = 3.08928
Tries = 1000000, Tries / Hits = 3.14204
Chapter 6  Iteration
71
Self Check
9.
How do you use a random number generator
to simulate the toss of a coin?
10.
Why is the NeedleTester program not an
efficient method for computing π?
Chapter 6  Iteration
72
Answers
9.
10.
int n = generator.nextInt(2); // 0 = heads, 1 = tails
The program repeatedly calls
Math.toRadians(angle). You could simply
call Math.toRadians(180) to compute π
Chapter 6  Iteration
73
Correctness Proof

Sometimes possible to prove that a loop (or
entire program) is correct

If possible, this is way better than testing

But not practical in most realistic cases

Only feasible for relatively simple code

Seldom used in practice
 But is used in some high-security situations
Chapter 6  Iteration
74