Transcript 4b-5a-Iteration

FIT1002 2006
Objectives
By the end of this lecture, students should:
• understand iteration statements
• understand the differences of for and while
• understand nested iteration
• be able to write simple code with iterations
Reading: Savitch, Sec. 3.3
1
FIT1002 2006
The while Statement
Implements the repetition in an algorithm
Repeatedly executes a block of statements
Tests a condition (Boolean expression) at the start of each
iteration
Terminates when condition becomes false (zero)
2
FIT1002 2006
Example: averaging numbers
Read in numbers, add them, and
return their average
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
3
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
Iteration Control
Initialize
Check condition
Update
return sum/count
4
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
}
5
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
}
6
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
}
7
FIT1002 2006
Aside: Keyboard Input
Java 5 provides a convenient way for simple keyboard input,
the Scanner class.
• you must “import java.util.Scanner;”
This makes the Scanner class known to your program.
More about this later…
• You create a new scanner object for a particular input
stream (“channel”):
Scanner console = new Scanner(System.in);
• new values can then be read from the Scanner object using
–
–
–
–
console.nextInt (Integer)
console. nextFloat (Float)
console. nextLine (String)
etc (see Java API doc at Sun’s web site)
8
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
return sum/count
}
}
Same as: count = count + 1;
Decrement: count --; (Savitch, p 30-33)
9
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
return sum/count
}
}
Other contracted forms: +=, -=, etc
we could write:
sum += console.nextInt();
10
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
}
The whole block to be repeated is marked
by braces { … } unless it is a single
statement.
11
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max is number of numbers to read
set sum to 0
set count to 0
Don’t forget a cast is required to obtain a
while (count < max) float division and result. What would
{
happen without it?
input nextNum
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
add nextNum to sum
add 1 to count
}
return sum/count
}
}
12
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
max
count
newInt
2
0
????
sum
0
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
sum = sum + newInt;
count ++;
}
return
sum/(float)count;
}
}
13
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max
count
newInt
sum
2
0
????
0
2
0
3
0
console.nextInt();
sum = sum + newInt;
count ++;
}
return
sum/(float)count;
}
}
14
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max
count
newInt
sum
2
0
????
0
2
0
3
0
2
0
3
3
console.nextInt();
sum = sum + newInt;
count ++;
}
return
sum/(float)count;
}
}
15
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
max
count
newInt
sum
2
0
????
0
2
0
3
0
2
0
3
3
2
1
3
3
sum = sum + newInt;
count ++;
}
return
sum/(float)count;
}
}
16
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
max
count
newInt
2
1
3
sum
3
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
sum = sum + newInt;
count ++;
}
return
sum/(float)count;
}
}
17
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
max
count
newInt
sum
2
1
3
3
2
1
6
3
console.nextInt();
sum = sum + newInt;
count ++;
}
return
sum/(float)count;
}
}
18
FIT1002 2006
Example: averaging
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
max
count
newInt
2
1
3
3
2
1
6
3
2
1
6
9
console.nextInt();
2
2
6
9
sum = sum + newInt;
count ++;
2
2
6
9
public float avg(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
}
return
sum/(float)count;
}
}
sum
The loop now terminates
as the condition is false
and the next statement
after the loop is executed
(here: return).
19
FIT1002 2006
Common Mistakes in while – “one
liners”
while (num < minimum)
num = console.nextInt();
System.out.println(“Number must be greater than “ + minimum);
System.out.println(“Please try again.”);
while (num < minimum)
{
num = console.nextInt();
}
System.out.println(“Number must be greater than “ + minimum);
System.out.println(“Please try again.”);
20
FIT1002 2006
Common Mistakes in while – “one
liners”
while (num < minimum)
num = console.nextInt();
System.out.println(“Number must be greater than “ + minimum);
System.out.println(“Please try again.”);
while (num < minimum)
{
num = console.nextInt();
System.out.println(“Number must be greater than “ + minimum);
System.out.println(“Please try again.”);
}
21
FIT1002 2006
Common Mistakes in while
extra semi-colon;
while (num < minimum) ;
{
num = console.nextInt();
System.out.println(“Number must be greater than “ + minimum);
System.out.println(“Please try again.”);
}
Marks the end of the
while-block -- usual
cause of infinite loops
22
FIT1002 2006
The for Statement
Form of loop which allows for initialization and iteration
control
Syntax:
for ( initialization; condition; update )
{
instruction block
Careful! A semi-colon
}
here marks the end of
the instruction block!
23
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
public float averageWithFor(int max)
{
int count;
int sum=0;
for (count=0; count < max; count++)
{ int newInt = console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
return sum/count
24
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
Initialize
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
public float averageWithFor(int max)
{
int count;
int sum=0;
for (count=0; count < max; count++)
{ int newInt = console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
return sum/count
25
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
Test
public float averageWithFor(int max)
{
int count;
int sum=0;
for (count=0; count < max; count++)
{ int newInt = console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
Test is performed
before the body
26
FIT1002 2006
Example: averaging
Read in numbers, add them, and
return their average
Update
max is number of numbers to read
set sum to 0
set count to 0
while (count < max)
{
input nextNum
add nextNum to sum
add 1 to count
}
return sum/count
public float averageWithFor(int max)
{
int count;
int sum=0;
for (count=0; count < max; count++)
{ int newInt = console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
Update is performed
after the body
27
FIT1002 2006
while and for
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
public float averageWhile(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
public float averageFor(int max)
{
int count;
int sum=0;
for (
count=0;
count < max;
count++)
{ int newInt =
console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
}
28
FIT1002 2006
while and for
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
Initialize
public float averageWhile(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
Initialize
public float averageFor(int max)
{
int count;
int sum=0;
for (
count=0;
count < max;
count++)
{ int newInt =
console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
}
29
FIT1002 2006
while and for
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
Test
public float averageWhile(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
Test
public float averageFor(int max)
{
int count;
int sum=0;
for (
count=0;
count < max;
count++)
{ int newInt =
console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
}
30
FIT1002 2006
while and for
import java.util.Scanner;
public class Test
{
Scanner console = new
Scanner(System.in);
Update
public float averageWhile(int max)
{
int count=0;
int sum=0;
while (count < max)
{ int newInt =
console.nextInt();
sum = sum + newInt;
count ++;
}
return sum/(float)count;
}
Update
public float averageFor(int max)
{
int count;
int sum=0;
for (
count=0;
count < max;
count++)
{ int newInt =
console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
}
31
FIT1002 2006
For / While Equivalence
Every For loop can always be rewritten as a while loop
…and vice versa
For loops are typically preferred for any form of “counting”
(I.e. where the number of iterations is known)
32
FIT1002 2006
Local Loop Variables
You can declare a new counter variable locally for the loop
body. Thjs is done in the for initalization (good style!)
public float averageWithFor(int max)
{
int count;
int sum=0;
for (count=0; count < max; count++)
{ int newInt = console.nextInt();
sum = sum + newInt;
}
return sum/(float)count;
}
public float averageWithFor(int max)
{
int sum=0;
for (int count=0; count < max; count++)
{ int newInt = console.nextInt();
sum = sum + newInt;
}
return sum/(float)max;
}
33
FIT1002 2006
do-while
There is a variant of the while statement, the do-while
statement
do
{ int newInt = console.nextInt();
sum = sum + newInt;
count ++;
}
while (count < max)
The only difference to the normal while is, when the test is
executed
while:
before loop body
do-while: after loop body
A do-while body will always be executed at least once.
34
FIT1002 2006
The break / continue Statements
Implements the "exit loop" primitive.
Break causes flow of control to leave a loop block
(while or for) immediately and continue after the loop.
Continue ends only the current loop iteration and transfers
the control back to the update expression (potentially
entering the next iteration of the loop).
Style
In almost all cases using break and continue is in
bad style. They should only be used to terminate a loop in
abnormal situations.
35
FIT1002 2006
Example reciprocal
Print out the reciprocals of
numbers entered. Quit when 0
is entered
loop
{
input nextNum
if (nextNum is 0)
{
exit loop
}
else
{
output 1/nextNum
}
}
public void reciprocal()
{
while (true)
{ float newFloat = console.nextFloat();
if (newFloat==0) break;
else System.out.println( 1/newFloat);
}
System.out.println("You entered Zero!");
}
36
FIT1002 2006
Example reciprocal
Print out the reciprocals of
numbers entered. Quit when 0
is entered
loop
{
input nextNum
if (nextNum is 0)
{
exit loop
}
else
{
output 1/nextNum
}
}
“while (True)”
infinite loop
public void reciprocal()
{
while (true)
{ float newFloat = console.nextFloat();
if (newFloat==0) break;
else System.out.println( 1/newFloat);
}
System.out.println("You entered Zero!");
}
37
FIT1002 2006
Infinite Loops
while ( true )
{
...etc...etc...etc...
}
for ( ; true ; )
{
...etc...etc...etc...
}
Use an:
if ( condition )
{
break;
}
statement to break the loop
for ( ; ; )
{
...etc...etc...etc...
}
38
FIT1002 2006
Example Factorization
Write a program which prints out the prime factorization
of a number (treat 2 as the first prime)
For example,
on input 6, desired output is: 2 3
" " 24,
"
"
: 2223
" " 14, "
"
: 27
" " 23,
"
"
: 23 (23 is prime)
39
FIT1002 2006
Algorithm
input n
set factor to 2
40
FIT1002 2006
Algorithm
(cont)
input n
set factor to 2
while(some factor yet to try)
{
}
41
FIT1002 2006
Algorithm
(cont)
input n
set factor to 2
while(some factor yet to try)
{
if (n is divisible by factor)
{
output factor
set n to n / factor
}
}
42
FIT1002 2006
Algorithm
(cont)
input n
set factor to 2
while(some factor yet to try)
{
if (n is divisible by factor)
{
output factor
set n to n / factor
}
else
{
increment factor
}
}
43
FIT1002 2006
Example: factorize
input n
set factor to 2
while(some factor yet to try)
{
if (n is divisible by factor)
{
output factor
set n to n / factor
}
else
{
increment factor
}
}
public void factorize(int number)
{
int factor=2;
while (number > 1) {
if (number % factor == 0) {
System.out.println(factor);
number = number / factor;
} else factor++;
}
}
44
FIT1002 2006
Iterating over a String (For)
Many string algorithms require iteration over the characters
in a string. The for loop is ideally suited to do this.
The characters in a string can be accessed by position index
using the charAt method.
Indices run from 0 to length -1!
char charAt(int index)
The length of the string can be obtained with the length
method
int length()
45
FIT1002 2006
Example: CountConsonantsAndVowels
Count the number of consonants and the number of vowels
in a file
Non-alphabetic characters should not be counted
46
FIT1002 2006
Algorithm: count consonants and vowels
input String
set consonantCount to 0
set vowelCount to 0
loop over all characters in the string
{
set ch as next character in string
if (ch is a vowel)
{
increment vowelCount
}
else if (ch is a consonant)
{
increment consonantCount
}
}
output consonantCount, vowelCount
47
FIT1002 2006
input String
set consonantCount to 0
set vowelCount to 0
public void stringCount() {
String s = console.nextLine();
int vowels=0;
int consonants=0;
loop over all characters in the string
{
for (int i=0; i< s.length(); i++) {
char c = s.charAt(i));
c = Character.toLowerCase( c );
if (Character.isLetter( c ))
if (c=='a' || c=='e' ||
c=='i' || c =='o' ||
c=='u')
vowels ++;
else
consonants++;
}// for loop ends here
set ch as next character in string
if (ch is a vowel)
{
increment vowelCount
}
else if (ch is a consonant)
{
increment consonantCount
}
System.out.println(s+" has”+
vowels+" Vowels and "+
consonants+" Consonants.");
}
output consonantCount, vowelCount
}
Note the use of the service
functions in the Character class.
Try to find these in the API
definition on the web!
48
FIT1002 2006
Iterating over a String (While)
Re-write the stringCount Method with a while loop instead
of a for loop
49
FIT1002 2006
Nested Loops
Loops can be placed inside other loops
The break statement applies to the innermost enclosing
while or for statement
50
FIT1002 2006
Example: rectangle
Print an m by n rectangle of asterisks
input width and height
for each row
{
for each column in the current row
{
print an asterisk
}
start next row
}
public void rectangle(int width, int height) {
for (int row=1; row <= height; row++) {
for (int column=1; column <= width; column++)
System.out.print("*");
System.out.println();
}
}
51
FIT1002 2006
Nested Loops: Loop Dependencies
An inner loop can depend on an outer (enclosing) loop.
How would you modify “rectangle” into a method to print a
triangle?
*
**
Modify this to print a triangle of asterisks
***
****
input width and height
*****
for each row
******
{
*******
for each column in the current row
{
********
print an asterisk
}
*********
start next row
**********
}
52
FIT1002 2006
Example: triangle
Print an m row triangle of asterisks
input height
for each row
{
for each column in the current row
{
print as many asterisk as the number of the row
}
start next row
}
53
FIT1002 2006
Example: triangle
Print an m row triangle of asterisks
input height
for each row
{
for each column in the current row
{
print as many asterisk as the number of the row
}
start next row
}
public void triangle(int height) {
for (int row=1; row <= height; row++) {
for (int column=1; column <= row; column++)
System.out.print("*");
System.out.println();
}
}
54