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