In this chapter you will learn how to write programs that repeatedly execute one or more statements. We will illustrate these concepts by looking at typical investment situations. Consider a bank account with an initial balance of $10,000 that earns 5 percent interest. The interest is computed at the end of every year on the current balance and then deposited into the bank account. For example, after the first year, the account has earned $500 (5 percent of $10,000) of interest. The interest gets added to the bank account. Next year, the interest is $525 (5 percent of $10,500), and the balance is $11,025.

How many years does it take for the balance to reach $20,000? Of course, it won't take longer than 20 years, because at least $500 is added to the bank account each year. But it will take less than 20 years, because interest is computed on increasingly larger balances. To know the exact answer, we will write a program that repeatedly adds interest until the balance is reached.

In Java, the while statement implements such a repetition. The construct

while (condition)
   statement

keeps executing the statement while the condition is true.

Most commonly, the statement is a block statement, that is, a set of statements delimited by { }.

In our case, we want to know when the bank account has reached a particular balance. While the balance is less, we keep adding interest and incrementing the years counter:

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

Figure 1 shows the flow of execution of this loop.

Figure 6.1. Execution of a while Loop

Here is the program that solves our investment problem.

ch06/invest1/Investment.java

1  /**
2     A class to monitor the growth of an investment that
3     accumulates interest at a fixed annual rate.
4  */
5  public class Investment
6  {
7     private double balance;
8     private double rate;
9     private int years;
10
11     /**
12        Constructs an Investment object from a starting balance and
13        interest rate.
14        @param aBalance the starting balance
15        @param aRate the interest rate in percent
16     */
17     public Investment(double aBalance, double aRate)
18     {
19        balance = aBalance;
20         rate = aRate;
21        years = 0;
22     }
23
24     /**
25        Keeps accumulating interest until a target balance has
26        been reached.
27        @param targetBalance the desired balance
28     */
29     public void waitForBalance(double targetBalance)
30     {
31        while (balance < targetBalance)
32         {
33           years++;
34           double interest = balance * rate / 100;
35           balance = balance + interest;
36         }
37      }
38
39      /**
40        Gets the current investment balance.
41        @return the current balance
42      */
43     public double getBalance()
44     {
45         return balance;
46     }
47
48     /**
49        Gets the number of years this investment has accumulated
50        interest.
51        @return the number of years since the start of the investment
52     */
53     public int getYears()
54     {
55         return years;

56       }
57    }

ch06/invest1/InvestmentRunner.java

1  /**
2     This program computes how long it takes for an investment
3     to double.
4  */
5  public class InvestmentRunner
6  {
7     public static void main(String[] args)
8     {
9       final double INITIAL_BALANCE = 10000;
10       final double RATE = 5;
11       Investment invest = new Investment(INITIAL_BALANCE, RATE);
12       invest.waitForBalance(2 * INITIAL_BALANCE);
13       int years = invest.getYears();
14       System.out.println("The investment doubled after "
15             + years + " years");
16    }
17 }

Program Run

The investment doubled after 15 years

A while statement is often called a loop. If you draw a flowchart, you will see that the control loops backwards to the test after every iteration (see Figure 2).

When you declare a variable inside the loop body, the variable is created for each iteration of the loop and removed after the end of each iteration. For example, consider the interest variable in this loop:

while (balance < targetBalance)
{
   years++;
   double interest = balance * rate / 100;
      // A new interest variable is created
      //  in each iteration
   balance = balance + interest;
} // interest no longer declared here

If a variable needs to be updated in multiple loop iterations, do not declare it inside the loop. For example, it would not make sense to declare the balance variable inside this loop.

Figure 6.2. Flowchart of a while Loop

The following loop,

while (true)

statement

executes the statement over and over, without terminating. Whoa! Why would you want that? The program would never stop. There are two reasons. Some programs indeed never stop; the software controlling an automated teller machine, a telephone switch, or a microwave oven doesn't ever stop (at least not until the device is turned off). Our programs aren't usually of that kind, but even if you can't terminate the loop, you can exit from the method that contains it. This can be helpful when the termination test naturally falls in the middle of the loop (see Special Topic 6.3 on page 245).

i = 0; sum = 0;
while (sum < 10)
{
   i++; sum = sum + i;
   Print i and sum;
}

1 1
2 3
3 6
4 10

i = 0; sum = 0;
while (sum < 10)
{
   i++; sum = sum - i;
   Print i and sum;
}

1 −1
2 −3
3 −6
4 −10
...

i = 0; sum = 0;
while (sum < 0)
{
   i++; sum = sum - i;
   Print i and sum;
}

i = 0; sum = 0;
while (sum >= 10)
{
   i++; sum = sum + i;
   Print i and sum;
}

i = 0; sum = 0;
while (sum < 10) ;
{
   i++; sum = sum + i;
   Print i and sum;
}

The while Statement

while (false) statement;

2. What would happen if RATE was set to 0 in the main method of the InvestmentRunner program?

int n = 1729;

int sum = 0;
while (n > 0)

{
   int digit = n % 10;
 
 
 

   sum = sum + digit;
   n = n / 10;
}
System.out.println(sum);

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

int years = 20;
while (years > 0)
{

years++; // Oops, should have been years--
   double interest = balance * rate / 100;
   balance = balance + interest;
}

Common Error 6.2: Off-by-One Errors

Consider our computation of the number of years that are required to double an investment:

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 at 1? Should you test for balance < 2 * initialBalance or for balance <= 2 * initialBalance? It is easy to be off by one in these expressions.

Some people try to solve off-by-one errors by randomly inserting +1 or −1 until the program seems to work. That is, of course, a terrible strategy. It can take a long time to compile and test all the various possibilities. Expending a small amount of mental effort is a real time saver.

Fortunately, off-by-one errors are easy to avoid, simply by thinking through a couple of test cases and using the information from the test cases to come up with a rationale for the correct loop condition.

Should years start at 0 or at 1? Look at a scenario with simple values: an initial balance of $100 and an interest rate of 50 percent. After year 1, the balance is $150, and 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. Hence years must start at 0, not at 1.

Note

An off-by-one error is a common error when programming loops. Think through simple test cases to avoid this type of error.

In other words, the balance variable denotes the balance afterthe end of the year. At the outset, the balance variable contains the balance after year 0 and not after year 1.

Next, should you use a < or <= comparison in the test? That is harder to figure out, because it is rare for the balance to be exactly twice the initial balance. Of course, there is one case when this happens, namely when the interest is 100 percent. The loop executes once. Now years is 1, and balance is exactly equal to 2 * initialBalance. Has the investment doubled after one year? It has. Therefore, the loop should not execute again. If the test condition is balance < 2 * initialBalance, the loop stops, as it should. If the test condition had been balance <= 2 * initialBalance, the loop would have executed once more.

In other words, you keep adding interest while the balance has not yet doubled.

Special Topic 6.1: do Loops

Sometimes you want to execute the body of a loop at least once and perform the loop test after the body was executed. The do loop serves that purpose:

do
   statement
while (condition);

The statement is executed while the condition is true. The condition is tested after the statement is executed, so the statement is executed at least once.

For example, suppose you want to make sure that a user enters a positive number. As long as the user enters a negative number or zero, just keep prompting for a correct input. In this situation, a do loop makes sense, because you need to get a user input before you can test it.

double value;
do
{
   System.out.print("Please enter a positive number: ");
   value = in.nextDouble();
}
while (value <= 0);

The figure shows a flowchart of this loop.

In practice, do loops are not very common. (The library code in Java 6 contains about 10,000 loop statements, but only about 2 percent are do loops.) Consider again the example of prompting for a positive value. In practice, you also need to guard against users who provide an input that isn't a number. Now the loop becomes so complex that you are better off controlling it with a Boolean variable:

boolean valid = false;
while (!valid)
{
   System.out.print("Please enter a positive number: ");
   if (in.hasNextDouble())
   {
      value = in.nextDouble();
      if (value > 0) valid = true;
   }
   else
     in.nextLine(); // Consume input
}

Flowchart of a do Loop

One of the most common loop types has the form

i = start;
while (i <= end)
{
   ...
   i++;
}

Because this loop is so common, there is a special form for it that emphasizes the pattern:

for (i = start; i <= end; i++)
{
   ...
}

You can also declare the loop counter variable inside the for loop header. That convenient shorthand restricts the use of the variable to the body of the loop (as will be discussed further in Special Topic 6.2 on page 234).

for (int i = start; i <= end; i++)
{
   ...
}

A for loop can be used to find out the size of our $10,000 investment if 5 percent interest is compounded for 20 years. Of course, the balance will be larger than $20,000, because at least $500 is added every year. You may be surprised to find out just how much larger the balance is.

In our loop, we let i go from 1 to numberOfYears, the number of years for which we want to compound interest.

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

Figure 3 shows the corresponding flowchart. Figure 4 shows the flow of execution. The complete program is on page 230.

Another common use of the for loop is to traverse all characters of a string:

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

Figure 6.3. Flowchart of a for Loop

Figure 6.4. Execution of a for Loop

Note that the counter variable i starts at 0, and the loop is terminated when i reaches the length of the string. For example, if str has length 5, i takes on the values 0, 1, 2, 3, and 4. These are the valid positions in the string.

Note too that the three slots in the for header can contain any three expressions. You can count down instead of up:

for (int i = 10; i > 0; i–-)

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

for (int i = −10; i <= 10; i = i + 2) ...

It is possible—but a sign of unbelievably bad taste—to put unrelated conditions into the loop header:

for (rate = 5; years−- > 0; System.out.println(balance))
   ... // Bad taste

We won't even begin to decipher what that might mean. You should stick with for loops that initialize, test, and update a single variable.

The for Statement

ch06/invest2/Investment.java

1  /**
2     A clsass to monitor the growth of an investment that
3     accumulates interest at a fixed annual rate.
4  */
5  public class Investment
6  {
7     private double balance;
8     private double rate;
9     private int years;
10
11      /**
12        Constructs an Investment object from a starting balance and
13        interest rate.
14        @param aBalance the starting balance
15        @param aRate the interest rate in percent
16      */
17      public Investment(double aBalance, double aRate)
18      {
19        balance = aBalance;
20        rate = aRate;
21        years = 0;
22      }
23
24      /**
25        Keeps accumulating interest until a target balance has
26        been reached.
27        @param targetBalance the desired balance
28      */
29      public void waitForBalance(double targetBalance)
30      {
31        while (balance < targetBalance)
32        {
33           years++;

34                 double interest = balance * rate / 100;
35                balance = balance + interest;
36           }
37       }
38
39       /**
40          Keeps accumulating interest for a given number of years.
41          @param numberOfYears the number of years to wait
42       */
43       public void waitYears(int numberOfYears)
44       {
45          for (int i = 1; i <= numberOfYears; i++)
46          {
47                 double interest = balance * rate / 100;
48                balance = balance + interest;
49          }
50            years = years + n;
51       }
52
53       /**
54          Gets the current investment balance.
55          @return the current balance
56       */
57       public double getBalance()
58       {
59          return balance;
60       }
61
62       /**
63          Gets the number of years this investment has accumulated
64          interest.
65          @return the number of years since the start of the investment
66       */
67         public int getYears()
68       {
69          return years;
70       }
71    }

ch06/invest2/InvestmentRunner.java

1  /**
 2     This program computes how much an investment grows in
 3     a given number of years.
 4  */
 5  public class InvestmentRunner
 6  {
 7     public static void main(String[] args)
 8     {
 9        final double INITIAL_BALANCE = 10000;
10        final double RATE = 5;
11        final int YEARS = 20;
12        Investment invest = new Investment(INITIAL_BALANCE, RATE);
13        invest.waitYears(YEARS);
14        double balance = invest.getBalance();
15        System.out.printf("The balance after %d years is %.2f
",
16               YEARS, balance);
17     }
18  }

Program Run

The balance after 20 years is 26532.98

4. How many times does the following for loop execute?

for (i = 0; i <= 10; i++)
   System.out.println(i * i);

for (Set counter to start; Test whether counter at end; Update counter by increment)
{  . . .
   // counter, start, end, increment not changed here
}

// Bad style--unrelated heaser expressions
for (System.out.println("Inputs:");
      (x = in.nextDouble()) > 0;
      sum = sum + x)
   count++;

for (int i = 1; i <= years; i++)
{

if (balance >= targetBalance)
      i = years;    //  Bad style
   else
   {
      double interest = balance * rate / 100;
      balance = balance + interest;
   }
}

for (years = 1;
      (balance = balance + balance * rate / 100) < targetBalance;
      years++)
   ;
System.out.println(years);

for (years = 1;
      (balance = balance + balance * rate / 100) < targetBalance;
      years++)
System.out.println(years);

sum = 0;
for (i = 1; i <= 10; i++);
   sum = sum + i;
System.out.println(sum);

for (i = 1; i <= 10; i++)
   ;

sum = sum + i;

for (i = 1; i != n; i++)

for (i = 1; i <= n; i++)

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

// i no longer defined here

for (i = 1; balance < targetBalance && i <= n; i++)
{
   . . .
}

for (int i = 1; i <= 10; i++)
   System.out.println(i * i);

for (int i = 1; i <= 10; i++) // Declares a new variable i
   System.out.println(i * i * i);

for (int i = 0, j = 10; i <= 10; i++, j−-)
{
   . . .
}

int j = 10;
for (int i = 0; i <= 10; i++)
{
   . . .
   j--;
}

for (i = 1; i <= n; i++) . . .

for (i = 0; i < str.length(); i++) . . .

for (i = 0; i <= str.length() - 1; i++) ...

for (i = a; i < b; i++) . . .

for (i = 0; i < str.length(); i++) . . .

for (i = a; i <= b; i++)

for (n = 0; n <= 10; n++)

|=|=|=|=|=|=|=|=|=|=|

(b - a) / c      for the asymmetric loop
 (b - a) / c + 1     for the symmetric loop

In the following sections, we discuss some of the most common algorithms that are implemented as loops. You can use them as starting points for your loop designs.

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

int upperCaseLetters = 0;
for (int i = 0; i < str.length(); i++)
{

char ch = str.charAt(i);
   if (Character.isUpperCase(ch))
   {
      upperCaseLetters++;
   }
}

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

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."); }
}

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

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

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

Processing Input with Sentinel Values

Suppose you want to process a set of values, for example a set of measurements. Your goal is to analyze the data and display properties of the data set, such as the average or the maximum value. You prompt the user for the first value, then the second value, then the third, and so on. When does the input end?

One common method for indicating the end of a data set is a sentinelvalue, a value that is not part of the data. Instead, the sentinel value indicates that the data has come to an end.

Some programmers choose numbers such as 0 or −1 as sentinel values. But that is not a good idea. These values may well be valid inputs. A better idea is to use an input that is not a number, such as the letter Q. Here is a typical program run:

Enter value, Q to quit: 1
Enter value, Q to quit: 2
Enter value, Q to quit: 3
Enter value, Q to quit: 4
Enter value, Q to quit: Q

Average = 2.5
Maximum = 4.0

Of course, we need to read each input as a string, not a number. Once we have tested that the input is not the letter Q, we convert the string into a number.

System.out.print("Enter value, Q to quit: ");
String input = in.next();
if (input.equalsIgnoreCase("Q"))
   We are done
else
{
   double x = Double.parseDouble(input);
   . . .
}

Now we have another problem. The test for loop termination occurs in the middleof the loop, not at the top or the bottom. You must first try to read input before you can test whether you have reached the end of input. In Java, there isn't a ready-made control structure for the pattern "do work, then test, then do more work". Therefore, we use a combination of a while loop and a boolean variable.

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

Note

Sometimes, the termination condition of a loop can only be evaluated in the middle of a loop. You can introduce a Boolean variable to control such a loop.

This pattern is sometimes called "loop and a half". Some programmers find it clumsy to introduce a control variable for such a loop. Special Topic 6.3 on page 245 shows several alternatives.

Here is a complete program that reads input and analyzes the data. We separate the input handling from the computation of the data set properties by using two classes, DataAnalyzer and DataSet. The DataAnalyzer class handles the input and adds values to a DataSet object with the add method. It then calls the getAverage method and the getMaximum method to obtain the average and maximum of all added data.

ch06/dataset/DataAnalyzer.java

1 import java.util.Scanner;
2
3 /**
4    This program computes the average and maximum of a set
5    of input values.
6 */
7 public class DataAnalyzer
8 {
9    public static void main(String[] args)
10   {
11      Scanner in = new Scanner(System.in);
12      DataSet data = new DataSet();
13

14      boolean done = false;
15      while (!done)
16      {
17         System.out.print("Enter value, Q to quit: ");
18         String input = in.next();
19         if (input.equalsIgnoreCase("Q"))
20             done = true;
21         else
22         {
23            double x = Double.parseDouble(input);
24             data.add(x);
25         }
26          }
27
28           System.out.println("Average = " + data.getAverage());
29           System.out.println("Maximum = " + data.getMaximum());
30       }
31    }

ch06/dataset/DataSet.java

1  /**
2     Computes information about a set of data values.
3  */
4  public class DataSet
5  {
6     private double sum;
7     private double maximum;
8     private int count;
9
10     /**
11        Constructs an empty data set.
12     */
13     public DataSet()
14     {
15         sum = 0;
16        count = 0;
17        maximum = 0;
18     }
19
20     /**
21        Adds a data value to the data set.
22        @param x a data value
23     */
24     public void add(double x)
25     {
26        sum = sum + x;
27        if (count == 0 || maximum < x) maximum = x;
28         count++;
29     }
30
31     /**
32        Gets the average of the added data.
33        @return the average or 0 if no data has been added
34     */
35     public double getAverage()
36      {

37         if (count == 0) return 0;
38         else return sum / count;
39       }
40
41      /**
42         Gets the largest of the added data.
43         @return the maximum or 0 if no data has been added
44      */
45      public double getMaximum()
46      {
47         return maximum;
48      }
49   }

Program Run

Enter value, Q to quit: 10
Enter value, Q to quit: 0
Enter value, Q to quit: −1
Enter value, Q to quit: Q
Average = 3.0
Maximum = 10.0

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

7. Why does the DataAnalyzer class call in.next and not in.nextDouble?

8. Would the DataSet class still compute the correct maximum if you simplified the update of the maximum variable in the add method to the following statement?

if (maximum < x) maximum = x;

How To 6.1: Writing a Loop

This How To walks you through the process of implementing a loop statement. We will illustrate the steps with the following example problem:

Read twelve temperature values (one for each month), and display the number of the month with the highest temperature. For example, according to http://worldclimate.com, the average maximum temperatures for Death Valley are (in order by month):

• 18.2 22.6 26.4 31.1 36.6 42.2

• 45.7 44.5 40.2 33.1 24.2 17.6

In this case, the month with the highest temperature (45.7 degrees Celsius) is July, and the program should display 7.

• Step 1 Decide what work must be done inside the loop.

  Every loop needs to do some kind of repetitive work, such as

  • Reading another item.

  • Updating a value (such as a bank balance or total).

  • Incrementing a counter.

  If you can't figure out what needs to go inside the loop, start by writing down the steps that you would take if you solved the problem by hand. For example, with the temperature reading problem, you might write

  Read first value.
  Read second value.
  If second value is higher than the first, set highest temperature to that value, highest month to 2.
  Read next value.
  If value is higher than the first and second, set highest temperature to that value, highest month to 3.
  Read next value.
  If value is higher than the highest temperature seen so far, set highest temperature to that value,
      highest month to 4.
  ...

  Now look at these steps and reduce them to a set of uniform actions that can be placed into the loop body. The first action is easy:

  Read next value.

  The next action is trickier. In our description, we used tests "higher than the first", "higher than the first and second", "higher than the highest temperature seen so far". We need to settle on one test that works for all iterations. The last formulation is the most general.

  Similarly, we must find a general way of setting the highest month. We need a variable that stores the current month, running from 1 to 12. Then we can formulate the second loop action:

  If value is higher than the highest temperature, set highest temperature to that value,
      highest month to current month.

  Altogether our loop is

  Loop
      Read next value.
      If value is higher than the highest temperature, set highest temperature to that value,
      highest month to current month.
      Increment current month.

• Step 2 Specify the loop condition.

  What goal do you want to reach in your loop? Typical examples are

  • Has a counter reached its final value?

  • Have you read the last input value?

  • Has a value reached a given threshold?

  In our example, we simply want the current month to reach 12.

• Step 3 Determine the loop type.

  We distinguish between two major loop types. A definite or count-controlled loop is executed a definite number of times. In an indefinite or event-controlled loop, the number of iterations is not known in advance—the loop is executed until some event happens. A typical example of the latter is a loop that reads data until a sentinel is encountered.

  Definite loops can be implemented as for statements. When you have an indefinite loop, consider the loop condition. Does it involve values that are only set inside the loop body? In that case, you should choose a do loop to ensure that the loop is executed at least once before the loop condition is be evaluated. Otherwise, use a while loop.

  Sometimes, the condition for terminating a loop changes in the middle of the loop body. In that case, you can use a Boolean variable that specifies when you are ready to leave the loop. Follow this pattern:

  boolean done = false;
  while (!done)
  {
     Do some work
     If all work has been completed
     {
        done = true;
     }
     else
     {
        Do more work
     }
  }

  Such a variable is called a flag.

  In summary,

  • If you know in advance how many times a loop is repeated, use a for loop.

  • If the loop must be executed at least once, use a do loop.

  • Otherwise, use a while loop.

  In our example, we read 12 temperature values. Therefore, we choose a for loop.

• Step 4 Set up variables for entering the loop for the first time.

  List all variables that are used and updated in the loop, and determine how to initialize them. Commonly, counters are initialized with 0 or 1, totals with 0.

  In our example, the variables are

  current month
  highest value
  highest month

  We need to be careful how we set up the highest temperature value. We can't simply set it to 0. After all, our program needs to work with temperature values from Antarctica, all of which may be negative.

  A good option is to set the highest temperature value to the first input value. Of course, then we need to remember to only read in another 11 values, with the current month starting at 2.

  We also need to initialize the highest month with 1. After all, in an Australian city, we may never find a month that is warmer than January.

• Step 5 Process the result after the loop has finished.

  In many cases, the desired result is simply a variable that was updated in the loop body. For example, in our temperature program, the result is the highest month. Sometimes, the loop computes values that contribute to the final result. For example, suppose you are asked to average the temperatures. Then the loop should compute the sum, not the average. After the loop has completed, you are ready compute the average: divide the sum by the number of inputs.

  Here is our complete loop.

  Read first value; store as highest value.
  highest month = 1

  for (current month = 2; current month <= 12; current month++)
      Read next value.
      If value is higher than the highest value, set highest value to that value,
      highest month to current month.

• Step 6 Trace the loop with typical examples.

  Hand trace your loop code, as described in Productivity Hint 6.1 on page 223. Choose example values that are not too complex—executing the loop 3–5 times is enough to check for the most common errors. Pay special attention when entering the loop for the first and last time.

  Sometimes, you want to make a slight modification to make tracing feasible. For example, when hand tracing the investment doubling problem, use an interest rate of 20 percent rather than 5 percent. When hand tracing the temperature loop, use 4 data values, not 12.

  Let's say the data are 22.6 36.6 44.5 24.2. Here is the walkthrough:

  

  The trace demonstrates that highest month and highest value are properly set.

• Step 7 Implement the loop in Java.

  Here's the loop for our example. Exercise P6.1 asks you to complete the program.

  double highestValue = in.nextDouble();
  int highestMonth = 1;
  for (int currentMonth = 2; currentMonth <= 12; currentMonth++)
  {
     double nextValue = in.nextDouble();
     if (nextValue > highestValue)
     {
        highestValue = nextValue;
        highestMonth = currentMonth;
     }
  }

Worked Example 6.1: Credit Card Processing

This Worked Example uses a loop to remove spaces from a credit card number.

Special Topic 6.3: The "Loop and a Half" Problem

Reading input data sometimes requires a loop such as the following, which is somewhat unsightly:

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

The true test for loop termination is in the middle of the loop, not at the top. This is called a "loop and a half", because one must go halfway into the loop before knowing whether one needs to terminate.

Some programmers dislike the introduction of an additional Boolean variable for loop control. Two Java language features can be used to alleviate the "loop and a half" problem. I don't think either is a superior solution, but both approaches are fairly common, so it is worth knowing about them when reading other people's code.

You can combine an assignment and a test in the loop condition:

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

The expression

(input = in.next()).equalsIgnoreCase("Q")

means, "First call in.next(), then assign the result to input, then test whether it equals "Q"". This is an expression with a side effect. The primary purpose of the expression is to serve as a test for the while loop, but it also does some work—namely, reading the input and storing it in the variable input. In general, it is a bad idea to use side effects, because they make a program hard to read and maintain. In this case, however, that practice is somewhat seductive, because it eliminates the control variable done, which also makes the code hard to read and maintain.

The other solution is to exit the loop from the middle, either by a return statement or by a break statement (see Special Topic 6.4 on page 246).

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

Special Topic 6.4: The break and continue Statements

You already encountered the break statement in Special Topic 5.2, where it was used to exit a switch statement. In addition to breaking out of a switch statement, a break statement can also be used to exit a while, for, or do loop. For example, the break statement in the following loop terminates the loop when the end of input is reached.

while (true)
{
   String input = in.next();
   if (input.equalsIgnoreCase("Q"))
      break;
   double x = Double.parseDouble(input);
   data.add(x);
}

In general, a break is a very poor way of exiting a loop. In 1990, a misused break caused an AT&T 4ESS telephone switch to fail, and the failure propagated through the entire U.S. network, rendering it nearly unusable for about nine hours. A programmer had used a break to terminate an if statement. Unfortunately, break cannot be used with if, so the program execution broke out of the enclosing switch statement, skipping some variable initializations and running into chaos (Expert C Programming, Peter van der Linden, Prentice-Hall 1994, p.38). Using break statements also makes it difficult to use correctness proof techniques (see Special Topic 6.5 on page 255).

However, when faced with the bother of introducing a separate loop control variable, some programmers find that break statements are beneficial in the "loop and a half" case. This issue is often the topic of heated (and quite unproductive) debate. In this book, we won't use the break statement, and we leave it to you to decide whether you like to use it in your own programs.

In Java, there is a second form of the break statement that is used to break out of a nested statement. The statement break label; immediately jumps to the end of the statement that is tagged with a label. Any statement (including if and block statements) can be tagged with a label—the syntax is

labele: statement

The labeled break statement was invented to break out of a set of nested loops.

outerloop:
while (outer loop condition)
{...
   while (inner loop condition)
   {...
      if (something really bad happened)
         break outerloop;
   }
}
Jumps here if something really bad happened

Naturally, this situation is quite rare. We recommend that you try to introduce additional methods instead of using complicated nested loops.

Finally, there is the continue statement, which jumps to the end of the current iteration of the loop. Here is a possible use for this statement:

while (!done)
{
   String input = in.next();
   if (input.equalsIgnoreCase("Q"))
   {

done = true;
      continue; // Jump to the end of the loop body
   }
   double x = Double.parseDouble(input);
   data.add(x);
   // continue statement jumps here
}

By using the continue statement, you don't need to place the remainder of the loop code inside an else clause. This is a minor benefit. Few programmers use this statement.

Sometimes, the body of a loop is again a loop. We say that the inner loop is nestedinside an outer loop. This happens often when you process two-dimensional structures, such as tables.

Let's look at an example that looks a bit more interesting than a table of numbers. We want to generate the following triangular shape:

The basic idea is simple. We generate a sequence of rows:

for (int i = 1; i <= width; i++)
{
   // Make triangle row
   ...
}

How do you make a triangle row? Use another loop to concatenate the squares [] for that row. Then add a newline character at the end of the row. The ith row has i symbols, so the loop counter goes from 1 to i.

for (int j = 1; j <= i; j++)
   r = r + "[]";
r = r + "
";

Putting both loops together yields two nested loops:

String r = "";
for (int i = 1; i <= width; i++)
{
   // Make triangle row
   for (int j = 1; j <= i; j++)
      r = r + "[]";
   r = r + "
";
}
return r;

Here is the complete program:

ch06/triangle1/Triangle.java

1 /**
2    This class describes triangle objects that can be displayed
3    as shapes like this:
4    []
5    [][]
6    [][][].
7 */
8 public class Triangle
9 {
10    private int width;
11
12    /**
13       Constructs a triangle.
14       @param aWidth the number of [] in the last row of the triangle
15    */
16    public Triangle(int aWidth)
17    {
18       width = aWidth;
19    }
20
21    /**
22       Computes a string representing the triangle.
23       @return a string consisting of [] and newline characters
24    */
25    public String toString()
26    {
27       String r = "";
28       for (int i = 1; i <= width; i++)
29       {
30          // Make triangle row
31          for (int j = 1; j <= i; j++)
32             r = r + "[]";
33          r = r + "
";
34        }
35       return r;
36    }
37 }

ch06/triangle1/TriangleRunner.java

1 /**
2    This program prints two triangles.
3 */
4 public class TriangleRunner
5 {
6    public static void main(String[] args)
7    {
8       Triangle small = new Triangle(3);
9       System.out.println(small.toString());
10
11       Triangle large = new Triangle(15);
12       System.out.println(large.toString());
13    }
14 }

Program Run

for (i = 1; i <= 3; i++)
{
   for (j = 1; j <= 4; j++)  { Print"*" }
   System.out.println();
}

****
****
****

for (i = 1; i <= 4; i++)
{
   for (j = 1; j <= 3; j++) { Print"*" }
   System.out.println();
}

***
***
***
***

for (i = 1; i <= 4; i++)
{
   for (j = 1; j <= i; j++) { Print"*" }
   System.out.println();
}

*
**
***
****

for (i = 1; i <= 3; i++)
{
   for (j = 1; j <= 5; j++)
   {
      if (j % 2 == 0) { Print"*" }
      else { Print"-" }
   }
   System.out.println();
}

-*-*-
-*-*-
-*-*-

for (i = 1; i <= 3; i++)
{
   for (j = 1; j <= 5; j++)
   {
      if ((i + j) % 2 == 0) { Print"*" }
      else { Print" " }
   }
   System.out.println();
}

* * *
 * *
* * *

10. What is the value of n after the following nested loops?

int n = 0;
for (int i = 1; i <= 5; i++)
   for (int j = 0; j < i; j++)
      n = n + j;

Worked Example 6.2: Manipulating the Pixels in an Image

This Worked Example shows how to use nested loops for manipulating the pixels in an image. The outer loop traverses the rows of the image, and the inner loop accesses each pixel of a row.

A simulation program uses the computer to simulate an activity in the real world (or an imaginary one). Simulations are commonly used for predicting climate change, analyzing traffic, picking stocks, and many other applications in science and business. In many simulations, one or more loops are used to modify the state of a system and observe the changes.

Here is a typical problem that can be decided by running a simulation: the Buffon needle experiment, devised by Comte Georges-Louis Leclerc de Buffon (1707–1788), a French naturalist. On each try, a one-inch long needle is dropped onto paper that is ruled with lines 2 inches apart. If the needle drops onto a line, count it as a hit. (See Figure 5.) Buffon conjectured that the quotient tries/hitsapproximates π.

In a simulation, you repeatedly generate random numbers and use them to simulate an activity.

Figure 6.5. The Buffon Needle Experiment

Now, how can you run this experiment in the computer? You don't actually want to build a robot that drops needles on paper. The Random class of the Java library implements a random number generator, which produces numbers that appear to be completely random. To generate random numbers, you construct an object of the Random class, and then apply one of the following methods:

For example, you can simulate the cast of a die as follows:

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.

To give you a feeling for the random numbers, run the following program a few times.

ch06/random1/Die.java

1 import java.util.Random;
2
3 /**
4    This class models a die that, when cast, lands on a random
5    face.
6 */
7 public class Die
8 {
9   private Random generator;
10   private int sides;
11
12   /**
13      Constructs a die with a given number of sides.
14      @param s the number of sides, e.g., 6 for a normal die
15   */
16   public Die(int s)
17   {

18         sides = s;
19         generator = new Random();
20      }
21
22      /**
23         Simulates a throw of the die.
24         @return the face of the die
25      */
26      public int cast()
27      {
28         return 1 + generator.nextInt(sides);
29      }
30   }

ch06/random1/DieSimulator.java

1 /**
2    This program simulates casting a die ten times.
3 */
4 public class DieSimulator
5 {
6    public static void main(String[] args)
7    {
8       Die d = new Die(6);
9       final int TRIES = 10;
10       for (int i = 1; i <= TRIES; i++)
11       {
12          int n = d.cast();
13          System.out.print(n + " ");
14       }
15       System.out.println();
16     }
17 }

Typical Program Run

6 5 6 3 2 6 3 4 4 1

Typical Program Run (Second Run)

3 2 2 1 6 5 3 4 1 2

As you can see, this program produces a different stream of simulated die casts every time it is run.

Actually, the numbers are not completely random. They are drawn from very long sequences of numbers that don't repeat for a long time. These sequences are computed from fairly simple formulas; they just behave like random numbers. For that reason, they are often called pseudorandom numbers. Generating good sequences of numbers that behave like truly random sequences is an important and well-studied problem in computer science. We won't investigate this issue further, though; we'll just use the random numbers produced by the Random class.

To run the Buffon needle experiment, we have to work a little harder. When you throw a die, it has to come up with one of six faces. When throwing a needle, however, there are many possible outcomes. You must generate two random numbers: one to describe the starting position and one to describe the angle of the needle with the x-axis. Then you need to test whether the needle touches a grid line. Stop after 10,000 tries.

Figure 6.6. When Does the Needle Fall on a Line?

Let us agree to generate the lower point of the needle. Its x-coordinate is irrelevant, and you may assume its y-coordinate y_low to be any random number between 0 and 2. However, because it can be a random floating-point number, we use the nextDouble method of the Random class. It returns a random floating-point number between 0 and 1. Multiply by 2 to get a random number between 0 and 2.

The angle α between the needle and the x-axis can be any value between 0 degrees and 180 degrees. The upper end of the needle has y-coordinate

The needle is a hit if y_high is at least 2. See Figure 6.

Here is the program to carry out the simulation of the needle experiment.

ch06/random2/Needle.java

1 import java.util.Random;
2
3 /**
4    This class simulates a needle in the Buffon needle experiment.
5 */
6 public class Needle
7 {
8    private Random generator;
9    private int hits;
10    private int tries;
11
12    /**
13       Constructs a needle.
14    */
15    public Needle()
16    {
17       hits = 0;
18       tries = 0;
19       generator = new Random();
20    }
21

22     /**
23       Drops the needle on the grid of lines and
24       remembers whether the needle hit a line.
25     */
26     public void drop()
27     {
28       double ylow = 2 * generator.nextDouble();
29       double angle = 180 * generator.nextDouble();
30
31       // Computes high point of needle
32
33       double yhigh = ylow + Math.sin(Math.toRadians(angle));
34       if (yhigh >= 2) hits++;
35       tries++;
36       }
37
38     /**
39       Gets the number of times the needle hit a line.
40       @return the hit count
41     */
42     public int getHits()
43     {
44       return hits;
45     }
46
47     /**
48       Gets the total number of times the needle was dropped.
49       @return the try count
50     */
51     public int getTries()
52     {
53       return tries;
54    }
55 }

ch06/random2/NeedleSimulator.java

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

Program Run

Tries = 10000, Tries / Hits =  3.08928
Tries = 1000000, Tries / Hits =  3.14204

The point of this program is not to compute π—there are far more efficient ways to do that. Rather, the point is to show how a physical experiment can be simulated on the computer. Buffon had to physically drop the needle thousands of times and record the results, which must have been a rather dull activity. The computer can execute the experiment quickly and accurately.

Simulations are very common computer applications. Many simulations use essentially the same pattern as the code of this example: In a loop, a large number of sample values are generated, and the values of certain observations are recorded for each sample. When the simulation is completed, the averages, or other statistics of interest from the observed values are printed out.

A typical example of a simulation is the modeling of customer queues at a bank or a supermarket. Rather than observing real customers, one simulates their arrival and their transactions at the teller window or checkout stand in the computer. One can try different staffing or building layout patterns in the computer simply by making changes in the program. In the real world, making many such changes and measuring their effects would be impossible, or at least, very expensive.

12. Why is the NeedleSimulator program not an efficient method for computing π?

Special Topic 6.5: Loop Invariants

Consider the task of computing aⁿ, where a is a floating-point number and n is a positive integer. Of course, you can multiply a · a · . . . · a, n times, but if n is large, you'll end up doing a lot of multiplication. The following loop computes aⁿ in far fewer steps:

double a = . . .;
int n = . . .;
double r = 1;
double b = a;
int i = n;
while (i > 0)
{
   if (i % 2 == 0) // n is even
   {
       b = b * b;
       i = i / 2;
   }
   else
   {
      r = r * b;
      i--;
   }
}
// Now r equals a to the nth power

Consider the case n = 100. The method performs the steps shown in the table below.

Computing a100
b	i	r
a	100	1
a2	50
a4	25
	24	a4
a8	12
a16	6
a32	3
	2	a36
a64	1
	0	a100

Amazingly enough, the algorithm yields exactly a¹⁰⁰. Do you understand why? Are you convinced it will work for all values of n? Here is a clever argument to show that the method always computes the correct result. It demonstrates that whenever the program reaches the top of the while loop, it is true that

Certainly, it is true the first time around, because b = a and i = n. Suppose that (I) holds at the beginning of the loop. Label the values of r, b, and i as "old" when entering the loop, and as "new" when exiting the loop. Assume that upon entry

In the loop you must distinguish two cases: iold even and iold odd. If iold is even, the loop performs the following transformations:

Therefore,

On the other hand, if i_old is odd, then

Therefore,

In either case, the new values for r, b, and i fulfill the loop invariant (I). So what? When the loop finally exits, (I) holds again:

Furthermore, we know that i = 0, because the loop is terminating. But because i = 0, r · bⁱ = r · b0_{= r}. Hence r = aⁿ, and the method really does compute the nth power of a.

This technique is quite useful, because it can explain an algorithm that is not at all obvious. The condition (I) is called a loop invariant because it is true when the loop is entered, at the top of each pass, and when the loop is exited. If a loop invariant is chosen skillfully, you may be able to deduce correctness of a computation. See Programming Pearls (Jon Bentley, Addison-Wesley 1986, Chapter 4) for another nice example.

As you have undoubtedly realized by now, computer programs rarely run perfectly the first time. At times, it can be quite frustrating to find the bugs. Of course, you can insert print commands, run the program, and try to analyze the printout. If the printout does not clearly point to the problem, you may need to add and remove print commands and run the program again. That can be a time-consuming process.

Modern development environments contain special programs, called debuggers, that help you locate bugs by letting you follow the execution of a program. You can stop and restart your program and see the contents of variables whenever your program is temporarily stopped. At each stop, you have the choice of what variables to inspect and how many program steps to run until the next stop.

Some people feel that debuggers are just a tool to make programmers lazy. Admittedly some people write sloppy programs and then fix them up with a debugger, but the majority of programmers make an honest effort to write the best program they can before trying to run it through a debugger. These programmers realize that a debugger, while more convenient than print commands, is not cost-free. It does take time to set up and carry out an effective debugging session.

In actual practice, you cannot avoid using a debugger. The larger your programs get, the harder it is to debug them simply by inserting print commands. You will find that the time investment to learn about a debugger is amply repaid in your programming career.

Like compilers, debuggers vary widely from one system to another. On some systems they are quite primitive and require you to memorize a small set of arcane commands; on others they have an intuitive window interface. The screen shots in this chapter show the debugger in the Eclipse development environment, downloadable for free from the Eclipse Foundation web site (eclipse.org). Other integrated environments, such as BlueJ, also include debuggers. A free standalone debugger called JSwat is available from www.bluemarsh.com/java/jswat.

You will have to find out how to prepare a program for debugging and how to start a debugger on your system. If you use an integrated development environment, which contains an editor, compiler, and debugger, this step is usually very easy. You just build the program in the usual way and pick a menu command to start debugging. On some systems, you must manually build a debug version of your program and invoke the debugger.

Once you have started the debugger, you can go a long way with just three debugging commands: "set breakpoint", "single step", and "inspect variable". The names and keystrokes or mouse clicks for these commands differ widely between debuggers, but all debuggers support these basic commands. You can find out how, either from the documentation or a lab manual, or by asking someone who has used the debugger before.

When you start the debugger, it runs at full speed until it reaches a breakpoint. Then execution stops, and the breakpoint that causes the stop is displayed (see Figure 7). You can now inspect variables and 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, so you should periodically clear the breakpoints that you no longer need.

Figure 6.7. Stopping at a Breakpoint

Figure 6.8. Inspecting Variables

Once the program has stopped, you can look at the current values of variables. Again, the method for selecting the variables differs among debuggers. Some debuggers always show you a window with the current local variables. On other debuggers you issue a command such as "inspect variable" and type in or click on the variable. The debugger then displays the contents of the variable. If all variables contain what you expected, you can run the program until the next point where you want to stop.

When inspecting objects, you often need to give a command to "open up" the object, for example by clicking on a tree node. Once the object is opened up, you see its instance variables (see Figure 8).

Running to a breakpoint gets you there speedily, but you don't know how the program got there. You can also step through the program a line at a time. Then you know how the program flows, but it can take a long time to step through it. The single-step command executes the current line and stops at the next program line. Most debuggers have two single-step commands, one called step into, which steps inside method calls, and one called step over, which skips over method calls.

For example, suppose the current line is

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

You should step into a method to check whether it carries out its job correctly. You should step over a method if you know it works correctly.

Finally, when the program has finished running, the debug session is also finished. To run the program again, you may be able to reset the debugger, or you may need to exit the debugging program and start over. Details depend on the particular debugger.

A debugger can be an effective tool for finding and removing bugs in your program. However, it is no substitute for good design and careful programming. If the debugger does not find any errors, it does not mean that your program is bug-free. Testing and debugging can only show the presence of bugs, not their absence.

14. In the debugger, you are reaching the beginning of a 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?

Worked Example 6.3: A Sample Debugging Session

This Worked Example shows how to find bugs in an algorithm for counting the syllables of a word.

Random Fact 6.1: The First Bug

According to legend, the first bug was one found in 1947 in the Mark II, a huge electromechanical computer at Harvard University. It really was caused by a bug—a moth was trapped in a relay switch. Actually, from the note that the operator left in the log book next to the moth (see the figure), it appears as if the term "bug" had already been in active use at the time.

The First Bug

The pioneering computer scientist Maurice Wilkes wrote: "Somehow, at the Moore School and afterwards, one had always assumed there would be no particular difficulty in getting programs right. I can remember the exact instant in time at which it dawned on me that a great part of my future life would be spent finding mistakes in my own programs."

java.util.Random
   nextDouble
   nextInt

for (int i = 0; i < 10; i++)
{

for (int j = 0; j < 10; j++)
      System.out.print(i * j % 10);
   System.out.println();
}

int s = 0;
for (int i = 1; i <= 10; i++) s = s + i;

int n = 1;
double x = 0;
double s;
do
{
   s = 1.0 / (n * n);
   x = x + s;
   n++;
}
while (s > 0.01);

Loop
   Read name of bridge.
   If not OK, exit loop.
   Read length of bridge in feet.
   If not OK, exit loop.
   Convert length to meters.
   Print bridge data.

Programming Exercises

P6.1 Complete the program in How To 6.1 on page 241. Your program should read twelve temperature values and print the month with the highest temperature.

P6.2 Credit Card Number Check. The last digit of a credit card number is the check digit, which protects against transcription errors such as an error in a single digit or switching two digits. The following method is used to verify actual credit card numbers but, for simplicity, we will describe it for numbers with 8 digits instead of 16:

• Starting from the rightmost digit, form the sum of every other digit. For example, if the credit card number is 4358 9795, then you form the sum 5 + 7 + 8 + 3 = 23.

• Double each of the digits that were not included in the preceding step. Add all digits of the resulting numbers. For example, with the number given above, doubling the digits, starting with the next-to-last one, yields 18 18 10 8. Adding all digits in these values yields 1 + 8 + 1 + 8 + 1 + 0 + 8 = 27.

• Add the sums of the two preceding steps. If the last digit of the result is 0, the number is valid. In our case, 23 + 27 = 50, so the number is valid.

Write a program that implements this algorithm. The user should supply an 8-digit number, and you should print out whether the number is valid or not. If it is not valid, you should print out the value of the check digit that would make the number valid.

P6.3 Currency conversion. Write a program CurrencyConverter that asks the user to enter today's price of one dollar in euro. Then the program reads U.S. dollar values and converts each to euro values. Stop when the user enters Q.

P6.4 Projectile flight. Suppose a cannonball is propelled vertically into the air with a starting velocity v₀. Any calculus book will tell us that the position of the ball after t seconds is, where g = 9.81 m/sec² is the gravitational force of the earth. No calculus book ever mentions why someone would want to carry out such an obviously dangerous experiment, so we will do it in the safety of the computer.

In fact, we will confirm the theorem from calculus by a simulation. In our simulation, we will consider how the ball moves in very short time intervals Δt. In a short time interval the velocity v is nearly constant, and we can compute the distance the ball moves as Δs = v · Δt. In our program, we will simply set

double deltaT = 0.01;

and update the position by

s = s + v * deltaT;

The velocity changes constantly—in fact, it is reduced by the gravitational force of the earth. In a short time interval, v decreases by, and we must keep the velocity updated as

v = v - g * deltaT;

In the next iteration the new velocity is used to update the distance.

Now run the simulation until the cannonball falls back to the earth. Get the initial velocity as an input (100 m/sec is a good value). Update the position and velocity 100 times per second, but only print out the position every full second. Also print out the values from the exact formula s(t) = −0.5 · g · t² + v₀ · t for comparison. Use a class Cannonball.

What is the benefit of this kind of simulation when an exact formula is available? Well, the formula from the calculus book is not exact. Actually, the gravitational force diminishes the farther the cannonball is away from the surface of the earth. This complicates the algebra sufficiently that it is not possible to give an exact formula for the actual motion, but the computer simulation can simply be extended to apply a variable gravitational force. For cannonballs, the calculus-book formula is actually good enough, but computers are necessary to compute accurate trajectories for higher-flying objects such as ballistic missiles.

P6.5 Write a program that prints the powers of ten

1.0
10.0
100.0
1000.0
10000.0
100000.0
1000000.0
1.0E7
1.0E8
1.0E9
1.0E10
1.0E11

Implement a class

public class PowerGenerator
{

/**
      Constructs a power generator.
      @param aFactor the number that will be multiplied by itself
   */
   public PowerGenerator(double aFactor) { ... }

   /**
      Computes the next power.
   */
   public double nextPower() { ... }
   ...
}

Then supply a test class PowerGeneratorRunner that calls System.out.println(myGenerator.nextPower()) twelve times.

P6.6 The Fibonacci sequence is defined by the following rule. The first two values in the sequence are 1 and 1. Every subsequent value is the sum of the two values preceding it. For example, the third value is 1 + 1 = 2, the fourth value is 1 + 2 = 3, and the fifth is 2 + 3 = 5. If f_n denotes the nth value in the Fibonacci sequence, then

Write a program that prompts the user for n and prints the first n values in the Fibonacci sequence. Use a class FibonacciGenerator with a method nextNumber.

Hint: There is no need to store all values for f_n. You only need the last two values to compute the next one in the series:

fold1 = 1;
fold2 = 1;
fnew = fold1 + fold2;

After that, discard fold2, which is no longer needed, and set fold2 to fold1 and fold1 to fnew.

Your generator class will be tested with this runner program:

public class FibonacciRunner
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);

      System.out.println("Enter n:");
      int n = in.nextInt();

      FibonacciGenerator fg = new FibonacciGenerator();

      for (int i = 1; i <= n; i++)
         System.out.println(fg.nextNumber());
   }
}

P6.7 Mean and standard deviation. Write a program that reads a set of floating-point data values from the input. When the user indicates the end of input, print out the count of the values, the average, and the standard deviation. The average of a data set x₁, . . ., x_n is

where Σ x_i = x₁ ... + x_n is the sum of the input values. The standard deviation is

However, that formula is not suitable for our task. By the time you have computed the mean, the individual x_i are long gone. Until you know how to save these values, use the numerically less stable formula

You can compute this quantity by keeping track of the count, the sum, and the sum of squares in the DataSet class as you process the input values.

P6.8 Factoring of integers. Write a program that asks the user for an integer and then prints out all its factors in increasing order. For example, when the user enters 150, the program should print

2
3
5
5

Use a class FactorGenerator with a constructor FactorGenerator(int numberToFactor) and methods nextFactor and hasMoreFactors. Supply a class FactorPrinter whose main method reads a user input, constructs a FactorGenerator object, and prints the factors.

P6.9 Prime numbers. Write a program that prompts the user for an integer and then prints out all prime numbers up to that integer. For example, when the user enters 20, the program should print

2
3
5
7
11
13
17
19

Recall that a number is a prime number if it is not divisible by any number except 1 and itself.

Supply a class PrimeGenerator with a method nextPrime.

P6.10 The Heron method is a method for computing square roots that was known to the ancient Greeks. If x is a guess for the value √a, then the average of x and a/x is a better guess.

Implement a class RootApproximator that starts with an initial guess of 1 and whose nextGuess method produces a sequence of increasingly better guesses. Supply a method hasMoreGuesses that returns false if two successive guesses are sufficiently close to each other (that is, they differ by no more than a small value ɛ). Then test your class like this:

RootApproximator approx = new RootApproximator(a, EPSILON);
while (approx.hasMoreGuesses())
   System.out.println(approx.nextGuess());

P6.11 The best known iterative method for computing the roots of a function f (that is, the x-values for which f(x) is 0) is Newton-Raphson approximation. To find the zero of a function whose derivative is also known, compute

For this exercise, write a program to compute nth roots of floating-point numbers. Prompt the user for a and n, then obtain n√a by computing a zero of the function f(x) = xⁿ − a. Follow the approach of Exercise P6.10.

P6.12 The value of e^x can be computed as the power series

where n! = 1 · 2 · 3 · . . . · n.

Write a program that computes e^x using this formula. Of course, you can't compute an infinite sum. Just keep adding values until an individual summand (term) is less than a certain threshold. At each step, you need to compute the new term and add it to the total. Update these terms as follows:

term = term * x / n;

Follow the approach of the preceding two exercises, by implementing a class ExpApproximator. Its first guess should be 1.

P6.13 Write a program RandomDataAnalyzer that generates 100 random numbers between 0 and 1000 and adds them to a DataSet. Print out the average and the maximum.

P6.14 Program the following simulation: Darts are thrown at random points onto the square with corners (1,1) and (−1, −1). If the dart lands inside the unit circle (that is, the circle with center (0,0) and radius 1), it is a hit. Otherwise it is a miss. Run this simulation and use it to determine an approximate value for π. Extra credit if you explain why this is a better method for estimating π than the Buffon needle program.

P6.15 Random walk. Simulate the wandering of an intoxicated person in a square street grid. Draw a grid of 20 streets horizontally and 20 streets vertically. Represent the simulated drunkard by a dot, placed in the middle of the grid to start. For 100 times, have the simulated drunkard randomly pick a direction (east, west, north, south), move one block in the chosen direction, and draw the dot. (One might expect that on average the person might not get anywhere because the moves to different directions cancel one another out in the long run, but in fact it can be shown with probability 1 that the person eventually moves outside any finite region. Use classes for the grid and the drunkard.

P6.16 This exercise is a continuation of Exercise P6.4. Most cannonballs are not shot upright but at an angle. If the starting velocity has magnitude v and the starting angle is α, then the velocity is a vector with components v_x = v · cos(α), v_y = v · sin(α). In the x-direction the velocity does not change. In the y-direction the gravitational force takes its toll. Repeat the simulation from the previous exercise, but update the x and y components of the location and the velocity separately. In every iteration, plot the location of the cannonball on the graphics display as a tiny circle. Repeat until the cannonball has reached the earth again.

This kind of problem is of historical interest. The first computers were designed to carry out just such ballistic calculations, taking into account the diminishing gravity for high-flying projectiles and wind speeds.

P6.17 Write a graphical application that displays a checkerboard with 64 squares, alternating white and black.

P6.18 Write a graphical application that prompts a user to enter a number n and that draws n circles with random diameter and random location. The circles should be completely contained inside the window.

P6.19 Write a graphical application that draws a spiral, such as the following:

P6.20 It is easy and fun to draw graphs of curves with the Java graphics library. Simply draw 100 line segments joining the points (x, f(x)) and (x + d, f(x + d)), where x ranges from x_min to x_max and d = (x_max -x_max)/100.

Draw the curve f(x) = 0.00005x³ − 0.03x² + 4x + 200, where x ranges from 0 to 400 in this fashion.

P6.21 Draw a picture of the "four-leaved rose" whose equation in polar coordinates is r = cos(2θ). Let θ go from 0 to 2π in 100 steps. Each time, compute r and then compute the (x,y) coordinates from the polar coordinates by using the formula

x = r · cos(θ), y · sin(θ)

Index = 206.835
      - 84.6 × Number of syllables/Number of words)
      - 1.015 × (Number of words/Number of sentences)