Transcript CS303E

CS 303E
Lecture 8:
Loops
Self-referentially, short for GNU's not UNIX,
a Unix-compatible software system developed
by the Free Software Foundation (FSF). Which
could be expanded to GNU’s not UNIX’s not UNIX,
which could be expanded to
GNU's not UNIX’s not UNIX’s not UNIX, which
could be expanded to…….
CS303E
Loops
1
Iteration – a Basic Operation
Example of iteration – building a fence:
Move tools and materials to starting
point.
Initialization
Install first fence post.
Termination
condition
Repeat until finished:
Move to position of next fence post.
Install next fence post.
Loop
Body of
Install fencing between new post
loop is
and previous post.
repeated.
CS303E
Loops
2
while Loop — Syntax
while ( boolean_expression )
statement;
or
Continuation
condition
Loop body
while ( boolean_expression )
{ statement;
...
}
CS303E
Loops
3
Syntax and Semantics of
while Statements
while (<Boolean expression>)
<statement>
while (<Boolean expression>){
<statement 1>
.
<statement n>
}
CS303E
Loops
true
?
false
statement
4
while Loop for Building Fence
Move tools and materials to starting point.
Install first fence post.
Continuation
while (not finished)
condition
{ Move to position of next fence post;
Install next fence post;
Install fencing between new post
and previous post;
}
CS303E
Loops
5
Loops — two basic patterns
Count-controlled loop:
Number of iterations is determined before
the loop starts.
Counts each iteration in a counter variable.
Stops when the desired number of iterations
has been performed.
Event-controlled loop:
Before each iteration, checks to see whether
some event has occurred.
Continues until that event occurs.
Number of iterations not known beforehand.
CS303E
Loops
6
Count-controlled loop pattern
counter = initialValue;
other initialization;
while ( counter <= finalValue )
{ do computation;
increment counter;
}
Number of iterations is:
finalValue – initialValue + 1
CS303E
Loops
7
Designing Correct Loops
Initialize all variables properly
• Plan how many iterations, then set the counter
and the limit accordingly
Check the logic of the termination
condition
Update the loop control variable properly
CS303E
Loops
8
Count controlled loop example
Specification: Sum the squares of the first 10
positive integers.
Algorithm:
int sum = 0;
// initialize sum so far
int count = 1;
// initialize counter
while ( count <= 10 )
// 10 = final value
{ sum = sum + (count * count); // do computation
count = count + 1; // increment counter
}
sumField.setNumber(sum);
CS303E
Loops
9
Off-by-One Error
int counter = 1;
while (counter <= 10){ //Executes 10 passes
<do something>
counter++;
}
int counter = 1;
while (counter < 10){ //Executes 9 passes
<do something>
counter++;
}
CS303E
Loops
10
Example – Sum powers of 2
Specification: Sum the first max powers of 2: 2 + 4 + 8 + . . .
Algorithm in pseudo-code:
1. Get value for max;
2. Set count to 1, sum to 0, power to 1;
3. While ( count <= max )
{ a. Multiply power by 2;
// 2, 4, 8, . . .
b. Increment sum by power; // 2 + 4 + 8 + . . .
c. Increment count by 1;
// 1, 2, . . ., max
}
4. Display sum;
CS303E
Loops
11
Code – Sum powers of 2
Specification: Sum the first max powers of 2: 2 + 4 + 8 + . . .
Code:
max = maxField.getNumber();
int count = 1, sum = 0, power = 1;
while ( count <= max )
{ power = power * 2;
// 2, 4, 8, . . .
sum = sum + power;
// 2 + 4 + 8 + . . .
count = count + 1;
// 1, 2, . . ., max
}
sumField.setNumber (sum);
CS303E
Loops
12
Tracing the loop
Suppose max = 5.
We want to calculate sum = 2 + 4 + 8 + 16 + 32.
max count power sum
Before loop starts: 5
1
1
0
After iteration 1:
5
2
2
2
After iteration 2:
5
3
4
6
...
After iteration 5:
5
6
32
62
CS303E
Loops
13
Exercises
Sum the odd numbers from 1 to 10.
Summing from 1 to N is easy. (Thanks to
Gauss)
n
 i  (n  1)  n 2
i 1
CS303E
Loops
14
Infinite Loop
int counter = 1;
while (counter <= 10){// Executes 5 passes
<do something>
counter = counter + 2;
}
int counter = 1;
while (counter != 10){// Runs forever
<do something>
counter = counter + 2;
}
In general, avoid using != in loop termination conditions.
CS303E
Loops
15
Event-controlled loop pattern
initialization;
while ( event has not occurred )
{ do work; }
Work must eventually cause event to occur.
HelloWorld in an Event Driven
Programming World
while(true){
System.out.print(“Hello World!! “);
}
CS303E
Loops
16
Example – Sum powers of 2
Specification: Sum the powers of 2 up to a power <= limit.
Algorithm in pseudo-code:
1. Get value for limit;
2. Set sum to 0, power to 2;
3. While ( power <= limit )
{ a. Increment sum by power; // 2 + 4 + 8 + . . .
b. Multiply power by 2;
// 4, 8, 16, . . .
}
4. Display sum;
CS303E
Loops
17
Code – Sum powers of 2
limit = inputField.getNumber();
sum = 0;
power = 2;
while ( power <= limit )
{ sum = sum + power;
power = power * 2;
}
outputField.setNumber (sum);
CS303E
Loops
// 2 + 4 + 8 + . . .
// 4, 8, 16, . . .
18
Mixing the two types of loops
Specification: Sum the first powers of 2, so long as
power <= limit but not more than 10 powers.
max = maxField.getNumber();
limit = limitField.getNumber();
sum = 0; power = 2; count = 1;
while ( power <= limit && count <= max )
{ sum = sum + power;
// 2 + 4 + 8 + . . .
power = power * 2;
// 4, 8, 16, . . .
count = count + 1;
// 2, 3, 4, . . .
}
outputField.setNumber (sum);
CS303E
Loops
19
CS 303E
Lecture 9:
Loops II
"An apprentice carpenter may want only a hammer
and saw, but a master craftsman employs many
precision tools. Computer programming likewise
requires sophisticated tools to cope with the
complexity of real applications,and only practice with
these tools will build skill in their use."
- Robert L. Kruse,
Data Structures and Program Design
CS303E
Loops
20
Prime Numbers
Write a program to determine if a given
number is prime.
Analysis / Design (algorithm)
CS303E
Loops
21
Prime Number Implementation
CS303E
Loops
22
Other Loops
Java provides syntax for two other types of
loops
do - while loop
for loop
Any of these could be rewritten as a while loop.
CS303E
Loops
23
do-while Loop
Syntax
do
{ //body of loop
First_Statement;
...
Last_Statement;
} while(Boolean_Expression);
Initialization code may precede loop body
CS303E
Loops
24
do-while Loop
Loop test is after loop body so the body must
execute at least once (minimum of at least one
iteration)
May be either count controlled or event
controlled loop
• Good choice for event controlled loop
Something in body of loop should eventually
cause Boolean_Expression to be false
CS303E
Loops
25
do-while Example
int count = 1;
int number = 10;
do //Display integers 1 - 10 on one
line
{
System.out.print(count + “, “ );
count++;
}while(count <= number);
Note System.out.print() is used and not
System.out.println() so the numbers will
all be on one line
CS303E
Loops
26
for loop
for — A simpler count-controlled loop.
The following two loops are equivalent:
i = 1;
while ( i <= n )
{ work
i = i + 1;
}

for ( i = 1; i <= n; i = i+1 )
{
work
}
Still need while for event-controlled loops and mixed
loops (count- and event-controlled).
CS303E
Loops
27
for Loop Syntax and Semantics
for (initialization statement;
termination condition;
update statement)
loop body statement(s)
initialization
statement
termination
condition
false
true
loop body
statement(s)
update
statement
CS303E
Loops
28
for Example
Compute and output first 10 integers and their squares:
for (int i = 1; i <= 10; i++)
System.out.println(i + " " + i*i + "\n");
initialization statement  int i = 1;
termination condition  i <= 10
update statement  i++ (or i = i + 1)
CS303E
Loops
29
for loop
Initialization, loop test, and loop counter change
are part of the syntax. Contrast with while loop.
Execution sequence:
1. Initialization- executes only the first iteration of the loop
2. Boolean_Expression - the loop test
3. loop body - execute only if loop test is true
4. After_Loop_Body - typically changes the loop counter
5. Boolean_Expression - Repeat the loop test (step 2), etc.
CS303E
Loops
30
Another for Example
Count down from 9 to 0
for(int count = 9; count >= 0; count--)
{
System.out.print("T = " + count);
System.out.println(" and counting");
}
System.out.println("Blast off!");
CS303E
Loops
31
Testing Loops
Check with small values or boundary values (1,
0, -1, limit).
Find a formula for the n-th iteration.
Display a trace if things aren’t working.
• System.out.println(“x = “ + x + “ y = “ + y);
where x and y are the variables of concern.
CS303E
Loops
32
A Tester Program
import BreezyGUI.*;
public class Tester{
public static void main(String[] args){
int counter = 1;
while (counter <= 10){
System.out.println("Counter = " + counter);
counter = counter + 2;
}
GBFrame.pause();
}
}
A non-GUI program for trying things out quickly.
CS303E
Loops
33
Text Areas
Another window component.
TextArea areaName = addTextArea (
“initial value”, row, col, width, height);
Like a text field, except has scroll bars and can
display any width and number of rows of text.
May want width and/or height > 1.
A part of the Java awt, as is Label, TextField,
Button. BreezyGUI just makes them easier to use
CS303E
Loops
34
TextArea methods
setText (aString) -- void (no value returned).
getText () -- returns String.
append (aString) -- void (no value returned).
Appends aString to the end of the TextArea.
Remember, to go to next line you need \n
CS303E
Loops
35
Output 10 Numbers
to a Text Area
TextArea outputArea =
addTextArea("", 1,1,2,5);
for (int i = 1; i <= 10; i++)
outputArea.append(i + "\n");
CS303E
Loops
36
Output 10 Numbers to a Text Area
TextArea outputArea
= addTextArea("", 1,1,2,5);
for (int i = 1; i <= 10; i++)
outputArea.append(i + "\n");
// or
String outputStr = "";
for (int i = 1; i <= 10; i++)
outputStr = outputStr + i + "\n";
outputArea.setText(outputStr);
CS303E
Loops
37
Method Format.justify
Format is part of the BreezyGUI package
Justify data (left, right, or centered) in a field of width
characters, with precision decimal places.
String justify (
char alignment,
// ‘l’ | ‘c’ | ‘r’
type data,
// data to be justified
int width,
// field width
int precision)
// decimal places (double only)
type = String or char or long or double
CS303E
Loops
38
Format.justify
Format.justify(<a letter>, <a string>, <columns>)
Format.justify(<a letter>, <an int>, <columns>)
Format.justify(<a letter>, <a double>, <columns>, <precision>)
These methods return String objects.
CS303E
Loops
39
Format.justify
Format.justify(<a letter>, <a string>, <columns>)
Format.justify(<a letter>, <an int>, <columns>)
Format.justify(<a letter>, <a double>, <columns>, <precision>)
Format.justify('l', 34, 4)
"34
Format.justify('r', 34, 4)
"
Format.justify('c', 34, 4)
" 34 "
Format.justify('r', 34.346, 7, 2)
"
CS303E
Loops
"
34"
34.35"
40
The Two Versions
while (counter <= 20){
sum = sum + counter;
output.append(counter +
" " +
sum +
"\n");
counter++;
}
while (counter <= 20){
sum = sum + counter;
output.append(Format.justify('r', counter, 5) +
Format.justify('r', sum, 10) +
"\n");
counter++;
}
CS303E
Loops
41
Justification of Text Output
CS303E
Loops
42
Some practical considerations
when using loops
The most common loop errors are unintended infinite loops
and off-by-one errors in counting loops
Sooner or later everyone writes an unintentional infinite
loop
• To get out of an unintended infinite loop enter ^C (control-C)
Loops should tested thoroughly, especially at the boundaries
of the loop test, to check for off-by-one and other possible
errors
• "Tracing" a variable (outputting its value each time through the
loop) is a common technique to test loop counters and troubleshoot
off-by-one and other loop errors
CS303E
Loops
43