Before we get to the main topic of today's lecture, I want to introduce an example that will help motivate what we are doing today. The example also serves as a nice demonstration that it is possible to write a while loop without a loop counter variable.
Suppose we have a polynomial
and we would like to find a root of the polynomial. That is, we want to find an x such that f(x) = 0. For example the polynomial depicted below has a root somewhere in the interval [1,2].
 |
Here is a strategy for solving this problem, called the binary search algorithm.
What's interesting about this algorithm is that it naturally will lead us to write a loop to do the repetition, and that loop will not use a loop counter to control it.
Before we can write the code for this algorithm, we have to solve one small technical problem: how do we determine whether the root we are looking for lies in the subinterval [left , mid] or the subinterval [mid , right]? The key to solving this problem lies in the observation that if a function has a single root in an interval it will change its sign as you go from one end of the interval to the other. A nice way to check for a sign change in an interval [a , b] is to compute the product f(a)*f(b). If the function has a sign change in the interval, that product will be negative. If the product is positive, then there is no sign change from one end of the interval to the other.
Given these preliminaries, we are now read to write a program to find roots of third degree polynomials.
public class FindRoot {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
double a, b, c, d;
double left, right, mid;
System.out.println("Enter values for a, b, c, and d: ");
a = input.nextDouble();
b = input.nextDouble();
c = input.nextDouble();
d = input.nextDouble();
System.out.println("Enter a range to search:");
left = input.nextDouble();
right = input.nextDouble();
// Compute the midpoint of the range
mid = (left + right) / 2.0;
// While the range is still large,
while (right - left > 10e-6) {
// Evaluate the polynomial at left and x
double fLeft = ((a * left + b) * left + c) * left + d;
double fMid = ((a * mid + b) * mid + c) * mid + d;
// If fLeft*fX is negative, the root is between left and x
// Otherwise, the root is between x and right.
if (fLeft * fMid < 0.0)
right = mid;
else
left = mid;
// Compute a new midpoint
mid = (left + right) / 2.0;
}
System.out.println("The approximate root is " + mid);
}
}
The logic that controls the loop here is based on the behavior of the interval [left , right] as we run the algorithm. The two endpoints are constantly changing their positions as we cut the intervals into subintervals, and the distance between left and right shrinks with each iteration of the while loop. This means that we can make a reasonable stopping criterion for the loop by just watching the distance between left and right. When that distance has shrunk to a suitably small size, we can stop the iteration.
One aspect of the program above is a little clunky. When we want to evaluate the polynomial at a point, we have to write some code like this:
double fLeft = ((a * left + b) * left + c) * left + d;
This is certainly correct, but it would be nice if you could do the same calculation with something that looks a little more like standard mathematical notation:
double fLeft = f(left);
To make this work, we need a mechanism that will allow us to define our own functions and then call them. Java does offer precisely such a mechanism, allowing us to write what Java calls methods.
Here is the program above rewritten to include a method definition for a method that computes the polynomial.
public class FindRootWithMethod {
// Method to compute the value of the polynomial
public static double f(double a,double b,double c,double d,double x) {
return ((a * x + b) * x + c) * x + d;
}
// main method
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
double a, b, c, d;
double left, right, mid;
System.out.println("Enter values for a, b, c, and d: ");
a = input.nextDouble();
b = input.nextDouble();
c = input.nextDouble();
d = input.nextDouble();
System.out.println("Enter a range to search:");
left = input.nextDouble();
right = input.nextDouble();
// Compute the midpoint of the range
mid = (left + right) / 2.0;
// While the range is still large,
while (right - left > 10e-6) {
// Evaluate the polynomial at left and x
double fLeft = f(a,b,c,d,left);
double fMid = f(a,b,c,d,mid);
// If fLeft*fX is negative, the root is between left and x
// Otherwise, the root is between x and right.
if (fLeft * fMid < 0.0)
right = mid;
else
left = mid;
// Compute a new midpoint
mid = (left + right) / 2.0;
}
System.out.println("The approximate root is " + mid);
}
}
Java allows a class to contain multiple methods. Up to this point, in every program we have written we have placed just one method in a class, and that method was always the main method that every program needs. Starting now we are going to write additional methods beyond the main method and place them in our classes.
Here is the code for the new method we placed in the class
public static double f(double a,double b,double c,double d,double x) {
return ((a * x + b) * x + c) * x + d;
}
Methods follow a set of structure rules.
Once you have written a method, you can call the method in your code following a syntax something like the following:
double fLeft = f(a,b,c,d,left);
Note that when you call a method you have to provide as many parameters as the method definition set up in its parameter list. This particular method uses five parameters, so we have to provide values for all five when we call it.
One of the major benefits that methods provide is code reuse. If you have written some code to solve a common problem, it is a good idea to write a method that can do that calculation for you. Then, whenever you need to solve that particular problem you can just call the method to do that work for you.
For example, in an earlier lecture I showed how to write a program that determines how many days are in a month. Since that problem is likely to show up in multiple settings, it would be a good idea to package that code into a method. The parameters to the method would be the month and year, while the return type would be an int telling you how many days are in that month.
Here is the 'how many days in a month' program I showed earlier re-written to use a method.
public class Month {
public static int daysInMonth(int month, int year) {
int days;
if (month == 9 || month == 4 || month == 6 || month == 11) {
days = 30;
} else if (month == 2) {
if (year % 400 == 0) {
days = 29;
} else if (year % 100 == 0) {
days = 28;
} else if (year % 4 == 0) {
days = 29;
} else {
days = 28;
}
} else {
days = 31;
}
return days;
}
public static void main(String[] args) {
int month, year, days;
Scanner input = new Scanner(System.in);
System.out.print("Enter a month and day: ");
month = input.nextInt();
year = input.nextInt();
days = daysInMonth(month, year);
System.out.println("There are " + days + " days in the month "
+ month + " " + year + ".");
}
}
Not all methods have to return a value. Some methods are simply meant to perform a task and do not require a return value. Such methods use a return type of void and simply do not use a return statement. For example, here is a program that uses a void method to print a table of powers to some base that the user inputs.
public class PrintPowers {
// Print all the integer powers of base from 0 to maxPower
public static void printPowers(int base, int maxPower) {
int n = 0;
int power = 1;
while (n <= maxPower) {
System.out.println(base + " to the power " + n + " is " + power);
n++;
power = power * base;
}
}
public static void main(String[] args) {
int b, N;
Scanner input = new Scanner(System.in);
System.out.println("Enter a base and a maximum exponent: ");
b = input.nextInt();
N = input.nextInt();
printPowers(b, N);
}
}
The author pointed out in chapter 4 that Java has a boolean data type that can be used to store true-false values. boolean variables are frequently used in combination with if-else statements or tests in loops.
Here is a somewhat artificial example
public class BooleanExample {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int x, absX;
boolean isPositive;
System.out.print("Enter an integer: ");
x = input.nextInt();
isPositive = (x >= 0);
if (isPositive) {
absX = x;
} else {
absX = -x;
}
System.out.println("The absolute value of " + x + " is " + absX);
}
}
A much more meaningful application for the boolean data type is to use it to write a boolean method. A boolean method answers a question and returns a true or false answer. boolean methods are frequently useful to reduce the complexity of difficult logic. Here is an example of a program that uses a boolean method to determine whether or not a given year is a leap year. The program uses that boolean method to simplify the task of determining how many days are in a month.
public class MonthWithBoolean {
public static boolean isLeapYear(int year) {
boolean result = false;
if (year % 400 == 0)
result = true;
else if ((year % 4 == 0)&&(year % 100 != 0))
result = true;
return result;
}
public static int daysInMonth(int month, int year) {
int days;
if (month == 9 || month == 4 || month == 6 || month == 11)
days = 30;
else if (month == 2) {
if (isLeapYear(year))
days = 29;
else
days = 28;
} else
days = 31;
return days;
}
public static void main(String[] args) {
int month, year, days;
Scanner input = new Scanner(System.in);
System.out.print("Enter a month and day: ");
month = input.nextInt();
year = input.nextInt();
days = daysInMonth(month, year);
System.out.println("There are " + days + " days in the month "
+ month + " " + year + ".");
}
}
A further advantage in doing things this way is that the isLeapYear method we just wrote is likely to be useful beyond this program. By packaging the leap year logic into a method we make that code much more portable.
Sometimes programs will use repetitive logic. Here is the program I showed earlier to compute change and print that results intelligently.
public class ComputeChange {
public static void main(String[] args) {
// Create a Scanner
Scanner input = new Scanner(System.in);
// Receive the amount
System.out.print(
"Enter an amount in double, for example 11.56: ");
double amount = input.nextDouble();
int remainingAmount = (int)(amount * 100);
// Find the number of one dollars
int numberOfOneDollars = remainingAmount / 100;
remainingAmount = remainingAmount % 100;
// Find the number of quarters in the remaining amount
int numberOfQuarters = remainingAmount / 25;
remainingAmount = remainingAmount % 25;
// Find the number of dimes in the remaining amount
int numberOfDimes = remainingAmount / 10;
remainingAmount = remainingAmount % 10;
// Find the number of nickels in the remaining amount
int numberOfNickels = remainingAmount / 5;
remainingAmount = remainingAmount % 5;
// Find the number of pennies in the remaining amount
int numberOfPennies = remainingAmount;
// Display results
String output = "Your amount " + amount + " consists of \n";
if(numberOfOneDollars > 1)
output = output + "\t" + numberOfOneDollars + " dollars\n";
else if(numberOfOneDollars == 1)
output = output + "\t1 dollar\n";
if(numberOfQuarters > 1)
output = output + "\t" + numberOfQuarters + " quarters\n";
else if(numberOfQuarters == 1)
output = output + "\t1 quarter\n";
if(numberOfDimes > 1)
output = output + "\t" + numberOfDimes + " dimes\n";
else if(numberOfDimes == 1)
output = output + "\t1 dime\n";
if(numberOfNickels > 1)
output = output + "\t" + numberOfNickels + " nickels\n";
else if(numberOfNickels == 1)
output = output + "\t1 nickel\n";
if(numberOfPennies > 1)
output = output + "\t" + numberOfPennies + " pennies\n";
else if(numberOfPennies == 1)
output = output + "\t1 penny\n";
System.out.println(output);
}
}
One of the things that jumps out at you immediately in this example is the fact that the code to print the various denominations correctly is highly repetitive. A good thing to do with repetitive code like this is to write a method to carry out the basic task and then just repeatedly call that method to do the necessary work. This often leads to code that is more compact and easier to understand. Here is the example above rewritten to make intelligent use of a method to reduce the redundancy in the code.
public class ComputeChangeWithMethod {
public static String printDenom(int amount, String pluralName,
String singularName) {
String text = "";
if (amount > 1) {
text = "\t" + amount + " " + pluralName + "\n";
} else if (amount == 1) {
text = "\t1 " + singularName + "\n";
}
return text;
}
public static void main(String[] args) {
// Create a Scanner
Scanner input = new Scanner(System.in);
// Receive the amount
System.out.print("Enter an amount in double,
for example 11.56: ");
double amount = input.nextDouble();
int remainingAmount = (int) (amount * 100);
// Find the number of one dollars
int numberOfOneDollars = remainingAmount / 100;
remainingAmount = remainingAmount % 100;
// Find the number of quarters in the remaining amount
int numberOfQuarters = remainingAmount / 25;
remainingAmount = remainingAmount % 25;
// Find the number of dimes in the remaining amount
int numberOfDimes = remainingAmount / 10;
remainingAmount = remainingAmount % 10;
// Find the number of nickels in the remaining amount
int numberOfNickels = remainingAmount / 5;
remainingAmount = remainingAmount % 5;
// Find the number of pennies in the remaining amount
int numberOfPennies = remainingAmount;
// Display results
String output = "Your amount " + amount + " consists of \n";
output = output + printDenom(numberOfOneDollars, "dollars", "dollar");
output = output + printDenom(numberOfQuarters, "quarters", "quarter");
output = output + printDenom(numberOfDimes, "dimes", "dime");
output = output + printDenom(numberOfNickels, "nickels", "nickel");
output = output + printDenom(numberOfPennies, "pennies", "penny");
System.out.println(output);
}
}
The method removed enough redundancy from the original code to make the program overall both shorter and easier to understand.
To practice writing and using some methods, do programming exercises 5.7 and 5.8 on page 172 of the text. I will show the solutions to these problems on Monday.