Chapter Goals

• To implement while, for, and do loops
• To hand-trace the execution of a program
• To learn to use common loop algorithms
• To understand nested loops
• To implement programs that read and process data sets
• To use a computer for simulations
• To learn about the debugger

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

• In a particle accelerator, subatomic particles traverse a loop-shaped tunnel multiple times, gaining the speed required for physical experiments.
• Similarly, in computer science, statements in a loop are executed while a condition is true.

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.1

How many years does it take for the investment to triple? Modify the program and run it.

• Answer: 23 years

Self Check 6.2

If the interest rate is 10 percent per year, how many years does it take for the investment to double? Modify the program and run it.

• Answer: 8 years

Self Check 6.3

Modify the program so that the balance after each year is printed. How did you do that?

• Answer:
  Add a statement
        System.out.println(balance); 
  as the last statement in the while loop.

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.

Self Check 6.5

What does the following loop print?

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

• Answer: 2 4 8 16 32 64 128

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 < targetBalance)
  {
     years++;
     balance = balance * (1 + RATE / 100);
  }
  System.out.println("The investment doubled after " 
     + year + " years.");

• Should year 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: year 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 aⁿ.

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 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.

Figure 3 Execution of a for Loop

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 loop 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

Self Check 6.11

Write the for loop of the Investment class as a while loop.

• Answer:

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

Self Check 6.12

How many numbers does this loop print?

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

• Answer: 11 numbers: 10 9 8 7 6 5 4 3 2 1 0

Self Check 6.13

Write a for loop that prints all even numbers between 10 and 20 (inclusive).

• Answer:

  for (int i = 10; i <= 20; i = i + 2)
  {
     System.out.println(i);
  }
      

Self Check 6.14

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

• Answer:

  int sum = 0;
  for (int i = 1; i <= n; i++)
  {
     sum = sum + i;
  }

Self Check 6.15

How would you modify the InvestmentRunner.java program to print the balances
after 20, 40, ..., 100 years?

• Answer:

  final int PERIODS = 5;
  for (int i = 1; i <= PERIODS; i++)
  {
      invest.waitYears(YEARS);
      System.out.printf(
         "The balance after %d years is %.2f\n",
          invest.getYears(), invest.getBalance());
  }

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);



• Figure 5 Flowchart of a do loop
  

Self Check 6.16

Suppose that we want to check for inputs that are at least 0 and at most 100. Modify the do loop for this check.

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

• Answer:
  

  do
  {
     System.out.print(
        "Enter a value between 0 and 100: ");
     value = in.nextInt();
  }
  while (value < 0 || value > 100);

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;
  }

Self Check 6.19

Write a do loop that reads integers and computes their sum. Stop when reading the value 0.

• Answer:

  int x;
  int sum = 0;
  do
  {
     x = in.nextInt();
     sum = sum + x;
  }
  while (x != 0);

Self Check 6.20

Write a do loop that reads integers and computes their sum. Stop when reading a zero or the same value twice in a row. For example, if the input is 1 2 3 4 4, then the sum is 14 and the loop stops.

• Answer:

  int x = 0;
  int previous;
  do
  {
     previous = x;
     x = in.nextInt();
     sum = sum + x;
  }
  while (x != 0 && previous != x);

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

Self Check 6.22

Why does the SentinelDemo.java program have two checks of the form salary != -1

• Answer: The first check ends the loop after the sentinel has been read. The second check ensures that the sentinel is not processed as an input value.

Self Check 6.23

What would happen if the declaration of the salary variable in SentinelDemo.java was changed to

double salary = -1;

• Answer: The while loop would never be entered. The user would never be prompted for input. Because count stays 0, the program would then print "No data".

Self Check 6.24

In the last example of this section, we prompt the user "Enter values, Q to quit: " What happens when the user enters a different letter?

• Answer: The nextDouble method also returns false. A more accurate prompt would have been: "Enter values, a key other than a digit to quit:" But that might be more confusing to the program user who would need to ponder which key to choose.

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 first 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.
     }
  }

Problem Solving: Storyboards

• A storyboard consists of annotated sketches for each step in an action sequence.
• 
  
• Developing a storyboard for your program helps you understand the inputs and outputs that are required for a program.
• Use a storyboard to answer questions about how the program should react to different inputs.

Problem Solving: Storyboards

Storyboarding for a problem to convert units of measurement.

• Show how to deal with potential confusion:
  
• Demonstrate error handling:
  

Problem Solving: Storyboards - continued

Storyboarding for a problem to convert units of measurement - part 2.

• An approach to avoid some errors:
  
• How will we exit the program:
  
  

Self Check 6.26

Provide a storyboard panel for a program that reads a number of test scores and prints the average score. The program only needs to process one set of scores. Don't worry about error handling.

• Answer: Computing the average

  Enter scores, Q to quit: 90 80 90 100 80 Q
  The average is 88
  (Program exits)

Self Check 6.27

Google has a simple interface for converting units. You just type the question, and you get the answer.

Make storyboards for an equivalent interface in a Java program. Show a scenario in which all goes well, and show the handling of two kinds of errors.

• Answer:
  
  

Self Check 6.28

Consider a modification of the program in Self Check 26. Suppose we want to drop the lowest score before computing the average. Provide a storyboard for the situation in which a user only provides one score.

• Answer: One score is not enough

  Enter scores, Q to quit: 90 Q
  Error: At least two scores are required.
  (Program exits)

Self Check 6.29

What is the problem with implementing the following storyboard in Java?

• Answer: It would not be possible to implement this interface using the Java features we have covered up to this point. There is no way for the program to know when the first set of inputs ends. (When you read numbers with value = in.nextDouble(), it is your choice whether to put them on a single line or multiple lines.)

Self Check 6.30

Produce a storyboard for a program that compares the growth of a $10,000 investment for a given number of years under two interest rates.

• Answer: Comparing two interest rates
  
  

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 - 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.

Self Check 6.32

How do you compute the total of all positive inputs?

• 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.

Self Check 6.34

What is wrong with the following loop for finding the position of the first space in a string?

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

• Answer: The loop will stop when a match is found, but you cannot access the match because neither position nor ch are defined outside the loop.

Self Check 6.35

How do you find the position of the last space in a string?

• 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--; }
  }

Self Check 6.36

What happens with the algorithm in Section 6.7.6 when no input is provided at all? How can you overcome that problem?

• Answer: The initial call to in.nextDouble() fails, terminating the program. One solution is to do all input in the loop and introduce a Boolean variable that checks whether the loop is entered for the first time.

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

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
  

Self Check 6.37

Why is there a statement System.out.println(); in the outer loop but not in the
inner loop?

• Answer: All values in the inner loop should be displayed on the same line.

Self Check 6.38

How would you change the program to display all powers from x⁰ to x⁵?

• Answer: Change lines 13, 18, and 30 to for (int n = 0; n <= NMAX; n++). Change NMAX to 5.

Self Check 6.39

If you make the change in Self Check 38, how many values are displayed?

• Answer: 60: The outer loop is executed 10 times, and the inner loop 6 times.

Self Check 6.40

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();
}

• Answer:
  0123
  1234
  2345

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

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.