Java (Case Studies)

Case Studies

Control statements are fundamental in programming. The ability to write control statements is essential in learning Java programming. If you can write programs using loops, you know how to program! For this reason, this section presents three additional examples of how to solve problems using loops.

Example: Finding the Greatest Common Divisor

This section presents a program that prompts the user to enter two positive integers and finds their greatest common divisor.

The greatest common divisor of two integers 4 and 2 is 2. The greatest common divisor of two integers 16 and 24 is 8. How do you find the greatest common divisor? Let the two input integers be n1 and n2. You know that number 1 is a common divisor, but it may not be the greatest common divisor. So you can check whether k (for k = 2, 3, 4 and so on) is a common divisor for n1 and n2, until k is greater than n1 or n2. Store the common divisor in a variable named gcd. Initially, gcd is 1. Whenever a new common divisor is found, it becomes the new gcd. When you have checked all the possible common divisors from 2 up to n1 or n2, the value in variable gcd is the greatest common divisor. The idea can be translated into the following loop:

int gcd = 1;
int k = 1;

while (k <= n1 && k <= n2) {
  if (n1 % k == 0 && n2 % k == 0)
    gcd = k;
  k++;
}

// After the loop, gcd is the greatest common divisor for n1 and n2

The complete program is given in Listing 4.6, and a sample run of the program is shown in Figure 4.8.

Figure 4.8. The program finds the greatest common divisor for two integers.

Listing 4.6. GreatestCommonDivisor.java

1 import javax.swing.JOptionPane; 2 3 public class GreatestCommonDivisor { 4 /** Main method */ 5 public static void main(String[] args) { 6 // Prompt the user to enter two integers 7 String s1 = JOptionPane.showInputDialog("Enter first integer"); 8 int n1 = Integer.parseInt(s1); 9 10 String s2 = JOptionPane.showInputDialog("Enter second integer"); 11 int n2 = Integer.parseInt(s2); 12 13 int gcd = 1; [Page 109]14 int k = 1; 15 while (k <= n1 && k <= n2) { 16 if (n1 % k == 0 && n2 % k == 0) 17 gcd = k; 18 k++; 19 } 20 21 String output = "The greatest common divisor for " + n1 + " and " 22 + n2 + " is " + gcd; 23 JOptionPane.showMessageDialog(null, output); 24 } 25 }

How did you write this program? Did you immediately begin to write the code? No. It is important to think before you type. Thinking enables you to generate a logical solution for the problem without concern about how to write the code. Once you have a logical solution, type the code to translate the solution into a Java program. The translation is not unique. For example, you could use a for loop to rewrite the code as follows:

for (int k = 1; k <= n1 && k <= n2; k++) {
  if (n1 % k == 0 && n2 % k == 0)
    gcd = k;
}

A problem often has multiple solutions. The GCD problem can be solved in many ways. Exercise 4.15 suggests another solution. A more efficient solution is to use the classic Euclidean algorithm. See http://www.cut-the-knot.org/blue/Euclid.shtml for more information.

You might think that a divisor for a number n1 cannot be greater than n1 / 2. So you would attempt to improve the program using the following loop:

for (int k = 1; k <= n1 / 2 && k <= ; n2 / 2 k++) {
  if (n1 % k == 0 && n2 % k == 0)
    gcd = k;
}

This revision is wrong. Can you find the reason? See Review Question 4.9 for the answer.

4.8.2. Example: Finding the Sales Amount

You have just started a sales job in a department store. Your pay consists of a base salary and a commission. The base salary is $5,000. The scheme shown below is used to determine the commission rate.

Sales Amount	Commission Rate
$0.01–$5,000	8 percent
$5,000.01–$10,000	10 percent
$10,000.01 and above	12 percent

Your goal is to earn $30,000 a year. This section writes a program that finds the minimum amount of sales you have to generate in order to make $30,000.

Since your base salary is $5,000, you have to make $25,000 in commissions to earn $30,000 a year. What is the sales amount for a $25,000 commission? If you know the sales amount, the commission can be computed as follows:

if (salesAmount >= 10000.01)
  commission =
    5000 * 0.08 + 5000 * 0.1 + (salesAmount - 10000) * 0.12;
else if (salesAmount >= 5000.01)
  commission = 5000 * 0.08 + (salesAmount - 5000) * 0.10;
else
  commission = salesAmount * 0.08;

This suggests that you can try to find the salesAmount to match a given commission through incremental approximation. For a salesAmount of $0.01 (1 cent), find commission. If commission is less than $25,000, increment salesAmount by 0.01 and find commission again. If commission is still less than $25,000, repeat the process until it is greater than or equal to $25,000. This is a tedious job for humans, but it is exactly what a computer is good for. You can write a loop and let a computer execute it painlessly. The idea can be translated into the following loop:

Set COMMISSION_SOUGHT as a constant;
Set an initial salesAmount;

do {
  Increase salesAmount by 1 cent;
  Compute the commission from the current salesAmount;
} while (commission < COMMISSION_SOUGHT);

The complete program is given in Listing 4.7, and a sample run of the program is shown in Figure 4.9.

Figure 4.9. The program finds the sales amount for the given commission.

Listing 4.7. FindSalesAmount.java

1 import javax.swing.JOptionPane; 2 3 public class FindSalesAmount { 4 /** Main method */ 5 public static void main(String[] args) { 6 // The commission sought 7 final double COMMISSION_SOUGHT = 25000; 8 final double INITIAL_SALES_AMOUNT = 0.01; [Page 111] 9 double commission = 0; 10 double salesAmount = INITIAL_SALES_AMOUNT; 11 12 do { 13 // Increase salesAmount by 1 cent 14 salesAmount += 0.01; 15 16 // Compute the commission from the current salesAmount; 17 if (salesAmount >= 10000.01) 18 commission = 19 5000 * 0.08 + 5000 * 0.1 + (salesAmount - 10000) * 0.12; 20 else if (salesAmount >= 5000.01) 21 commission = 5000 * 0.08 + (salesAmount - 5000) * 0.10; 22 else 23 commission = salesAmount * 0.08; 24 } while (commission < COMMISSION_SOUGHT); 25 26 // Display the sales amount 27 String output = 28 "The sales amount $" + (int)(salesAmount * 100) / 100.0 + 29 "\nis needed to make a commission of $" + COMMISSION_SOUGHT; 30 JOptionPane.showMessageDialog(null, output); 31 } 32 }

The do-while loop (lines 12–24) is used to repeatedly compute commission for an incremental salesAmount. The loop terminates when commission is greater than or equal to a constant COMMISSION_SOUGHT.

In Exercise 4.17, you will rewrite this program to let the user enter COMMISSION_SOUGHT dynamically from an input dialog.

You can improve the performance of this program by estimating a higher INITIAL_SALES_AMOUNT (e.g., 25000).

What is wrong if saleAmount is incremented after the commission is computed, as follows?

do {
  // Compute the commission from the current salesAmount;
  if (salesAmount >= 10000.01)
    commission =
      5000 * 0.08 + 5000 * 0.1 + (salesAmount - 10000) * 0.12;
  else if (salesAmount >= 5000.01)
    commission = 5000 * 0.08 + (salesAmount - 5000) * 0.10;
  else
    commission = salesAmount * 0.08;

  // Increase salesAmount by 1 cent
  salesAmount += 0.01;
} while (commission < COMMISSION_SOUGHT);

The change is erroneous because saleAmount is 1 cent more than is needed for the commission when the loop ends. This is a common error in loops, known as the off-by-one error.

Tip

This example uses constants COMMISSION_SOUGHT and INITIAL_SALES_AMOUNT. Using constants makes programs easy to read and maintain.

4.8.3. Example: Displaying a Pyramid of Numbers

This section presents a program that prompts the user to enter an integer from 1 to 15 and displays a pyramid. If the input integer is 12, for example, the output is shown in Figure 4.10.

Figure 4.10. The program uses nested loops to print numbers in a triangular pattern.

Your program receives the input for an integer (numberOfLines) that represents the total number of lines. It displays all the lines one by one. Each line has three parts. The first part comprises the spaces before the numbers; the second part, the leading numbers, such as 3 2 1 in line 3; and the last part, the ending numbers, such as 2 3 in line 3.

Each number occupies three spaces. Display an empty space before a double-digit number, and display two empty spaces before a single-digit number.

You can use an outer loop to control the lines. At the n^th row, there are (numberOfLines – n)*3 leading spaces, the leading numbers are n, n-1, … 1, and the ending numbers are 2, ..., n. You can use three separate inner loops to print each part.

Here is the algorithm for the problem:

Input numberOfLines;

for (int row = 1; row <= numberOfLines; row++) {
  Print (numberOfLines - row) * 3 leading spaces;
  Print leading numbers row, row - 1, ..., 1;
  Print ending numbers 2, 3, ..., row - 1, row;
  Start a new line;
}

The complete program is given in Listing 4.8.

Listing 4.8. PrintPyramid.java

1 import javax.swing.JOptionPane; 2 3 public class PrintPyramid { 4 /** Main method */ 5 public static void main(String[] args) { 6 // Prompt the user to enter the number of lines 7 String input = JOptionPane.showInputDialog( 8 "Enter the number of lines:"); 9 int numberOfLines = Integer.parseInt(input); 10 11 if (numberOfLines < 1 || numberOfLines > 15) { 12 System.out.println("You must enter a number from 1 to 15"); 13 System.exit(0); 14 } 15 16 // Print lines 17 for (int row = 1; row <= numberOfLines; row++) { 18 // Print NUMBER OF LINES – row) leading spaces 19 for (int column = 1; column <= numberOfLines - row; column++) 20 System.out.print(" "); 21 [Page 113]22 // Print leading numbers row, row - 1, ..., 1 23 for (int num = row; num >= 1; num-) 24 System.out.print((num >= 10) ? " " + num : " " + num); 25 26 // Print ending numbers 2, 3, ..., row - 1, row 27 for (int num = 2; num <= row; num++) 28 System.out.print((num >= 10) ? " " + num : " " + num); 29 30 // Start a new line 31 System.out.println(); 32 } 33 } 34 }

The program uses the print method (lines 20, 24, and 28) to display a string to the console. The conditional expression (num >= 10) ? " " + num : " " + num in lines 24 and 28 returns a string with a single empty space before the number if the number is greater than or equal to 10, and otherwise returns a string with two empty spaces before the number.

Printing patterns like this one and the ones in Exercises 4.18 and 4.19 is a good exercise for practicing loop control statements. The key is to understand the pattern and to describe it using loop control variables.

The last line in the outer loop (line 31), System.out.println(), does not have any argument in the method. This call moves the cursor to the next line.