The while Loop

• Loops
  • A part of a program is repeated over and over, until a specific goal is reached
  • For calculations that require repeated steps
  • For processing input consisting of many data items

The while Loop

• Investment problem
  • You put $10,000 into a bank account that earns 5 percent interest per year. How many years does it take for the account balance to be double the original investment?
• The algorithm

  Start with a year value of 0, a column for the interest, and a balance of $10,000.
  

  year	interest	balance
  0		$10,000

• 
  Repeat the following steps while the balance is less than $20,000.
     Add 1 to the year value.
     Compute the interest as balance x 0.05 (i.e., 5 percent interest).
     Add the interest to the balance.
  Report the final year value as the answer.

The while Loop

Because the interest earned also earns interest, a bank balance grows exponentially.

The while Loop

• How can you "Repeat steps while the balance is less than $20,000?"
• With a while loop statement
• Syntax

  while (condition)
  {
     statements
  }

• As long condition is true, the statements in the while loop execute

The while Loop

• The code

  while (balance < targetBalance)
  {
     year++;
     double interest = balance * RATE / 100;
     balance = balance + interest;
  }

The while Loop

Figure 1 Flowchart of a while Loop

Syntax 6.1 The while Statement

The while Loop

• For a variable declared inside a loop body
  • Variable is created for each iteration of the loop
  • And removed after the end of each iteration

• while (balance < targetBalance)
  {
     year++;
     double interest = balance * RATE / 100;
     balance = balance + interest;
  }
  // interest no longer declared here

 

Execution of a while Loop

• Step by step execution of the investment while loop

Figure 2 Execution of the Investment loop

Section_1/Investment.java

Section_1/InvestmentRunner.java

Program Run:

• The investment doubled after 15 years

Self Check 6.4

Suppose we change the program so that the condition of the while loop is

      while (balance <= targetBalance)

What is the effect on the program? Why?

• Answer: The program prints the same output. This is because the balance after 14 years is slightly below $20,000, and after 15 years, it is slightly above $20,000.

Question Mar 13

What does the following loop print?

     int n = 1;
     while (n < 100)
     {
         n = 2 * n;
         System.out.print(n + " ");
     }

1. 2 4 8 16 32 64
2. 1 2 4 8 16 32 64 128
3. 2 4 8 16 32 64 128
4. Nothing. There is a syntax error

 

while Loop Examples

Common Error: Infinite Loops

• Example:
  • forgetting to update the variable that controls the loop

    int years = 1;
    while (years <= 20)
    {
       double interest = balance * RATE / 100;
       balance = balance + interest;
    }

• Example:
  • incrementing instead of decrementing

    int years = 20;
    while (years > 0)
    { 
       double interest = balance * RATE / 100;
       balance = balance + interest;
       years++;
    }

• These loops run forever – must kill program

Common Error: Off-by-One Errors

• Off-by-one error: a loop executes one too few, or one too many, times
• Example:

  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 <=?

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.
• interest rate: 100%
  
  after one year: balance is 2 * initialBalance
  loop should stop
  Therefore: must use < not <=
• Think, don't compile and try at random
  

Problem Solving: Hand-Tracing

• A simulation of code execution in which you step through instructions and track the values of the variables.
• What value is displayed?

  int n = 1729;
  int sum = 0;
  while (n > 0)
  {
      int digit = n % 10;
      sum = sum + digit;
      n = n / 10;
  }
  System.out.println(sum);

Problem Solving: Hand-Tracing - Step by Step

• Step 1
  
• Step 2
  
• Step 3
  

Problem Solving: Hand-Tracing

• Step 4
  
  
• Step 5
  
  
  

Problem Solving: Hand-Tracing

• Step 6
  
• Step 7
  
  

Problem Solving: Hand-Tracing

• Step 8
  
• Step 9
  
• Step 10
  The sum, which is 19, is printed

Self Check 6.6

Hand-trace the following code, showing the value of n and the output.

int n = 5;
while (n >= 0)
{
   n--;
   System.out.print(n);
}

• Answer:

   n output
   5
   4   4
   3   3
   2   2
   1   1
   0   0
  -1  -1

Self Check 6.7

Hand-trace the following code, showing the value of n and the output. What potential error do you notice?

int n = 1;
while (n <= 3)
{
   System.out.print(n + ", ");
   n++;
}

• Answer:

  n output
  1    1,
  2    1, 2,
  3    1, 2, 3,
  4

  There is a comma after the last value. Usually, commas are between values only.

Self Check 6.8

Hand-trace the following code, assuming that a is 2 and n is 4. Then explain what the code does for arbitrary values of a and n.

int r = 1;
int i = 1;
while (i <= n)
{
   r = r * a;
   i++;
}

• Answer:

  a n r i
  2 4 1 1
      2 2
      4 3
      8 4
     16 5
  The code computes an.

Self Check 6.9

Trace the following code. What error do you observe?

int n = 1;
while (n != 50)
{
   System.out.println(n);
   n = n + 10;
}

• Answer:

  n output
   1  1
  11 11
  21 21
  31 31
  41 41
  51 51
  61 61
  ...

  This is an infinite loop. n is never equal to 50.

Self Check 6.10

The following pseudo-code is intended to count the number of digits in the number

number n:
count = 1
temp = n
while (temp > 10)
   Increment count.
   Divide temp by 10.0.

Trace the pseudocode for n = 123 and n = 100. What error do you find?

• Answer:

  count temp
  1      123
  2      12.3
  3      1.23

  This yields the correct answer. The number 123 has 3 digits.

  count temp
  1 100
  2 10.0

  This yields the wrong answer. The number 100 also has 3 digits. The loop condition should have been while (temp >= 10).

The for Loop

• To execute a sequence of statements a given number of times
  • Could use a while loop controlled by a counter

    int counter = 1; // Initialize the counter
    while (counter <= 10) // Check the counter
    {
       System.out.println(counter);
       counter++; // Update the counter
    }

  • Use a special type of loop called for loop

    for (int counter = 1; counter <= 10; counter++)
    {
       System.out.println(counter);
    }
            

• Use a for loop when a variable runs from a starting value to an ending value with a constant increment or decrement

Syntax 6.2 for Statement

The for Loop

• The initialization is executed once, before the loop is entered
• The condition is checked before each iteration
• The update is executed after each iteration

The for Loop

• A for loop can count down instead of up

  for (int counter = 10; counter >= 0; counter--) . . .

• The increment or decrement need not be in steps of 1

  for (int counter = 0; counter <= 10; counter = counter + 2) . . .

The for Loop

• If the counter variable is defined in the loop header
  • It does not exist after the loop

    for (int counter = 1; counter <= 10; counter++)
    {
       . . .
    }
    // counter no longer declared here

• If you declare the counter variable before the loop
  • You can continue to use it after the loop

    int counter;
    for (counter = 1; counter <= 10; counter++)
    {
       . . .
    }
    // counter still declared here

The for Loop

• To traverse all the characters of a string

  for (int i = 0; i < str.length(); i++)
  {
     char ch = str.charAt(i);
     Process ch.
  }

• The counter variable i starts at 0, and the loop is terminated when i reaches the length of the string.

The for Loop

• To compute the growth of our savings account over a period of years
  • Use a for because the variable year starts at 1 and then moves in constant increments until it reaches the target

    for (int year = 1; year <= numberOfYears; year++)
    {
       Update balance.
    }

• Table of balances
  

The for Loop - Flowchart

Figure 4: Flowchart of a for loop

section_3/Investment.java

section_3/InvestmentRunner.java

Program Run:

• The balance after 20 years is 26532.98

The for Loop Examples

Qestion 2 Mar 13

How many numbers does this loop print?

for (int n = 10; n >= 0; n--)
{
   System.out.println(n);
}

1. 10 numbers
2. 11 numbers
3. 12 numbers
4. Nothing. n does not exist inside the loop

Question 1 Mar 18

Write a for loop that computes the sum of the integers from 1 to n.

Two flavors of infinite loops

       //print the numbers from 5 to 1 (inclusive)
       for (int i = 5; i > 0; i++)
       {
          System.out.print(i + " ");
       }
  

The code above is not actually an infinite loop because of integer overflow and twos comlement arithmetic
The one below is

        //print the numbers from 5 to 1 (inclusive)
        int i =  1;
        while ( i > 0)
        {
            System.out.println(i );
        }

        //find sum of numbers from 1 to 10 (inclusive of both ends)
        int sum = 0;
        int i =  1;
        while ( i <= 10)
        {
            sum = sum + i;
        }

The Do Loop

• Executes the body of a loop at least once and performs the loop test after the body is executed.
• Use for input validation
  • To force the user to enter a value less than 100

    int value;
    do
    {
       System.out.print("Enter an integer < 100: ");
       value = in.nextInt();
    }
    while (value >= 100);

• A do loop flowchart
  
  

Question 2 Mar 18

Suppose that we want to check for inputs that are at least 0 and at most 100. What should you use as the while loop condition

int value;
do
{
   System.out.print("Enter an integer < 100: ");
   value = in.nextInt();
}
while (...);

1. while (value <= 0 && value >= 100);
2. while (value <= 0 || value >= 100);
3. while (value < 0 || value > 100);
4. while (value < 0 && value >100);
5. Something else

Self Check 6.17

Rewrite the input check do loop using a while loop. What is the disadvantage of your solution?

int value;
do
{
   System.out.print("Enter an integer < 100: ");
   value = in.nextInt();
}
while (value >= 100);

• Answer:

  int value = 100;
  while (value >= 100)
  {
     System.out.print("Enter a value < 100: ");
     value = in.nextInt();
  }

  Here, the variable value had to be initialized with an artificial value to ensure that the loop is entered at least once.

Self Check 6.18

Suppose Java didn't have a do loop. Could you rewrite any do loop as a while loop?

• Answer: Yes. The do loop

  do { body } while (condition);

  is equivalent to this while loop:

  boolean first = true;
  while (first || condition)
  {
     body;
     first = false;
  }

Application: Processing Sentinel Values

• A sentinel value denotes the end of a data set, but it is not part of the data.
• If 0 can not be part of the data set
  • keep accepting input until a 0 finishes the sequence
• If 0 is valid but no value can be negative
  • use -1 to indicate termination
• In the military, a sentinel guards a border or passage. In computer science, a sentinel value denotes the end of an input sequence or the border between input sequences.
  

 

Application: Processing Sentinel Values

• To compute the average of a set of salaries
  • use -1 to indicate termination
• Inside the loop
  • Read the input
  • process it if the input is not -1
• Stay in the loop while the sentinel value is not -1
• Initialize the input to something other than -1

section_5/SentinelDemo.java

Program Run:

• Enter salaries, -1 to finish: 10 10 40 -1
  Average salary: 20
  

Application: Processing Sentinel Values

• Using a Boolean variable to control a loop.
  • Set the variable before entering the loop
  • Set it to the opposite to leave the loop.

    System.out.print("Enter salaries, -1 to finish: ");
    boolean done = false;
    while (!done)
    {
       value = in.nextDouble();
       if (value == -1)
       {
          done = true;
       }
       else
       {
          Process value
       }
    }

Application: Processing Sentinel Values

• When any number can be an acceptable input
  • Use a sentinel value that is not a number (such as the letter Q)
  • in.hasNextDouble() returns false if the input is not a floating-point number
  • Use this loop

    System.out.print("Enter values, Q to quit: ");
    while (in.hasNextDouble())
    {
       value = in.nextDouble();
       Process value.
    }

Self Check 6.21

What does the SentinelDemo.java program print when the user immediately types -1 when prompted for a value?

• Answer: No data

Question 3 Mar 18

In the example below, we use Q as the sentinal value" What happens when the user enters a X?

System.out.print("Enter values, Q to quit: ");
while (in.hasNextDouble())
{
   value = in.nextDouble();
   Process value.
}

1. An InputMismatchException will be thrown
2. The program will continue to prompt the user until he/whe enters a valid value
3. The program will terminate
4. An infinite loop results

Self Check 6.25

What is wrong with the following loop for reading a sequence of values?

System.out.print("Enter values, Q to quit: ");
do
{
   double value = in.nextDouble();
   sum = sum + value;
   count++;
}
while (in.hasNextDouble());

• Answer: If the user doesn't provide any numeric input, the call to in.nextDouble() will fail.

The "Loop and a Half" Problem

Sometimes termination condition of a loop can only be evaluated in the middle of the loop. There are different approaches:

• Use a Boolean variable

  boolean done = false;
  while (!done)
  {
     String input = in.next();
     if (input.equals("Q"))
     {
        done = true;
     }
     else
     {
        Process data.
     }
  }

The "Loop and a Half" Problem - Continued

Additional approaches:

• Combine an assignment and a test in the loop condition

  while (!(input = in.next()).equals("Q"))
  {
     Process data.
  }

• Exit the loop from the middle

  public void processInput(Scanner in)
  {
     while (true)
     {
        String input = in.next();
        if (input.equals("Q"))
        {
           return;
        }
        Process data.
     }
  }

Common Loop Algorithm: Sum and Average

• Sum - keep a running total: a variable to which you add each input value:

  double total = 0; 
  while (in.hasNextDouble()) 
  { 
     double input = in.nextDouble(); 
     total = total + input; 
  }

• Average -Find total and count how many values you have

  double total = 0;
  int count = 0;
  while (in.hasNextDouble())
  {
     double input = in.nextDouble();
     total = total + input;
     count++;
  }
  double average = 0;
  if (count > 0)
  {
     average = total / count;
  }

Common Loop Algorithm: Counting Matches

• Count how many spaces are in a string:

  int spaces = 0; 
  for (int i = 0; i < str.length(); i++) 
  {
     char ch = str.charAt(i); 
     if (ch == ' ') 
     { 
        spaces++; 
     } 
  }

Common Loop Algorithm: Counting Matches - Continued

• Count how many words in the input have at most three letters

  int shortWords = 0;
  while (in.hasNext())
  {
     String input = in.next();
     if (input.length() <= 3)
     {
        shortWords++;
     }
  }

• In a loop that counts matches, a counter is incremented whenever a match is found
  

Common Loop Algorithm: Finding the First Match

• Find the first space in a string:
• Because we do not visit all elements in the string, a while loop is a better choice than a for loop:
  

  boolean found = false; 
  char ch = '?'; 
  int position = 0; 
  while (!found && position < str.length()) 
  { 
     ch = str.charAt(position); 
     if (ch == ' ') { found = true; } 
     else { position++; } 
  }

• When searching, you look at items until a match is found.
  

Common Loop Algorithm: Prompting Until a Match is Found

• Keep asking the user to enter a positive value < 100 until the user provides a correct input:

  boolean valid = false; 
  double input = 0; 
  while (!valid) 
  { 
     System.out.print("Please enter a positive value < 100: "); 
     input = in.nextDouble(); 
     if (0 < input && input < 100) { valid = true; } 
     else { System.out.println("Invalid input."); } 
  }

• The variable input is declared outside the while loop because you will want to use the input after the loop has finished.

Common Loop Algorithm: Maximum and Minimum

• To find the largest value, update the largest value seen so far whenever you see a larger one.

  double largest = in.nextDouble();
  while (in.hasNextDouble())
  {
     double input = in.nextDouble();
     if (input > largest)
     {
        largest = input;
     } 
  }

• To find the smallest value, reverse the comparison

  double smallest = in.nextDouble();
  while (in.hasNextDouble())
  {
     double input = in.nextDouble();
     if (input < smallest)
     {
        smallest = input;
     }
  }

• There must be at least one input

Common Loop Algorithm: Maximum and Minimum

To find the height of the tallest bus rider, remember the largest value so far, and update it whenever you see a taller one.

Common Loop Algorithm: Comparing Adjacent Values

• Check whether a sequence of inputs contains adjacent duplicates such as 1 7 2 9 9 4 9:

  double input = 0; 
  while (in.hasNextDouble()) 
  { 
     double previous = input; 
     input = in.nextDouble(); 
     if (input == previous) 
     { 
        System.out.println("Duplicate input"); 
     } 
  }

• When comparing adjacent values, store the previous value in a variable.
  

Self Check 6.31

What total is computed when no user input is provided in the algorithm in Section 6.7.1?

• Answer: The total is zero.

Question 1 Mar 20

Write code to compute the total of all positive inputs?

1. Got it!
2. Worked on it but did not get the correct code
3. Did not attempt

• Answer:
  

  double total = 0;
  while (in.hasNextDouble())
  {
     double input = in.nextDouble();
     if (input > 0) { total = total + input; }
  }

Self Check 6.33

What are the values of position and ch when no match is found in the algorithm in Section 6.7.3?

• Answer: position is str.length() and ch is unchanged from its initial value, '?'. Note that ch must be initialized with some value - otherwise the compiler will complain about a possibly uninitialized variable.

Question 1 Apr 3

Write the code to find the position of the last space in a string? Don't use lastIndexOf

1. Got it!
2. Worked on it but did not get the correct code
3. Did not attempt

• Answer: Start the loop at the end of string:

  boolean found = false;
  int i = str.length() - 1;
  while (!found && i >= 0)
  {
     char ch = str.charAt(i);
     if (ch == ' ') { found = true; }
     else { i--; }
  }

Nested Loops

• One loop inside another loop
• Print a table of the powers of x, like this:
  

  x¹	x²	x³	x4
  1	1	1	1
  2	4	8	16
  3	9	27	81

  
  
• Pseudocode

  Print table header.
  For x from 1 to 10
     Print table row.
     Print new line.

• To print the values for each exponent requires a second loop

  For n from 1 to 4
     Print xn.

• The hour and minute displays in a digital clock are an example of nested loops. The hours loop 12 times, and for each hour, the minutes loop 60 times.
  

Nested Loop

section_8/PowerTable.java

Program Run:

•          1         2         3         4
          x         x         x         x
           1         1         1         1
           2         4         8        16
           3         9        27        81
           4        16        64       256
           5        25       125       625
           6        36       216      1296
           7        49       343      2401
           8        64       512      4096
           9        81       729      6561
          10       100      1000     10000
  

Question 2 Apr 3

What do the following nested loops display?

for (int i = 0; i < 3; i++)
{
   for (int j = 0; j < 4; j++)
   {
      System.out.print(i + j);
   }
   System.out.println();
}

1. 012
   123
   234
   345
   
2. 0123
   1234
   2345
3. 1234
   2345
   3456
   
4. Something else

Self Check 6.41

Write nested loops that make the following pattern of brackets:
[][][][]
[][][][]
[][][][]

• Answer:

  for (int i = 1; i <= 3; i++)
  {
     for (int j = 1; j <= 4; j++)
     {
        System.out.print("[]");
     }
     System.out.println();
  }

Nested Loop Examples

Nested Loop Examples - Continued

Question 3 Apr 3

Write code to produce this pattern

  ****
  ***
  **
  *

1. Got it!
2. Worked on it but did not get the correct code
3. Did not attempt

• Answer:
  

         final int MAX_ROWS = 4;
         for(int i = MAX_ROWS; i > 0; i --)
         {
             for (int j = i; j > 0 ; j--)
             {
                 System.out.print("*");
             }
             System.out.println();
         }

Application: Random Numbers and Simulations

• In a simulation, you use the computer to simulate an activity.
• You can introduce randomness by calling the random number generator.
• To generate a random number
  • create an object of the Random class
  • Call one of its methods
    

    Method	Returns
    nextInt(n)	A random integer between the integers 0 (inclusive) and n (exclusive)
    nextDouble()	A random floating-point number between 0 (inclusive) and 1 (exclusive)

Application: Random Numbers and Simulations

• To simulate the cast of a die:

  Random generator = new Random();
  int d = 1 + generator.nextInt(6);

• The call generator.nextInt(6) gives you a random number between 0 and 5 (inclusive).
• Add 1 to obtain a number between 1 and 6.

section_9_1/Die.java

section_9_1/DieSimulator.java

Program Run:

•    6 5 6 3 2 6 3 4 4 1

  Second Run:

     3 2 2 1 6 5 3 4 1 2

The Monte Carlo Method

Using a simulation to calculate π

• Simulate shooting a dart into a square surrounding a circle of radius 1
  
• Estimate for π is 4 x hits / tries.
• To generate a random floating-point value between -1 and 1

  double r = generator.nextDouble(); // 0 <= r < 1
  double x = -1 + 2 * r; // -1 <= x < 1

section_9_2/MonteCarlo.java

Program Run:

• Estimate for pi: 3.1504
  
  

Self Check 6.42

How do you simulate a coin toss with the Random class?

• Answer: Compute generator.nextInt(2), and use 0 for heads, 1 for tails, or the other way around.

Self Check 6.43

How do you simulate the picking of a random playing card?

• Answer: Compute generator.nextInt(4) and associate the numbers 0 . . . 3 with the four suits. Then compute generator.nextInt(13) and associate the numbers 0 . . . 12 with Jack, Ace, 2 . . . 10, Queen, and King.

Self Check 6.44

How would you modify the DieSimulator program to simulate tossing a pair of dice?

• Answer: Construct two Die objects:

  Die d1 = new Die(6);
  Die d2 = new Die(6);
  Then cast and print both of them:
  System.out.println(
  d1.cast() + " " + d2.cast());

Self Check 6.45

In many games, you throw a pair of dice to get a value between 2 and 12. What is wrong with this simulated throw of a pair of dice?

int sum = 2 + generator.nextInt(11);

• Answer: The call will produce a value between 2 and 12, but all values have the same probability. When throwing a pair of dice, the number 7 is six times as likely as the number 2. The correct formula is

  int sum = generator.nextInt(6)
  + generator.nextInt(6) + 2;

Self Check 6.46

How do you generate a random floating-point number >= 0 and < 100?

• Answer:

  generator.nextDouble() * 100.0

Using a Debugger

• Debugger: a program to execute another program and analyze its run-time behavior
• A debugger lets you stop and restart your program, see contents of variables, and step through it
• The larger your programs, the harder to debug them simply by inserting print commands
• Debuggers can be part of your IDE (e.g. Eclipse, BlueJ) or separate programs (e.g. JSwat)
• Three key concepts:
  • Breakpoints
  • Single-stepping
  • Inspecting variables

The Debugger Stopping at a Breakpoint

Figure 8
Stopping at a Breakpoint

Inspecting Variables

Figure 9 Inspecting Variables

 

Debugging

• Execution is suspended whenever a breakpoint is reached
• In a debugger, the program runs at full speed until it reaches a breakpoint
• When execution stops you can:
  • Inspect variables
  • Step through the program a line at a time
  • Or, continue running the program at full speed until it reaches the next breakpoint
• When the program terminates, the debugger stops as well
• Breakpoints stay active until you remove them
• Two variations of single-step command:
  • Step Over: skips method calls
  • Step Into: steps inside method calls

Single-step Example

• Current line:

  String input = in.next();
  Word w = new Word(input);
  int syllables = w.countSyllables();
  System.out.println("Syllables in " + input + ": " + syllables);

• When you step over method calls, you get to the next line:

  String input = in.next();
  Word w = new Word(input);
  int syllables = w.countSyllables();
  System.out.println("Syllables in " + input + ": " + syllables);

• However, if you step into method calls, you enter the first line of the countSyllables method

  public int countSyllables()
  {
     int count = 0;
     int end = text.length() - 1;
     . . .
  }

Self Check 6.47

In the debugger, you are reaching a call to System.out.println. Should you step into the method or step over it?

• Answer: You should step over it because you are not interested in debugging the internals of the println method.

Self Check 6.48

In the debugger, you are reaching the beginning of a long method with a couple of loops inside. You want to find out the return value that is computed at the end of the method. Should you set a breakpoint, or should you step through the method?

• Answer: You should set a breakpoint. Stepping through loops can be tedious.

Self Check 6.49

When using the debugger, you find that a variable has an unexpected value. How
can you go backwards to see when the variable changed?

• Answer: Unfortunately, most debuggers do not support going backwards. Instead, you must restart the program. Try setting breakpoints at the lines in which the variable is changed

Self Check 6.50

When using a debugger, should you insert statements to print the values of variables?

• Answer: No, there is no need. You can just inspect the variables in the debugger.

Self Check 6.51

Instead of using a debugger, could you simply trace a program by hand?

• Answer: For short programs, you certainly could. But when programs get longer, it would be very time-consuming to trace them manually