Iteration

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
  
  

Investment with Compound Interest

while Statement

File Investment.java

File InvestmentTest.java

Flowchart for while Loop

Syntax 6.1. The while Statement

while (balance < targetBalance)

{

   year++;

   double interest = balance * rate / 100;

   balance = balance + interest;

}

Common Error: Infinite Loop

Common Error: Off-by-1 Error

• year = 0;
  while (balance < targetBalance)
  {
     year++;
     double interest = balance * rate / 100;
     balance = 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
  

do Statement

do 
   statement
while (condition);

Example: Validate input

double value;
do
{
   String input = JOptionPane.showInputDialog(
      "Please enter a positive number");
   value = Integer.parseInt(input);
}
while (input <= 0);

Flowchart for do Loop

for Statement

• for (initialization; condition; update)
     statement
• Example:
  for (int i = 1; i <= n; i++)
  {
     double interest = balance * rate / 100;
     balance = balance + interest;
  }
• Equivalent to
  initialization;
  while (condition)
  { statement; update; }
  

Flowchart for for Loop

File Investment.java

File InvestmentTest.java

Syntax 6.2. The for Statement

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);
• A missing semicolon
  for (i = 1; i <= 10; sum = sum + i++)
  System.out.println(sum);
  

Nested Loops

• Create triangle pattern
  []
  [][]
  [][][]
  [][][][]
• Loop through rows
  for (int i = 1; i <= n; i++)
  {
     // make triangle row
  }
• Make triangle row is another loop
  for (int j = 1; j <= i; j++)
     r = r + "[]";
  r = r + "\n";
• Put loops together => Nested loops

File Triangle.java

File TriangleTest.java

Reading Input Values

boolean done = false;
while (!done)
{
   String input = read input;
   if (end of input indicated)
      done = true;
   else
   {
      process input
   }
}

"Loop and a half"

File DataSet.java

File InputTest.java

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
  }
  

File InputTest.java

Traversing Characters in String

• s.charAt(i) is the ith character of the string s

• for (int i = 0; i < s.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

Random Numbers

• Random number generator
  Random generator = new Random();
  int n = generator.nextInt(a);
     // 0 <= n < a
  double x = generator.nextDouble();
     // 0 <= x < 1
  
• Throw die (random number between 1 and 6)
  int d = 1 + generator.nextInt(6);
  

File Die.java

File DieTest.java

Buffon Needle Experiment

Needle Position

• Needle length = 1, distance between lines = 2
  
• Generate random y_low  between 0 and 2
• Generate random angle a between 0 and 180 degrees
• y_high  = y_low  + sin( a)
• Hit if y_high >= 2
  

File Needle.java

File NeedleTest.java

1	/**
2	This program simulates the Buffon needle experiment
3	and prints the resulting approximations of pi.
4	*/
5	public class NeedleTest
6	{
7	public static void main(String[] args)
8	{
9	Needle n = new Needle();
10	final int TRIES1 = 10000;
11	final int TRIES2 = 100000;
12
13	for (int i = 1; i <= TRIES1; i++)
14	n.drop();
15	System.out.println("Tries / Hits = "
16	+ (double)n.getTries() / n.getHits());
17
18	for (int i = TRIES1 + 1; i <= TRIES2; i++)
19	n.drop();
20	System.out.println("Tries / Hits = "
21	+ (double)n.getTries() / n.getHits());
22	}
23	}