Transcript Chapter 6

Chapter 6
Iteration
Chapter 6 Assignment 1
• Read 6.1 – 6.5
• Pages 276 – 278 # R6.2-6.5, R6.8, R6.13
• Due November 27, 2012
• Loops and Nested Loops Worksheet
• Due November 30th.
• Read 6.6 – 6-.7
• Page 278 do # R6.14 and R6.18
• Due December 3rd.
Chapter Goals
To be able to program loops with the while ,
for , and do statements
To avoid infinite loops and off-by-one errors
To understand nested loops
To learn how to process input
To implement simulations
To use a debugger
Conditional Control
• The if statement and if/else statement
allows a statement or a block of statements
to be executed conditionally based on a
Boolean test.
if (grade >= 0 && grade <= 100)
{
//valid grade
}
Iterative Control: while
• The while statement repeatedly executes a
statement or block of statements while the
Boolean test evaluates to true.
int sum = 0;
int numGrades = 0;
//get grade from user
while (grade >= 0 && grade <= 100)
{
sum += grade;
numGrades++;
//get grade from user
}
// find the average of the grades
Investment with Compound
Interest
Invest $10,000, 5% interest, compounded annually
Year Balance
0
$10,000
1
$10,500
2
$11,025
3 $11,576.25
When will the balance be at least $20,000?
while Statement
while (condition)
statement;
repeats the statement while the condition is
true
while (balance < targetBalance)
{
year++;
double interest = balance * rate / 100;
balance += interest;
}
Semantics of while loop
(Owen
Astrachan:Tapestry)
if (test)
{
statements;
}
while (test)
{
statements;
}
test
false
true
Statement list
Next statement
test
false
true
Statement list
Next statement
Common Error: Infinite Loop
while (year < 20)
{
balance += balance * rate / 100;
}
while (year > 0)
{
year++; // oops, meant --
}
Loops run forever--must terminate
program
Common Error: Off-by-1
Error
 year = 0;
while (balance < targetBalance)
{
year++;
double interest = balance * rate / 100;
balance += interest;
}
System.out.println("Reached target after "
+ year + " years.");
 Should year start at 0 or 1?
 Should the test be < or <=?
Avoiding Off-by-1 Error
 Run through a simple example:
target balance = $20,000, interest rate
50%
after one year: balance = $15,000
after two years: balance = $22,500
Therefore: year must start at 0
 interest rate 100%
after one year: balance = $20,000
loop should stop
Therefore: must use <
 Think, don't compile and try at random
•Developing Loops
Owen Astrachan
• Some loops are easy to develop code for, others are
not.
– Sometimes the proper loop test and body are
hard to design.
• Practice helps, but
– Good design comes from experience; Experience
comes from bad design.
• There are other looping statements in addition to
while, but they don’t offer anything more
powerful, just some syntactic convenience.
– for loop
– do-while loop
The for loop
• Many times, the exact number of iterations is known
before loop begins. This indicates that a for loop may
be our best choice.
• public void moveCat(int x)
{
final int OFF_SCREEN = 30;
final int SMALL_AMOUNT = 2;
for(int y = 1; y <= OFF_SCREEN; y++)
{
face.moveHorizontal(SMALL_AMOUNT);
body.moveHorizontal(SMALL_AMOUNT);
ear1.moveHorizontal(SMALL_AMOUNT);
ear2.moveHorizontal(SMALL_AMOUNT);
leg1.moveHorizontal(SMALL_AMOUNT);
leg2.moveHorizontal(SMALL_AMOUNT);
}
}
The while loop – The for loop
int k = 0;
while (k < TIMES)
{
// do stuff;
k += 1;
}
for(int k=0; k < TIMES; k++)
{
// do stuff
}
• The for loop has the initialization, test, update
in one place.
Flowchart for for Loop
Rewrite as a while loop.
int sum = 0;
for(int x = 1; x <= 10; x++)
{
sum += x;
}
Rewrite as a while loop.
int sum = 0;
for(int x = 1; x <= 10; x++)
{
sum += x;
}
the result?
Rewritten as a while:
int sum = 0;
int x = 1;
while(x <= 10)
{
sum+=x;
x++;
}
Rewrite as a for loop.
int sum = 0;
int x = 0;
while (x <= 10)
{
System.out.println("X");
x++;
}
Rewritten as a for loop
int sum = 0;
for(int x = 0; x <= 10; x++)
{
System.out.println(“X”);
}
Common Errors: Semicolons
• A semicolon that shouldn't be there
sum = 0;
for (i = 1; i <= 10; i++);
sum = sum + i;
System.out.println(sum);
The do-while loop
• The while loop may never execute,
some loops should execute at least
once.
do
{
// enter a grade
}
while (grade < 0 || 100 < grade);
– Execute while the test/guard is true, in
example above what must be true when
loop terminates (de Morgan) ?
Flowchart for do Loop
Do
Statement(s)
True
While
condition
False
Rewrite as do…while loop
for (int x = 1; x <= 10; x++)
{
sum += x;
}
Rewrite as do…while loop
for (int x = 1; x <= 10; x++)
{
sum += x;
}
int x = 1;
do
{
sum += x;
x++;
}
while (x <= 10);
Know when to use each type of
loop!
• for loop
• while loop
• do..while loop
Know when to use each type of
loop!
• for loop
– you know exactly how many times loop is to
be executed.
• while loop
– loop may be executing zero times
• do..while loop
– loop must execute at least once
Scope of for loop variables
• If a variable is declared in the for loop
header, its scope extends to the end of
the for loop.
for(int x = 1; x <= n; x++)
{
// x can be accessed here
}
// x is no longer defined.
Scope of for loop variables
• If a variable is declared outside the for
loop header, its scope extends outside the
end of the for loop.
int x;
for(x = 1; x <= n; x++)
{
// x can be accessed here
}
// x is still in scope here
Nested loops
• Sometimes one loop occurs in another
– Generating tables
for(int row = 1; row <= 6; row++)
{
for(int col = 1; col <= 6; col++)
{
System.out.print ("\t" + row*col);
}
System.out.println();
}
– What’s printed? What’s the purpose of the inner loop?
Nested loops
for(int row = 1; row <= 6; row++)
{
for(int col = 1; col <= 6; col++)
{
System.out.print ("\t" + row*col);
}
System.out.println();
}
1
2
3
4
5
6
2
3
4
5
6
4
6
8
10
12
6
9
12
15
18
8
12
16
20
24
10
15
20
25
30
12
18
24
30
36
Practice
int i, j, product;
int sum = 0;
for (int i = 1; i <= 4; i++)
{
for (j = 1; j <= 3; j++)
{
product = i * j;
sum += product;
}
}
More Practice
int x, y, z;
for (x = 1; x <= 2; x++)
for (y = 1; y <= 2; y++)
for (z = 1; z <= 2; z++)
System.out.println(x + " " + y + " " + z)
//OUTPUT
1 1 1
x
y
z
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2
Give output:
for(int d=1; d<=4; d++)
{
System.out.println();
for(int a=1; a<=d; a++)
{
System.out.print("*");
}
}
*
**
***
****
See File Triangle.java
and
File TriangleRunner.java
pages 245-246 in your textbook
Chapter 6 Assignment 1
• Read 6.1 – 6.5
• Pages 276 – 278 # R6.2-6.5, R6.8, R6.13
• Due November 27, 2012
• Loops and Nested Loops Worksheet
• Due November 30th.
• Read 6.6 – 6-.7
• Page 278 do # R6.14 and R6.18
• Due December 3rd.
Consider the following incomplete Word
class.
public class Word
{
public Word(String s)
{
original = s;
// more may eventually be added
here
}
// code goes here
private String original;
// more may eventually be added here
}
The incomplete Word class.
public class Word
{
public Word(String s)
{
original = s;
}
// returns the reverse of original
public String reverse()
{
//code goes here
}
// more code goes here
private String original;
}
Write a Word method to return a String
that is the reverse of the Word's original
String value.
public String reverse()
{
}
Word w = new Word("math");
w.reverse() returns "htam"
Ideas???
Guidance
• How many characters does original have?
original.length() characters
Guidance
• How do we instantiate a new String with
0 characters?
Guidance
• How do we instantiate a new String with
0 characters?
String rev = "";
or
String rev = new String();
Guidance
• How do we access one letter of the String
original?
The ith character of original is:
original.charAt(i)
returns a char
or
original.substring(i, i+1) returns a
String
Guidance
• How do we traverse the original String in
reverse order?
– Use a while loop starting with the last
character of original:
– int current = original.length()–1;
• position of last letter in original
– while (current >= 0)
• get the current character of original
• decrement current
Guidance
• How do we build the new String?
• Concatenate:
rev += original.charAt(current);
or
rev += original.substring(current, current +
1);
Guidance
• How do we return the answer?
return rev;
Write method reverse().
Is a word a palindrome……
Algorithm(s) ????????????????
Is a word a palindrome……
public boolean isPalindrome()
{
}
Is a word a palindrome……
public boolean isPalindrome()
{
String rev = reverse();
return rev.equals(original);
}
Another algorithm ???????????
Alternate palindrome algorithm
Let's consider the word:
L
E
V
E
L
Alternate palindrome algorithm
Let's consider the word:
L
E
V
E
L
Look at letters in pairs– check pairs as you go.
When you find a pair that has unequal letter
values, return false immediately!
Develop test cases
• "LEVEL"
• "MADAM"
• "A"
• ""
• State necessary preconditions
– A precondition is a condition that must be
true in order for the method to work as
intended.
• Provided to restrict the parameters of a method
Pre and Post - Conditions
• State necessary preconditions
– A precondition is a condition that must be
true in order for the method to work as
intended.
• Provided to restrict the parameters of a method
• State necessary postconditions
– A postcondition is a condition that is true after
a method has been called.
• One kind: The return value is computed correctly
A FunNumber class
with lots of fun methods!
A FunNumber class:
public class FunNumber
{
public FunNumber(int num)
{
original = num;
}
// fun methods go here
public int getValue()
{
return original;
}
private int original;
}
A FunNumber class:
• Write a fun method that will return
the sum of the positive integers less
than or equal to the FunNumber's
value.
– State precondition and postcondition
FunNumber n = new FunNumber(10);
n.sumInts()returns 55
// (1+2+3+...+10 = 55)
Problem:
• Write a fun method,
findFactorial, that will return n!
(n factorial) where n is the integer
parameter for the FunNumber
constructor.
– State precondition and postcondition
FunNumber n = new FunNumber(5);
n.findFactorial()returns 120
// (5 x 4 x 3 x 2 x 1 = 120)
Factorial
• n! = 1 x 2 x … x n is “n factorial”,
used in math, statistics.
public int findFactorial()
// precondition: n >= 0
// postcondition: returns n! (1 x 2 x … x n)
Factorial
• Return the value of a variable product
– A loop will iterate n times, mutiplying by
1, 2, …, n
– Accumulate the answer in product
• If product holds the answer,
– product == n! when the loop terminates
Factorial continued
//precondition: original >= 0
// postcondition returns original!
public int findFactorial()
{
int product = ?;
int count = 0;
//code goes here
return product;
}
Factors………
• Write a method to print all factors of
the FunNumber value.
Write the method isPrime that returns
true is the value of the FunNumber is
prime, false otherwise.
• 2 is prime, 3 is prime, 5 is prime, 17
is prime, … 137, 193?
• (1 is not prime!)
• Can you suggest an algorithm?
Some other interesting FunNumber
methods
• findNumberOfDigits returns the
number of digits in the FunNumber
value.
• findSumOfDigits returns the sum
of the digits in the FunNumber
value.
• isPerfect returns true if the
FunNumber value is a “perfect”
number, false otherwise.
Assignment 2
• Open your workspace named Chapter 6.
• Add to this, new Application projects Word
and FunNumber
• copy FunNumberClass.java and
WordClass.java into your h:\drive then
add to your projects as FunNumber.java
and Word.java
• Write a test program for each to test
these classes using input from the user.
Assingment 2 Continued
• Complete the methods stated in Word.java
• Complete the methods stated in
FunNumber.java
Random Numbers
and simulations….
Random Number Generators
• Random number generators are used to
simulate events.
• Java provides the Random class which
implements a random number generator.
• This random number generator can
produce random integers and random
double numbers.
class java.util.Random
Method
Method Summary
int nextInt(n)
Returns a random integer
in the range from 0 to n1 inclusive.
double
nextDouble()
Returns a random
floating-point number
between 0 (inclusive) and
1 (exclusive).
Sample use:
Random generator = new Random();
// Constructs the number generator.
int randInt = generator.nextInt(10);
// Generates a random integer from 0-9
inclusive.
double randDouble = generator.nextDouble();
// Generates a random double from 0(inclusive)
to 1 (exclusive).
Die class using Random
import java.util.Random;
public class Die
{
public Die(int s)
{
sides = s;
generator = new Random();
}
public int cast()
{
return 1 + generator.nextInt(sides);
}
private Random generator;
private int sides;
}
DieTester.java
/**
This program simulates casting a die ten times.
*/
public class DieTest
{
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();
}
1643226254
}
Caution:
• When writing programs that include
•
random numbers, two Random objects
created within the same millisecond will
have the same sequence of random
numbers.
If the following declarations are executed
in the same millisecond,
Random generator1 = new Random();
Random generator2 = new Random();
generator1 and generator2 will generate same
sequence of random numbers.
Die
class
using
Random
import java.util.Random;
public class Die
{
public Die(int s)
{
sides = s;
generator = new Random();
}
public int cast()
{
return 1 + generator.nextInt(sides);
}
private Random generator;
private int sides;
}
Roll two dice ten times. Record results.
Consider the following first attempt!
public class DieTestForTwo
{
public static void main(String[] args)
{
Die d = new Die(6);
Die d2 = new Die(6);
final int TRIES = 10;
for (int i = 1; i <= TRIES; i++)
{
int n = d.cast();
int n2 = d2.cast();
System.out.println(n + " " + n2);
}
System.out.println();
}
Results:
6
2
1
6
4
6
6
3
3
5
6
2
1
6
4
6
6
3
3
5
Results:
6
2
1
6
4
6
6
3
3
5
6
2
1
6
4
6
6
3
3
5
What happened?????
What happened and why?
6
2
1
6
4
6
6
3
3
5
6
2
1
6
4
6
6
3
3
5
public class DieTestForTwo
{
public static void main(String[] args)
{
Die d = new Die(6);
Die d2 = new Die(6);
final int TRIES = 10;
for (int i = 1; i <= TRIES; i++)
{
int n = d.cast();
int n2 = d2.cast();
System.out.println(n + " " + n2);
}
System.out.println();
}
}
Another attempt:
public class DieTestForTwo
{
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();
int n2 = d.cast();
System.out.println(n + " " + n2);
}
System.out.println();
}
}
New results:
2
1
3
5
6
4
2
5
3
2
1
4
3
6
6
6
2
1
6
1
Is this the desired outcome?
The difference?
2
1
3
5
6
4
2
5
3
2
1
4
3
6
6
6
2
1
6
1
public class DieTestForTwo
{
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();
int n2 = d.cast();
System.out.println(n + " " + n2);
}
System.out.println();
}
}
Remember….
• It is a better idea to share a single random
number generator in the entire program.
• We rarely want to generate identical
sequences of random numbers!
Math.random()
• Generates a random number [0, 1)
• To use:
double num1 = Math.random();
• If you want an int between 1 and 100:
int num2 = (int)(Math.random() * 100);
• This is part of the AP subset
Not Tested -- String Tokenization
 StringTokenizer breaks up string into tokens
 By default, white space separates tokens
 "4.3 7 -2" breaks into three tokens:
"4.3", "7", "-2"
StringTokenizer tokenizer = new StringTokenizer();
while (tokenizer.hasMoreTokens())
{
String token = tokenizer.nextToken();
// process token
}
Traversing Characters in String
s.charAt(i) is the ith character of the string s
for (int i = 0; i < .length(); i++)
{
char ch = s.charAt(i);
// process ch
}
 Example: Count vowels
int vowelCount = 0;
String vowels = "aeiouy";
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (vowels.indexOf(ch) >= 0)
vowelCount++;
}
 s.indexOf(ch) is the index of the
first occurrence of ch in s, or -1 if
ch doesn't occur in s
Programming Assignment
• Word and Fun Number Labs
• Due December 5, 2012
• Test on Chapter 6, Thursday and Friday,
December 6th and 7th.